一般的二叉搜索树

遍历整棵树时间 O(log(n)) ，n为结点的个数

查询，插入，删除的时间是O(log(h)), h为树深

随机构建一个二叉树时间 O(log(n))，n为结点的个数

AVL树

AVL树又称为高度平衡的二叉搜索树。它能保持二叉树的高度平衡，尽量降低二叉树的高度，减少树的平均搜索长度

性质：

1.左子树和右子树的高度之差的绝对值不超过1

2.树中的每个左子树和右子树都是AVL树

3.每个节点都有一个平衡因子(balance factor–bf),任一节点的平衡因子是-1,0,1。(每个节点的平衡因子等于右子树的高度减去左子树的高度 )

一棵AVL树有n个节点，其高度可以保持在logn，插入/删除/查找的时间复杂度也是O(log n)

最早的平衡二叉树之一，windows对进程地址空间的管理用到了AVL树

是平衡搜索树的一种，最坏情况下基本动态集合操作时间为O(log(n))

5个性质：

1.每个结点不是黑色就是红色

2.根结点肯定是黑色

3.每个叶结点(NIL)是黑色的

4.如果一个结点是红色，那么该结点的两个子结点都是黑色的

5.每个结点，到后代叶结点的黑色结点数量是相等的

插入,删除的时间复杂度是O(log(n))

广泛用在C++的STL中。如map和set都是用红黑树实现的。

管理进程控制块

nginx中，用红黑树管理timer

epoll在内核中的实现，用红黑树管理事件块

一棵m阶B树(balanced tree of order m)是一棵平衡的m路搜索树

性质：

1.每个结点储存关键字和关键字的个数，并且该些关键字已非降序存放

2.结点里还存放指向其孩子结点的指针，并且存放bool值的leaf，表明是否是叶子结点

3.每个叶子结点有相同的深度，即树高h

4.假若B树的最小度数为t，除根节点以外的任何结点都必须至少有t-1个关键字，只有t个孩子。每个结点孩子至多是2t-1关键字，和2t个孩子，该结点是满的

5.t越大，树高越小

查找,插入的时间复杂度O(tlog(t)(n)),t为底数

创建时间复杂度O(1)

分裂时间复杂度为O(t)

用在磁盘文件组织，数据索引和数据库索引