红黑树和AVL树的定义,特点,及二者区别有哪些?

2019-06-0507:53:53数据结构与算法Comments2,732 views字数 606阅读模式

请你来说一说红黑树和AVL树的定义,特点,以及二者区别。

参考回答:

平衡二叉树(AVL树):文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13421.html

平衡二叉树又称为AVL树,是一种特殊的二叉排序树。其左右子树都是平衡二叉树,且左右子树高度之差的绝对值不超过1。一句话表述为:以树中所有结点为根的树的左右子树高度之差的绝对值不超过1。将二叉树上结点的左子树深度减去右子树深度的值称为平衡因子BF,那么平衡二叉树上的所有结点的平衡因子只可能是-1、0和1。只要二叉树上有一个结点的平衡因子的绝对值大于1,则该二叉树就是不平衡的。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13421.html

红黑树:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13421.html

红黑树是一种二叉查找树,但在每个节点增加一个存储位表示节点的颜色,可以是红或黑(非红即黑)。通过对任何一条从根到叶子的路径上各个节点着色的方式的限制,红黑树确保没有一条路径会比其它路径长出两倍,因此,红黑树是一种弱平衡二叉树,相对于要求严格的AVL树来说,它的旋转次数少,所以对于搜索,插入,删除操作较多的情况下,通常使用红黑树。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13421.html

性质:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13421.html

1. 每个节点非红即黑文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13421.html

2. 根节点是黑的;文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13421.html

3. 每个叶节点(叶节点即树尾端NULL指针或NULL节点)都是黑的;文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13421.html

4. 如果一个节点是红色的,则它的子节点必须是黑色的。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13421.html

5. 对于任意节点而言,其到叶子点树NULL指针的每条路径都包含相同数目的黑节点;文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13421.html

区别:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13421.html

AVL 树是高度平衡的,频繁的插入和删除,会引起频繁的rebalance,导致效率下降;红黑树不是高度平衡的,算是一种折中,插入最多两次旋转,删除最多三次旋转。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13421.html

  • 本站内容整理自互联网,仅提供信息存储空间服务,以方便学习之用。如对文章、图片、字体等版权有疑问,请在下方留言,管理员看到后,将第一时间进行处理。
  • 转载请务必保留本文链接:https://www.cainiaoxueyuan.com/suanfa/13421.html

Comment

匿名网友 填写信息

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定