集合支持的操作: 1. 搜索 2. 插入 3. 删除 4. 最小值 5. 最大值 6. 前一个 7. 后一个

树是在计算机里实现动态集合的一种数据结构。树可以有很多分支，叫多叉树。但是在计算机世界中，常见的是二叉树。二叉树的时间复杂度依赖树的高度，如果二叉树是一棵平衡的二叉树，那么时间复杂度是O(lgn)。如果是一棵非常不平衡的二叉树，时间复杂度有可能为O(n)。

二叉查找树的定义:

• 左子节点的值小于等于父节点的值
• 右子节点的值大于等于父节点的值

但是二叉查找树不是一棵自平衡的二叉树。为了稳定的得到O(lgn)的时间复杂度，需要保持树的平衡。AVL树、红黑树、B树是自平衡的二叉查找树。

AVL树是最先发明的自平衡的二叉查找树，名称以创始人的名字命名。

AVL树的定义:

红黑树的定义:

• 二叉查找树的所有性质
• 每个节点要么是红的要么是黑的
• 根节点是黑的
• 每个叶子节点(空节点)是黑的
• 如果一个节点是红的，那么它的孩子都是黑的
• 对于每个节点，从该节点到后代叶子节点包含同样数量的黑节点

红黑树主要用于实现集合和字典等内存型数据结构。

B树的定义:

• 每个节点x都有下列属性
  1. x.n是当前被存储在节点x里的关键字的数量
  2. x.key是关键字，其中关键字以非降序存储
  3. x.leaf标识是否为叶子节点。若是，则为TRUE，若不是， 则为FALSE
• 每个节点x也包含x.n+1个指向孩子节点的指针。叶子节点没有孩子，因此叶子节点的指针未定义
• 关键字x.key分割存储在子树里的关键字的范围
• 所有的叶子节点都有同样的深度，即树的高度
• 每个节点拥有的关键字数量有上限和下限。t表示关键字的数量，当t>=2时称为最小的B树。
  1. 除了根节点外每个节点至少有t-1个关键字。除了根节点外每个节点至少有t个孩子。如果树是非空的，根节点至少有一个关键字。
  2. 每个节点至多包含2t-1个关键字。因此，内部节点至多包含2t个孩子。如果包含了2t-1个关键字，则该节点是满的。

B树主要用于对机械硬盘等第二存储设备的访问。

参考

• 算法导论