关于红黑树
2018-01-28 本文已影响0人
Rayeston
- 特殊的二叉查找树
- 任意一个节点所包含的键值，大于等于左孩子的键值，小于等于右孩子的键值。
- 红黑树的特性
-
每个节点或者是黑色，或者是红色。
-
根节点是黑色。
-
每个叶子节点是黑色。
-
如果一个节点是红色的，则它的子节点必须是黑色的。
-
从任一节点开始到该节点的所有叶节点的所有路径上，都包含了相同数目的黑节点。
关于最后一条特性：如果不满足该条特性，则不为红黑树
-
红黑树.png
- 旋转
- 旋转的目的是将节点多的一支出让节点给另一个节点少的一支
-
左旋
左旋.gif
-
右旋
右旋.gif
