加入收藏 | 设为首页 | 会员中心 | 我要投稿 衡阳站长网 (https://www.0734zz.cn/)- 数据集成、设备管理、备份、数据加密、智能搜索!
当前位置: 首页 > 服务器 > 安全 > 正文

自己动手实现java数据结构(七) AVL树

发布时间:2021-04-01 19:18:56 所属栏目:安全 来源:网络整理
导读:1.AVL树介绍 前面我们已经介绍了二叉搜索树。普通的二叉搜索树在插入、删除数据时可能使得全树的数据分布不平衡,退化,导致二叉搜索树最关键的查询效率急剧降低。这也引出了平衡二叉搜索树的概念,平衡二叉搜索树在此前的基础上,通过一系列的等价变换使二
副标题[/!--empirenews.page--]

1.AVL树介绍

  前面我们已经介绍了二叉搜索树。普通的二叉搜索树在插入、删除数据时可能使得全树的数据分布不平衡,退化,导致二叉搜索树最关键的查询效率急剧降低。这也引出了平衡二叉搜索树的概念,平衡二叉搜索树在此前的基础上,通过一系列的等价变换使二叉搜索树得以始终处于"平衡"的状态,拥有稳定且高效的查询效率。
  AVL树是最早被计算机科学家发明的自平衡二叉搜索树,AVL树得名于它的发明者G. M.?Adelson-Velsky和E. M.?Landis,他们在1962年的论文《An algorithm for the organization of information》中发表了它。

  不同的平衡二叉搜索树对所谓"平衡"有不同的定义,AVL树认为当所有节点的左右子树高度之差不超过正负1时,全树是平衡的。

  在插入新节点和删除旧节点之后,AVL树会判断当前是否有节点失去平衡,并对失衡的节点进行相应的重平衡操作,恢复到AVL树定义的适度平衡状态。

2.AVL树重平衡原理

2.1 等价变换介绍

  二叉搜索树有一个重要的特性:所存储元素的中序遍历次序是有序的,这也是二叉搜索树能够使用二分法加速查找的基础。

  对于同一中序遍历次序,二叉搜索树的拓扑结构可以是多样的,在保持二叉搜索树中序遍历次序不变的情况下(等价),对其拓扑结构进行一系列变换(变换),被称为等价变换。

  等价变换是平衡二叉搜索树重平衡操作的理论基础。

?  

自己动手实现java数据结构(七) AVL树

2.2 等价变换方式

  等价变换的基本操作有两种:

    顺时针旋转(zig),可以形象的理解为x->y箭头方向下午两点变成了下午四点,也被称为右旋

    逆时针旋转(zag),可以形象的理解为y->x箭头方向上午十点变成了上午八点,也被称为左旋

  顺时针旋转和逆时针旋转的操作是互逆的,复杂等价变换操作可以看成是由这两种基本操作组合而成。

顺时针旋转:

  

自己动手实现java数据结构(七) AVL树

逆时针旋转:

  

自己动手实现java数据结构(七) AVL树

2.3 AVL树的失衡状态及重平衡

在了解如何恢复AVL树平衡状态之前,需要先理解几个关键点:

  1.无论是插入新节点还是删除老节点,最多只会导致插入/删除节点位置的上层的历代祖先节点失去平衡(数量大致为 logN),而不会导致全树节点都失去平衡,因此只需要判断其历代祖先节点的平衡状态,即可判断其是否破坏了AVL树的平衡状态

  2.当原先较高的子树中插入新节点时,可能会导致历代祖先节点失衡(部分祖先节点,而非全部)

  3.当原先较低的子树中删除老节点时,可能会导致历代祖先节点失衡(部分祖先节点,而非全部)

  针对AVL树的失衡节点进行重平衡时,主要关注失衡节点自身(N Node)、引起失衡方向的孩子节点(S Son)、引起失衡方向的孙子节点(GS GrandSon)及所属子树,对其进行等价变换操作,使之恢复平衡。

  我们从失衡节点出发,依据失衡节点和其引起失衡方向的孩子节点、其引起失衡方向的孙子节点的共同构成的拓扑结构,共以下四种形态:

  

自己动手实现java数据结构(七) AVL树

2.3.1 左左形

左左形 插入节点引起失衡及重平衡:

自己动手实现java数据结构(七) AVL树

左左形 删除节点引起失衡及重平衡:

自己动手实现java数据结构(七) AVL树

2.3.3 左右形

左右形 插入节点引起失衡及重平衡:

自己动手实现java数据结构(七) AVL树

左右形 删除节点引起失衡及重平衡:

自己动手实现java数据结构(七) AVL树

2.3.2 右右形

  右右形和左左形是镜像的拓扑结构,失衡场景和重平衡手段与"2.3.1 左左形"原理相同,限于篇幅,不再展开说明。

2.3.4 右左形

  右左形和左右形是镜像的拓扑结构,失衡场景和重平衡手段与"2.3.2 左右形"原理相同,限于篇幅,不再展开说明。

2.3.5 插入和删除操作重平衡的区别

  在示意图中,注意观察标识树高层次的横向细长的白色箭头。

  插入和删除操作会导致操作节点位置的历代祖先失去平衡,这需要从低到高依次检查平衡状态并进行重平衡处理。

  插入新节点导致失衡并重平衡的过程中,当前失衡节点(最低的失衡祖先节点)所在子树的高度在重平衡操作完成后和未插入新节点之前是一样的。因而当最低位置的祖先节点恢复了平衡后,更高的祖先节点也将自动的恢复平衡(因为插入前是平衡的,而插入后失衡子树的高度在重平衡后也和原先一致了)。

  删除老节点导致失衡并重平衡的过程中,当前失衡节点(最低的失衡祖先节点)所在子树的高度在重平衡操作完成后和未插入新节点之前可能是不一样的(所在子树高度降低1)。因而当最低位置的祖先节点恢复平衡后,可能会导致更高的祖先节点进而失去平衡,这种现象会向上逐层传播。最坏的极端情况下,每当恢复一个较低的祖先节点平衡时,都会导致更高一层祖先节点失衡,直至根节点完成重平衡,这样的重平衡操作最多需要执行(logN)次。

2.4 3+4重构

  前面介绍了针对不同失衡状态拓扑结构进行重平衡的方法,都是使用一次或多次旋转的方式完成的。

(编辑:衡阳站长网)

【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容!

热点阅读