数据结构_红黑树

1、二叉树

• 每一个分支不能超过两个

2、 排序数/查找树

• 在二叉树的基础上，元素是有大小顺序的
• 左 子树 小，右 子树 大

 3、平衡树

• 左孩子数 和  右孩子数 相等

 4、不平衡树

5、 红黑树

• 特点：趋近于平衡树，查询的速度非常的快，查询叶子节点最大次数和最小次数不能超过2倍
• 约束：

1. 节点可以是红色的或者黑色的
2. 根节点是黑色的
3. 叶子节点（空节点）是黑色的
4. 每个红色的节点的子节点都是黑色的
5. 任何一个节点到其每一个叶子节点的所有路径上黑色节点数相同