关于红黑树建立的图解~
关于红黑树建立的图解
红黑树的性质
- 节点是红或黑
- 根节点是黑
- 每个叶节点是黑的
- 一个节点是红，则它的儿子都为黑
- 每个节点从该节点到其子孙节点的所有路径上包含相同数目的黑节点
- 插入1，2，3
注意：外部节点为空且为黑色
插入时的调整
双红调整
节点u就是新插入结点的父节点的父节点的另一个孩子。
- 如果节点u为黑色，分为左左、右右、左右、右左四种情况进行。
- 如果节点u为红色，修改g、p、u三个结点的颜色
- g由黑变红，如果是根节点则颜色变为黑色。
- p、u颜色由红变黑。
x:当前节点 p:parent u:uncle g:grandparent
例：依次插入1、2、3、4
为序列1…12建立RB树
建立之后的结果如下：
具体过程就省略了~按照上面的方法就能得出……