红黑树和普通二叉树的区别_红黑树是完全二叉树吗

红黑树和普通二叉树的区别_红黑树是完全二叉树吗红黑树与平衡二叉树区别?如果说平衡二叉树是一个类的话,那么红黑树就是该类的一个实例。算法的书我丢久了,一下子也找不到,我是凭记忆说的。红黑树的算法比较麻烦,但它的思想很好,如果理解了它的思想也就理解它的算法,我也只记得思想,具体算法记不得了。我就在这说说

红黑树与平衡二叉树区别?   如果说平衡二叉树是一个类的话,那么红黑树就是该类的一个实例。算法的书我丢久了,一下子也找不到,我是凭记忆说的。红黑树的算法比较麻烦,但它的思想很好,如果理解了它的思想也就理解它的算法,我也只记得思想,具体算法记不得了。我就在这说说思想吧。红黑树有两个重要性质:1、红节点的孩子节点不能是红节点;2、从根到前端节点的任意一条路径上的黑节点数目一样多。   这两条性质确保该树的高度为logN,所以是平衡树。   红黑树是每个节点都带颜色的树,节点颜色或是红色或是黑色,红黑树是一种查找树。红黑树有一个重要的性质,从根节点到叶子节点的最长的路径不多于最短的路径的长度的两倍。对于红黑树,插入,删除,查找的复杂度都是O(log N)。插入的节点总是设为红节点,当其复节点为红节点时,这就有破坏了性质1,就需要调整。将插入节点作为考察节点,考察其叔父,如果也是红节点,则将其父亲和叔父改为黑节点,而将其祖父改为红节点,然后以其祖父为考察节点。如果其叔父是黑节点则做一旋转变换可以搞定,没有图不太好说明,你可以自己考虑一下,总之它的思想是把“多出来”的红色往上一层推去,确保下面层红黑性质,最后推到根以后,如果依然违反性质1,则可以直接把根由红改黑即可,就相当于把这“多出来”的红色推到树以外的节点去了。   删除节点时先要找到顶替的节点,如果删去的节点是黑色则破坏了性质2,也需要调整。调整的思想也同前面类似,把这个黑色赋予顶替节点,则顶替节点相当于有两重黑色,然后将它的两重黑色向上推,一直推到根,再从根推到外面去了。   平衡二叉树的调整算法几乎所有数据结构的书都有呀,根据破坏平衡性的加入点,将插入操作分为了四种,分别是LL、LR、RR、RL。每种引起不平衡的插入位置,均有相应的调整算法。   AVL树又称高度平衡的二叉搜索树,是1962年由两位俄罗斯的数学家G.M.Adel’son-Vel,sky和E.M.Landis提出 的.引入二叉树的目的是为了提高二叉树的搜索的效率,减少树的平均搜索长度.为此,就必须每向二叉树插入 一个结点时调整树的结构,使得二叉树搜索保持平衡,从而可能降低树的高度,减少的平均树的搜索长度.    AVL树的定义:    一棵AVL树满足以下的条件:    1>它的左子树和右子树都是AVL树    2>左子树和右子树的高度差不能超过1 从条件1可能看出是个递归定义,如GNU一样.    性质:    1>一棵n个结点的AVL树的其高度保持在0(log2(n)),不会超过3/2log2(n+1)    2>一棵n个结点的AVL树的平均搜索长度保持在0(log2(n)).    3>一棵n个结点的AVL树删除一个结点做平衡化旋转所需要的时间为0(log2(n)).# 红黑树是一种很有意思的平衡检索树。它的统计性能要好于平衡二叉树(有些书籍根据作者姓名,Adelson- Velskii和Landis,将其称为AVL-树),因此,红黑树在很多地方都有应用。在C++ STL中,很多部分(目前包括 set, multiset, map, multimap)应用了红黑树的变体(SGI STL中的红黑树有一些变化,这些修改提供了更好的性能,以及对set操作的支持)。  #   # 红黑树的定义如下:  #   #   # 满足下列条件的二叉搜索树是红黑树  #   #     * 每个结点要么是“红色”,要么是“黑色”(后面将说明)  #     * 所有的叶结点都是空结点,并且是“黑色”的  #     * 如果一个结点是“红色”的,那么它的两个子结点都是“黑色”的  #     * (注:也就是說,如果結點是黑色的,那么它的子節點可以是紅色或者是黑色的)。  #     * 结点到其子孙结点的每条简单路径都包含相同数目的“黑色”结点  #     * 根结点永远是“黑色”的     AVL 树是高度平衡的,频繁的插入和删除,会引起频繁的reblance,导致效率下降红黑树不是高度平衡的,算是一种折中,插入最多两次旋转,删除最多三次旋转

2024最新激活全家桶教程,稳定运行到2099年,请移步至置顶文章:https://sigusoft.com/99576.html

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请联系我们举报,一经查实,本站将立刻删除。 文章由激活谷谷主-小谷整理,转载请注明出处:https://sigusoft.com/51180.html

(0)
上一篇 2024年 9月 3日
下一篇 2024年 9月 3日

相关推荐

关注微信