数据结构-红黑树
1.定义
红黑树是自平衡的二叉查找树。
2.性质
1）每个节点要么是黑色，要么是红色。
2）根节点为黑色。
3）每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)。
4）从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
这些约束强制了红黑树的关键性质: 从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。结果是这个树大致上是平衡的。因为操作比如插入、删除和查找某个值的最坏情况时间都要求与树的高度成比例，这个在高度上的理论上限允许红黑树在最坏情况下都是高效的，而不同于普通的二叉查找树。
红黑树
在红黑树中，叶子被假定为nil或空，它不包含数据而只充当树在此结束的指示。
3.插入
假设我们现在要插入一个新的节点，如过插入的这个新的节点为黑色，那么必然会违反性质（4），所以我们把新插入的点定义为红色的。但是如果插入的新节点为红色，就可能会违反性质(3) ，出行双红的情况，因此我们需要对其进行调整，使得整棵树依然满足红黑树的性质，也就是双红修正。
以下为插入全过程：依次插入50，27，90，48，45，56，78，40，35
1）插入50，因为根结点为空，所以插入50为黑色。
2） 插入27，27<50,插入到左子树。
3）插入90，90>50插入到右子树
4）插入48，48<50在根节点左子树，又大于27，插入到27右子树，因为不满足性质3，出现双红，所以调整，改变父亲和叔叔的颜色为黑色。
5）插入45，首先右旋，将48作为新的结点插入，改变父亲节点45颜色，祖父结点27颜色，再左旋。
6）插入56
7）插入78，先左旋，把56当作为新插入的结点，调整父亲78颜色和祖父90的颜色，再右旋
8）插入40
9）插入35
矫情吗；*
太过爱你忘了你带给我的痛
àì夳堔傛蜴生んèń
我会带着你远行
不念不忘少年蓝@
还没有评论，来说两句吧...