有关红黑树

这个呢,是我很久之前就写了一部分的,本来想把插入删除的都给写了,后面由于我的懒惰,一直没有更新删除,但这次,我还是不会更,啊哈哈哈哈

---

迷之分割线,第一次使用Markdown,不太6啊
下面就是正题了.
首先呢,要知道什么是红黑树.

在算法导论对R-B Tree的介绍：红黑树，一种二叉查找树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的。

红黑树有以下几个特点:

• 每个结点要么是红的要么是黑的。

• 根结点是黑的。
• 每个叶结点（叶结点即指树尾端NIL指针或NULL结点）都是黑的。
• 如果一个结点是红的，那么它的两个儿子都是黑的。
• 对于任意结点而言，其到叶结点树尾端NIL指针的每条路径都包含相同数目的黑结点。

其次是为什么要用红黑树而不用AVL,我个人理解就是AVL是平衡的,每插入删除一个节点都会调整,而且调整的效率并不高,很可能要调很多次.而红黑树是近似平衡的,最多3次即可调整完毕,是比较快速的.

接下来就是红黑树的插入删除了.

PS:删除等我哪天闲下来再更吧...虽然不难,但是我懒啊

红黑树的每次插入删除的调整的目的都是为了使得这棵树满足上面的5个特点.所以调整思路很容易就确定出来的(这里就当我扯淡吧,在没看例子的时候还是挺难想到想全的,膜一下鲁道夫·贝尔大大).

插入部分

插入的过程相对来说还是比较容易的.因为特点中说从根到叶节点的黑节点数要相同.所以每次插入的要是是红色的节点那就肯定不会影响红黑树的这几个特点了,所以我们就每次插入红色的节点.但又有个问题,红节点的孩子不能是红色的,所以要进行变色调整.接下来就详细描述一下这个过程好了.

• 1.最简单的情况插入的位置的父节点是黑色的,那就直接插就好了,不用做调整.因为它的插入不会影响红黑树的性质.

• 2.插入的是根节点,那直接把这个节点变成黑色就好了,因为根节点必须是黑色的.

• 3.插入的节点的父节点是红色的,这个系列是最麻烦的. 详细说一下.

• 3.1父节点是红色的且叔叔节点(叔叔节点就是父亲的兄弟节点)是红色的.
  因为父亲是红色的,所以必须有爷爷节点(父亲的父节点).且爷爷是黑色的,那么解决策略就是：将当前节点的父节点和叔叔节点涂黑，祖父结点涂红，把当前结点指向祖父节点，从新的当前节点重新开始算法.
  插个图说明下好了
  插入前:
  

  Paste_Image.png
  插入后:

Paste_Image.png

废话下,说详细点好了,为什么这么做呢.原因:它的插入使得红黑树的性质被破坏了,所以,我们就先维护爷爷节点这一块往下的子树,使得其满足红黑树的性质,然后再往上接着维护.那这么维护真的可以么,嗯,因为如果将父亲和叔叔都变黑了,祖父变成红色,那么这一整颗子树的从祖父到叶子的黑节点数还是和插入这货之前的一样,所以这方法是可以的.

• 3.2父节点是红色,叔叔节点是黑色.这个可以用一个图表来总结.(本人写字丑,忍忍吧).

20161008230546547.jpg
上面呢就是总结出来的.
下面引用个JULY(原文链接)的图来说明下,图上的圆圈呢是情况的号码.如果5出现,必定接着使用6的方法来进行调整.先凑合着看看,下面详细说下 Paste_Image.png Paste_Image.png

5和6是配套的,因为不可能只出现5,出现5都会转到6.简单的说,5就是将树调整成6的适用条件.然后6的调整原理就是:(举个例子,用图中左左的的情况)因为插入是红的,父是红的,且插入的和父亲都是左子,叔叔是黑的,那祖父肯定是黑的,所以变色后右旋一次,路径中的黑子数还是一样的,也没有红节点孩子是红色,保证了红黑树的性质,所以这个解决方案就是可行的了.
到此插入就讲完了,很简单吧. 有空再更删除.不用期待,很少有空的,啊哈哈哈.