【RBT】

【RBT】

红黑树性值

1、红黑树中每个节点要么是红的要么是黑的2、根节点必须是黑色的3、终端节点是黑色的4、不允许两个红节点互为父子关系5、从任意节点出发，到其所有可能到达的各个终端节点的各条路径上，黑色节点数目必须完全相同

添加

1、【空树】：作为根（黑）2、【父黑】：直接放入（红）3、【父红】：

PP刚好为根结点时，我们必须把PP重新设为黑色，那么树的红黑结构变为：黑黑红。换句话说，从根结点到叶子结点的路径中，黑色结点增加了。这也是唯一一种会增加红黑树黑色结点层数的插入情景。 我们还可以总结出另外一个经验：红黑树的生长是自底向上的。这点不同于普通的二叉查找树，普通的二叉查找树的生长是自顶向下的。

3.2【叔黑】：

3.2.1：【父是爷.左】：

3.2.1.1：【x是父.右】：父标记为x，以x为支点左旋3.2.1.2：【x是父.左】：父->黑，爷->红，以爷为支点右旋

3.2.2：【父是爷.右】：

3.2.2.1：【x是父.左】：父标记为x，以x为支点右旋3.2.2.2：【x是父.右】：父->黑，爷->红，以爷为支点左旋

删除

（找左的最右|右的最左，之后都会转变=>删除某节点X，此节点至多有一个孩子）

1、【根、无孩子】：删除根空 2、【根、有一个红孩子】：删根、红子->黑，成为新根 3、【非根、红】：删除 4、【非根、黑、有一个红子】：删X，X子和X父连接，红子->黑 5、【非根、黑、无子】：删除X：5.1【兄弟是红】（父、侄一定是黑）：父->红，兄->黑：5.1.1【兄是父的右】：以父为支点左旋 5.1.2【兄是父的左】：以父为支点右旋 5.2【兄弟是黑】：5.2.1【俩侄子全黑（由其他情况转移到此情况）|空】：5.2.1.1【父是红】：父->黑，兄->红。Over。 5.2.1.2【父是黑】：兄->红，父为新X；重新讨论，向上求助 5.2.2【左侄红、右侄黑】：5.2.2.1【兄是父.右】：兄->红，左侄->黑，以兄为支点右旋；=>5.2.3.2 5.2.2.2【兄是父.左】：兄->父.色，父->黑，左侄->红，以父为支点右旋。Over。 5.2.3【右侄红】 ：5.2.3.1【兄是父.左】：兄->红，右侄->黑，以兄为支点右旋；=>5.2.2.2 5.2.3.2【兄是父.右】：兄->父.色，父->黑，右侄->黑，以父为支点左旋。Over。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。