红黑树插入算法疑问解决办法
红黑树插入算法疑问
本人在看红黑树的插入算法的时候有一些疑问,想请教诸位能人。
红黑树插入算法中对于,如果插入节点的父接点，叔节点为红色,则将父节点与叔节点改为红色,将祖父节点改为黑色,然后将祖父节点作为判断点进行颜色修正判断.我的疑问就是，如果 祖父节点作为根节点，则直接改为黑色。这样就变成，插入节点为红色，父，叔，祖父都为黑色.为什么不是,对父节点作右旋操作,然后 父节点为黑色,插入节点与祖父节点为红色？
黑(g) 红(g) 黑(p)
红(p) 红(u)-> 黑(p) 黑(u) -> 红 红(g)
红 红 黑(u)
另外一个疑问是:红黑树允许多个黑节点连续存在吗？还是强制要有黑红黑红的节点顺序？
请指教~~~~
------解决方案--------------------
看来楼主对红黑树的定义有点疑惑。
红黑树允许多个黑节点连续存在吗？还是强制要有黑红黑红的节点顺序？
红黑树运行多个黑色节点连续存在，但不允许有两个红色节点连续存在，
下面是红黑树的性质。
性质1. 节点是红色或黑色。
性质2. 根节点是黑色。
性质3 每个叶节点是黑色的。
性质4 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
性质5. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
仔细看看就能解决你的疑惑
------解决方案--------------------
1.允许连续黑。（不然很多情况下无法满足其他红黑树性质）
2.“如果插入节点的父接点，叔节点为红色,则将父节点与叔节点改为红色,将祖父节点改为黑色”
这里写错了吧，应该为：如果插入节点的父接点，叔节点为红色,则将父节点与叔节点改为黑色,将祖父节点改为红色
3. 如果父节点为黑色，直接插入就行（新插入节点总是红色），不用做任何额外操作
------解决方案--------------------
补充：后续步骤（父节点与叔节点改为黑色,将祖父节点改为红色之后）
1. 当前节点改为上一步的祖父节点
2. 如果新的当前节点的父节点为黑色（这里包括了当前节点为根节点，因为一般处理红黑树时，会把应该指向null的指针指向一个默认的黑色节点），直接改为黑色，插入完毕。
3. 现在单签节点的父节点一定为红色了。判断叔节点，为红则重复最开始的步骤（父节点与叔节点改为黑色,将祖父节点改为红色）。
4. 叔节点为黑，这里又要分父节点是祖父节点的左子树还是右指数了，分别对应两套解法
本人在看红黑树的插入算法的时候有一些疑问,想请教诸位能人。
红黑树插入算法中对于,如果插入节点的父接点，叔节点为红色,则将父节点与叔节点改为红色,将祖父节点改为黑色,然后将祖父节点作为判断点进行颜色修正判断.我的疑问就是，如果 祖父节点作为根节点，则直接改为黑色。这样就变成，插入节点为红色，父，叔，祖父都为黑色.为什么不是,对父节点作右旋操作,然后 父节点为黑色,插入节点与祖父节点为红色？
黑(g) 红(g) 黑(p)
红(p) 红(u)-> 黑(p) 黑(u) -> 红 红(g)
红 红 黑(u)
另外一个疑问是:红黑树允许多个黑节点连续存在吗？还是强制要有黑红黑红的节点顺序？
请指教~~~~
------解决方案--------------------
看来楼主对红黑树的定义有点疑惑。
红黑树允许多个黑节点连续存在吗？还是强制要有黑红黑红的节点顺序？
红黑树运行多个黑色节点连续存在，但不允许有两个红色节点连续存在，
下面是红黑树的性质。
性质1. 节点是红色或黑色。
性质2. 根节点是黑色。
性质3 每个叶节点是黑色的。
性质4 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
性质5. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
仔细看看就能解决你的疑惑
------解决方案--------------------
1.允许连续黑。（不然很多情况下无法满足其他红黑树性质）
2.“如果插入节点的父接点，叔节点为红色,则将父节点与叔节点改为红色,将祖父节点改为黑色”
这里写错了吧，应该为：如果插入节点的父接点，叔节点为红色,则将父节点与叔节点改为黑色,将祖父节点改为红色
3. 如果父节点为黑色，直接插入就行（新插入节点总是红色），不用做任何额外操作
------解决方案--------------------
补充：后续步骤（父节点与叔节点改为黑色,将祖父节点改为红色之后）
1. 当前节点改为上一步的祖父节点
2. 如果新的当前节点的父节点为黑色（这里包括了当前节点为根节点，因为一般处理红黑树时，会把应该指向null的指针指向一个默认的黑色节点），直接改为黑色，插入完毕。
3. 现在单签节点的父节点一定为红色了。判断叔节点，为红则重复最开始的步骤（父节点与叔节点改为黑色,将祖父节点改为红色）。
4. 叔节点为黑，这里又要分父节点是祖父节点的左子树还是右指数了，分别对应两套解法