红黑树--插入

本文主要是介绍红黑树--插入，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

 红黑树转换：https://www.cs.usfca.edu/~galles/visualization/RedBlack.html

 红黑树的性质

性质1. 结点是红色或黑色。

性质2. 根结点是黑色。

性质3. 所有叶子都是黑色。（叶子是NIL结点）

性质4. 每个红色结点的两个子结点都是黑色。（从每个叶子到根的所有路径上不能有两个连续的红色结点）

性质5. 从任一节结点其每个叶子的所有路径都包含相同数目的黑色结点。

插入情况        （不建议直接看插入情景，直接看下面例子）

        1. 父结点为黑色时

                直接将插入结点与父结点

        2.父结点为红色时

                2.1 若插入结点的父结点的兄弟结点为红色时，父结点和父结点的兄弟结点变为黑色，父结点的父结点变为红色，此时插入结点为父结点的父结点

                2.2 若插入结点的父结点的兄弟结点为黑色时 （这种情况不存在）

                2.3 若父结点是左结点且无兄弟结点时

                        2.3.1 插入结点插入到父结点的左结点时，则对父结点和父结点的父结点颜色互换，然后对父结点的父结点右旋

                        2.3.2 插入结点插入到父结点的右结点时，先对父结点左旋，此时插入结点和父结点身份互换，再对父结点和父结点的父结点颜色互换，然后对父结点的父结点右旋

                2.4 若父结点是右结点且无兄弟结点时

                        2.4.1 插入结点插入到父结点的右结点时，则对父结点和父结点的父结点颜色互换，然后对父结点的父结点左旋

                        2.4.2 插入结点插入到父结点的左结点时，先对父结点右旋，此时插入结点和父结点身份互换，再对父结点和父结点的父结点颜色互换，然后对父结点的父结点左旋

下面我们用例子来说明（下面讨论都不引入”叶子是NIL结点“，图1不含有NIL结点，图2含有NIL结点）

                              图 1                                                             图 2     

 向下图中的图1 插入一个250的结点（插入的结点都是红结点）

 变化过程如下图(变化情景应为 2.1)

                 2.1 若插入结点的父结点的兄弟结点为红色时，父结点和父结点的兄弟结点变为黑色，父结点的父结点变为红色，此时插入结点为父结点的父结点

 对下图 插入一个 100 结点 变化过程 如下图

   2.3.1 插入结点插入到父结点的左结点时，则对父结点和父结点的父结点颜色互换，然后对父结点的父结点右旋

 对下图 插入一个 270 结点 变化过程 如下图

   2.3.2 插入结点插入到父结点的右结点时，先对父结点左旋，此时插入结点和父结点身份互换，再对父结点和父结点的父结点颜色互换，然后对父结点的父结点右旋

 向下图插入一个450的结点

2.4.1 插入结点插入到父结点的右结点时，则对父结点和父结点的父结点颜色互换，然后对父结点的父结点左旋

  向下图插入一个370的结点

   2.4.2 插入结点插入到父结点的左结点时，先对父结点右旋，此时插入结点和父结点身份互换，再对父结点和父结点的父结点颜色互换，然后对父结点的父结点左旋

这篇关于红黑树--插入的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！