断断续续看了好几天，终于把红黑树看懂了。
先上成果：http://linzhihe.top/rb-tree/
R-B Tree，全称是Red-Black Tree，又称为“红黑树”，它一种特殊的二叉查找树。红黑树的每个节点上都有存储位表示节点的颜色，可以是红(Red)或黑(Black)。
红黑树的基本性质
- 每个节点或者是黑色，或者是红色。
- 根节点是黑色。
- 每个叶子节点（NIL）是黑色。 [注意：这里叶子节点，是指为空(NIL或NULL)的叶子节点！
- 如果一个节点是红色的，则它的子节点必须是黑色的。
- 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。
这里特别要注意下第三条性质，
图一
这里第一个图是没有加Nil节点的，看起来是不是满足红黑树的所以性质？
但是第二个图加了Nil节点之后，就不满足（5）了。
左旋和右旋
左旋和右旋是红黑树操作中的基础，上两个图，只可意会，不可言传。。。。。。
右旋
左旋
可以看出来，这两个过程其实是互逆的。
新增节点
第一步：将红黑树当作一颗二叉查找树，将节点插入。 红黑树本身就是一颗二叉查找树，将节点插入后，该树仍然是一颗二叉查找树。也就意味着，树的键值仍然是有序的。此外，无论是左旋还是右旋，若旋转之前这棵树是二叉查找树，旋转之后它一定还是二叉查找树。这也就意味着，任何的旋转和重新着色操作，都不会改变它仍然是一颗二叉查找树的事实。
第二步：将插入的节点着色为"红色",这样不会违背性质1,2,3,5.
第三步：通过一系列的旋转或着色等操作，使之重新成为一颗红黑树。可大致分为以下四种情况：
-
插入节点的父节点为黑色。
第一种情况
这种情况没什么好说的，不违反任何性质。
-
父节点为红色，必然存在祖父节点。且祖父节点为黑色。存在叔叔节点，且叔叔节点为红色。
第二种情况
这样做了之后就不会违反性质5了，但是有可能违反性质4，所以可以把gp单做新插入的节点处理，也就是把gp及其子节点单做一个整体->新插入的红色节点。
-
父节点为红色，必然存在祖父节点。且祖父节点为黑色。叔叔节点不存在，也就是为NIL。或者在2的情况下，叔叔节点也可能存在不为NIL的黑色节点的情况。这里就统一用黑色节点表示了。
新插入节点、父节点、祖父节点在一条直线上。
第三种情况
这里还是要解释下u这个节点，如果为NIL自然没问题，但是如果为非NIL的黑色节点，那么新插入的n节点也必然不是单纯的红色节点，而是第二种情况下被单做红色节点的情况，里面内含黑色节点。
-
其他和第三种情况一样，就是新插入节点、父节点、祖父节点不在一条直线上。
第四种情况
这样处理之后就变成了第三种情况，然后以p节点为新插入的红色节点继续处理。
删除节点
可根据删除节点的左右孩子（非NIL节点）分为3种
- 左右子树都不为空
- 只有左子树或者右子树（只有一个非NIL孩子节点）
- 左右子树都没有
对于第一种情况，可以从左子树找出最大值或者右子树找出最小值作为替代节点，将替代节点的值复制到删除节点，再将替代节点删除。这样就转换为2或者3情况了。
在2、3种情况下：
- 删除节点的颜色为红色
这种情况下，删除节点必为情况3.所以直接删除就好。 -
删除节点为黑色，只有一个孩子节点，且这种情况下孩子节点必为红色。
黑色节点-红孩子
这种情况直接将孩子节点替换删除节点，并将孩子节点颜色变黑即可。
-
删除节点为黑色，没有非NIL子节点（情况3），先把节点删除了，把顶替删除节点的NIL节点称之为当前节点，再来分析：
3.1)
兄弟节点红色
兄弟节点红色的情况下，将父节点和兄弟节点的颜色互换，转换为3.2 3.3 3.4的情况里的一种
3.2)
兄弟节点黑色-远侄子节点红色
兄弟节点为黑色，且远侄子节点为红色节点。
父节点白色代表可能为黑也可能为红。
近侄子节点为白色代表可能为NIL或者红色，在3.5的情况下也有可能为黑色
3.3)
兄弟节点黑色-近侄子节点红色
兄弟节点黑色，远侄子节点为空，近侄子节点红色，转换后就变成3.2的情况了，然后按照3.2的情况处理。
3.4)
兄弟节点黑色-侄子节点不为红色-父节点红色
兄弟节点黑色，侄子节点不为红色，父节点为红色，只需要把父节点和兄弟节点颜色对调即可。
3.5)
兄弟节点黑色-侄子节点不为红色-父节点黑色
兄弟节点黑色，侄子节点不为红色，父节点为黑色，这种情况只能讲兄弟你节点变红，此时P内部满足红黑树，但是经过P的外部少一个黑节点，所以可以吧P内部整体当做一个NIL节点来处理，重复上面的逻辑。
网友评论