首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往
  • 您找到你想要的搜索结果了吗?
    是的
    没有找到

    奈学:红黑树(RedBlackTree)的概述

    AVL树是一种自平衡的二叉查找树,又称平衡二叉树。AVL用平衡因子判断是否平衡并通过旋转来实现平衡,它的平衡的要求是:所有节点的左右子树高度差不超过1。AVL树是一种高平衡度的二叉树,执行插入或者删除操作之后,只要不满足上面的平衡条件,就要通过旋转来保持平衡,而的由于旋转比较耗时,由此我们可以知道AVL树适合用于插入与删除次数比较少,但查找多的情况。   由于维护这种高度平衡所付出的代价可能比从中获得的效率收益还大,故而实际的应用不多,更多的地方是用追求局部而不是非常严格整体平衡的红黑树。   红黑树(Red Black Tree),它一种特殊的二叉查找树,是AVL树的特化变种,都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡,从而获得较高的查找性能。 红黑树的平衡的要求是:从根到叶子的最长的路径不会比于最短的路径的长超过两倍。 因此,红黑树是一种弱平衡二叉树,在相同的节点情况下,AVL树的高度<=红黑树。   红黑树是用弱平衡来换取增删节点时候旋转次数的降低,任何不平衡都会在三次旋转之内解决,降低了对旋转的要求,从而提高了性能,所以对于查询,插入,删除操作都较多的情况下,用红黑树。

    00

    平衡二叉树与红黑树的区别_平衡二叉树怎么构造

    红黑树是一颗二叉搜索树,通过对任何一条从根到叶子的简单路径上各个结点的颜色进行约束,红黑树确保没有一条路径会比其他路径长出2倍,因而是近似于平衡的。   树的每个结点包含5个属性,color,key,left,right,p。如果一个结点没有子结点或父结点,则该结点的响应指针属性的指为NIL。我们可以把这些NIL视为指向二叉搜索树的叶结点(外部节点)的指针,把带关键字的结点视为树的内部结点。     一颗红黑树是满足下面红黑性质的二叉搜索树:       1.每个结点或是红色的,或是黑色的。       2.根结点是黑色的。       3.每个叶子结点(NIL)是黑色的。       4.如果一个结点是红的,那么它的两个子结点都是黑的。       5.对每个结点,从该结点到其所有后代叶结点的简单路径上,均包含相同数目的黑结点。 ——引用自《算法导论》 第十三章 红黑树 红黑树的性质

    02
    领券