红黑树与平衡二叉树的区别,红黑树平衡树对比

首页 > 经验 > 作者:YD1662022-11-14 14:54:56

因为以上插入点的特殊性,插入后的整棵树还是平衡的(插入点所在位置的节点的最高深度为5,与其它节点的最高深度相等)。

在原树上插入20:

红黑树与平衡二叉树的区别,红黑树平衡树对比(9)

可以看到,插入以后树已经不是一个平衡的二叉树(最高深度成了6),而且并不满足红黑树的要求,因为20和21均为红色,这种情况下就需要对红黑树进行变色,21需要变为黑色,22就会变成红色,如果22变成红色,则需要17和25都变成黑色:

红黑树与平衡二叉树的区别,红黑树平衡树对比(10)

而17变成黑色显然是不成立的,因为如果17变为黑色,那么13就会变为红色,不满足二叉树的规则,因此此处需要进行另一个操作---------左旋操作

红黑树与平衡二叉树的区别,红黑树平衡树对比(11)

左旋:下图就是一个左旋的例子,一般情况下,如果左子树深度过深,那么便需要进行左旋操作以保证左右子树深度差变小

红黑树与平衡二叉树的区别,红黑树平衡树对比(12)

上一页12345下一页

栏目热文

文档排行

本站推荐

Copyright © 2018 - 2021 www.yd166.com., All Rights Reserved.