lgn

请注意，本文编写于 192 天前，最后修改于 192 天前，其中某些信息可能已经过时。 归并排序是利用归并的思想实现的排序方法，该算法采用经典的分治策略。递归的将数组两两分开直到只包含一个元素，然后将数组排序合并，最终合并为排序好的数组

如果中序遍历为有序的话则为二叉搜索树，为了避免退化为单链表，加入平衡规则后保持平衡则为平衡二叉树，搜索的时间复杂度为O(lgn). 满二叉树、完全二叉树又推出最大堆、最小堆（堆排序、定时器）。平衡二叉树又推出avl、红黑树。 对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树