红黑树原理

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

一、红黑树定义

1、根节点是黑色的。

2、每一个叶子结点都是黑色的 nil 节点，也就是说叶子结点不存放数据。

3、任何相邻节点都不能同为红色节点。红色节点是被黑色节点隔开的。

4、每个节点，从该节点开始到达该节点的叶子结点的任何路径包含相同数目的黑色节点。

二、节点左旋和右旋

        树的左旋

         树的右旋

一、红黑树增加节点

增加的节点都是红色节点；

情况一：插入的节点是根节点，不用操作，直接把红色改为黑色即可。

情况二：父节点是黑色节点，不用做任何操作，直接加入即可。

情况三：父节点是红色节点，父节点的兄弟节点也是红色节点；

        将加入节点的父节点和叔叔节点都变为黑色，父节点的父节点变为红色。

 情况四：父节点是红色节点，叔叔节点是黑色节点，这种情况分为四种状态；

 状态1：左左

                节点 x 在左子树的左侧节点，就将父节点 g 右旋 ，然后 p 节点和当前 p 节点的右节点交换颜色；

 状态二： 左右

        节点p左旋，变为左左状态，重复左左操作。

 状态三：右右

        将 g 节点左旋，然后 g 节点和父节点交换颜色。

 状态四：右左

        将 p 节点右旋，节点状态变为 右右状态，重复右右操作。

 三、举例节点新增

        节点加入顺序  ：10 ，70，32，34，13，56，21，如下图所有流程。

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