数据结构 - 红黑树之宁式记忆口诀

尝试用口诀的方式记忆数据结构 1.0Beta抢鲜版

二叉查找树（Binary Search Tree）

BST特性

1.左子树上所有结点的值均小于或等于它的根结点的值。
2.右子树上所有结点的值均大于或等于它的根结点的值。
3.左、右子树也分别为二叉排序树。

尝试查找节点8的位置：9-5-7-8

缺点：如果新增节点时，初始节点只有9，5，13。按顺序插入4，3，2，1。则会导致二叉树的不平衡性

红黑树

自平衡的二叉查找树，满足二叉查找树的特征外

1.结点是红色或黑色。
2.根结点是黑色。
3.每个叶子结点都是黑色的空结点（NIL结点）。
4 每个红色结点的两个子结点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色结点)
5.从任一结点到其每个叶子的所有路径都包含相同数目的黑色结点。

比如插入21节点，13-17-25-22-21。则会打破红黑树的规则4。为了满足红黑树得规则

1、变色：尝试把红色结点变为黑色，或者把黑色结点变为红色。
2、旋转

2.1 左旋转 逆时针旋转两个节点

2.1 右旋转

使用手册

1、新节点的父亲节点和叔叔节点是红色： 变色父为黑，根节点为红，叔叔节点为黑 （口诀：父亲叔叔红了。变成黑，根节点变成红~）

2、新结点的父结点是红色，叔叔结点是黑色或者没有叔叔，且新结点是父结点的右孩子，父结点是祖父结点的左孩子。

已B为轴，进行左旋。

仍未到红黑树要求。先记录下口诀。（我有一个红父亲，我是父亲的右孩子，父亲是爷爷的左孩子。以父亲为轴进行左旋~）

3、新结点的父结点是红色，叔叔结点是黑色或者没有叔叔，且新结点是父结点的左孩子，父结点是祖父结点的左孩子。

处理方式：对祖父节点进行右旋，之后变色未满足条件的节点即可
祖父节点右旋：

将不满足红黑树条件的进行变色

口诀：我的父亲是红色的，我是父亲的左孩子，父亲也是爷爷的左孩子。爷爷右旋，然后变变色彩吧~

*以上父亲节点都是祖父节点的左孩子。如果父亲节点为右孩子，2情况变为了3情况的镜像，3情况变为了2情况的镜像
即可以把3的情况的操作变为左旋，2的情况操作变为右旋

记忆点图

21为新节点，变为符合红黑树规则的自平衡二叉查找树
（秘籍：1情况之变色，3情况之镜像之左旋，调调色啦）