二叉树、平衡树、红黑树

1. 二叉查找树

• 左子树上所有结点的值均小于或等于它的根结点的值。
• 右子树上所有结点的值均大于或等于它的根结点的值。
• 左、右子树也分别为二叉排序树。

2. 平衡二叉树

• 满足二叉查找树的定义
• 必须满足任何节点的两个子树的高度差不能大于1

3. 红黑树（是一种自平衡的二叉查找树）

• 根节点是黑色
• 节点是红色或黑色
• 每个叶子节点都是黑色的空节点（NIL）
• 每个红色节点的两个子节点都是黑色（从每个叶子到根的所有路径上不能有两个连续的红色节点）
• 从任一节点到叶子节点所有路径包含的黑色节点数目相同

未满足上述条件，需要通过[旋转]和[变色]来调整

注：数据库使用的B+Tree（Balance Tree），是m叉树（多路搜索树）。它的所有的关键字（可以理解为数据）都存储在叶子节点（Leaf Page），非叶子节点（Index Page）并不存储真正的数据，所有记录节点都是按键值大小顺序存放在同一层叶子节点上。其次，所有的叶子节点由指针连接。

漫画算法：什么是红黑树？