您当前的位置:网站首页>常见问题>平衡二叉树和二叉排序树的关系 找常见问题就上ki4.cc (>^ω^<),平衡二叉排序树,二叉排序树

平衡二叉树和二叉排序树的关系 找常见问题就上ki4.cc (>^ω^<),平衡二叉排序树,二叉排序树

2020年07月03日 投稿作者: 围观人数:21

幻灯片的各种视图快速切换方法是什么 找常见问题就上ki4.cc (>^ω^<)

幻灯片的各种视图快速切换方法是:单击水平滚动条左边的【视图控制】按钮。幻灯片共有四种视图模式,分别是:1、普通视图模式;2、浏览视图模式;3、备注页视图模式;4、阅读视图模式。

平衡二叉树和二叉排序树并没有直接的关系,但是二叉排序树的查找效率与二叉树的形态有关,所有当我们希望二叉排序树的形态是均匀的时候,这样的二叉树就被称为平衡二叉树。

1. 二叉排序树

二叉排序树(Binary Sort Tree),又称二叉查找树(Binary Search Tree),亦称二叉搜索树

  • 二叉排序树定义:

二叉排序树或者是一棵空树,或者是具有下列性质的二叉树:

  1. 若左子树不空,则左子树上所有节点的值均小于它的根节点的值;
  2. 若右子树不空,则右子树上所有节点的值均大于它的根节点的值;
  3. 左、右子树也分别为二叉排序树。

如图下图所示就是一棵二叉排序树:

对二叉排序树进行中序遍历,便可得到一个按关键字排序的序列,如对上图进行一次中序遍历可得到一个有序序列:10,42,45,55,58,63,67,70,83,90,98

  • 二叉排序树的查找分析

就查找的平均时间性能而言,二叉排序树上的查找与折半查找类似,但就维护表的有序性而言,二叉排序树更高效,因为它无需移动节点,只需修改指针即可完成二叉排序树的插入和删除操作。

二叉排序树查找在在最坏的情况下,需要的查找时间取决于树的深度

  1. 当二叉排序树接近于满二叉树时,其深度为 l o g 2 n log_2n log2n ,因此最坏情况下的查找时间为O( l o g 2 n log_2n log2n),与折半查找是同数量级的。
  2. 当二叉树如下图所示形成单枝树时,其深度为n,最坏情况下查找时间为O(n),与顺序查找属于同一数量级。

    所以为了保证二叉排序树查找有较高的查找速度,希望该二叉树接近于满二叉树,或者二叉树的每一个节点的左、右子树深度尽量相等

2. 平衡二叉树

通过上面的分析可知,二叉排序树的查找效率与二叉树的形态有关,我们希望二叉排序树的形态是均匀的,这样的二叉树称为平衡二叉树。

基数排序有什么用 找常见问题就上ki4.cc (>^ω^<)

基数排序属于“分配式排序”,是透过键值的部份资讯,将要排序的元素分配至某些“桶”中,以达到排序的作用,基数排序适合用于对时间、字符串等这些整体权值未知的数据进行排序。

  • 平衡二叉树定义
    平衡二叉树(Balanced Binary Tree),它是一棵空树,或者是具有以下性质:
  1. 它的左右两个子树的深度差的绝对值不超过1;
  2. 它的左右两个子树也分别是平衡二叉树。

将二叉树节点的左子树的深度减去它的右子树的深度称为平衡因子BF,则平衡二叉树上所有节点的平衡因子只可能是-1、0和1,如下图左边的为平衡二叉树,右边的为非平衡二叉树。

因为平衡二叉树上任何节点的左、右子树的深度之差都不会超过1,可以证明它的深度和n个节点的完全二叉树的深度 ⌊ l o g 2 n ⌋ \lfloor log_2n \rfloor log2n+1是同数量级的。因此,它的平均查找次数也是和 ⌊ l o g 2 n ⌋ \lfloor log_2n \rfloor log2n+1同数量级的。

要构造一棵平衡二叉树,Georgii M. Adelson-Velskii 和 Evgenii M. Landis 提出了一种动态保持二叉平衡树的方法,其基本思想是:在构造二叉排序树的时候,每当插入一个节点时,先检查是否因插入节点而破坏了树的平衡性,如果是,则找出其中最小不平衡子树,在保持排序树的前提下,调整最小不平衡子树中各节点之间的连接关系,以达到新的平衡,所以这样的平衡二叉树简称AVL树。其中最小平衡子树是指:离插入节点最近,且平衡因子绝对值大于1的节点作为根节点的子树

  • 调整最小不平衡子树一般有四种情况:
  1. 单向右旋(LL型): 插入位置为左子树的左子树,以左子树为轴心,进行单次向右旋转,如下图所示。节点旁边的数字为该节点的平衡因子,I节点为当前插入节点(如果I节点处于正中,则表示I节点既可以是左孩子也可以是右孩子。

注意LL型,以中间节点为轴心进行旋转。为什么这里I为BL左孩子不能将B-BL-I作为LL型,是因为A节点才是离I节点最近的平衡因子绝对值>1的子树,其余节点的平衡因子绝对值都没有超过1;同理当I为BL右孩子,也不能将B-BL-I作为LR型

2. 单向左旋(RR型): 插入位置为右子树的右子树,右子树为轴心,进行单次向左旋转

注意RR型,以中间节点为轴心进行旋转。这里I为左右子树并不影响其实RR型,原理同上。

3. 双向旋转先左后右(LR型):插入位置为左子树的右子树,要进行两次旋转,先向左旋转,再向右旋转。

插入节点为左孩子:注意为什么不能B-C-I作为子树将其定为RL型,原理同RR型中的解释,对于LR型,,是以R端或者L靠近插入节点端作为旋转轴心(如下图相当于先旋转以B为根的子树后,成为了LL型,再旋转以A为根的子树)。

插入节点为右孩子:

4. 双向旋转先右后左(RL型):插入位置为右子树的左子树,进行两次调整,先右旋转再左旋转;处理情况与LR类似。

插入节点为左孩子:

插入节点为右孩子:

经过上面的我们可以发现,平衡因子与类型有很大的关系,需要以离插入节点最近且平衡因子绝对值>1的节点作为根节点的子树进行判定是哪种类型

  • 练习

如下图所示,先插入节点2后,成为LL型,然后整体右旋处理后平衡。

再依次插入8和6之后,节点5的平衡因子绝对值>1,成为RL型,所以先以5为根节点,将其子树8-6右旋(成为RR型),然后将5为根节点的整棵树再左旋。

继续插入节点9后,节点4的平衡因子>1,成为RR型,所以以4为根节点,将整体左旋。

以上就是平衡二叉树和二叉排序树的关系的详细内容,更多请关注ki4导航其它相关文章!

基础排序法有哪些 找常见问题就上ki4.cc (>^ω^<)

基础排序法有:1、选择排序,分为“简单选择排序”和“堆排序”;2、插入排序,分为“简单插入排序”和“希尔排序”;3、交换排序,分为“冒泡排序”和“快速排序”;4、​归并排序;5、基数排序。

标签

版权说明
免责声明:本文文章内容由ki4导航网发布,但不代表本站的观点和立场,具体内容可自行甄别.