侧边栏壁纸
  • 累计撰写 247 篇文章
  • 累计创建 16 个标签
  • 累计收到 0 条评论

目 录CONTENT

文章目录

平衡二叉树(AVL)的定义和实现原理

kaixindeken
2021-04-22 / 0 评论 / 0 点赞 / 96 阅读 / 1,750 字

引子

理想情况下,二叉排序树的插入、删除、查找时间复杂度都是 O(logn),非常高效,而且它是一种动态的数据结构,插入删除性能合查找一样好,不像之前提到的二分查找,虽然查找性能也是 O(logn),但是需要先对线性表进行排序,二排序的最好时间复杂度也是 O(nlogn),所以二分查找不适合动态结构的排序。

但是我们也提到如果二叉排序树构造的不好的话就会退化成斜树:

1.jpeg

此时按照之前的实现算法性能退化成了 O(n),所以如何构造二叉排序树很重要,我们的理想情况是满二叉树和完全二叉树,它们的性能都是 O(logn),所以我们在构造二叉排序树的时候要尽可能像它们靠近,才能得到最佳的操作性能,由此引出了我们今天的话题——平衡二叉树。

什么是平衡二叉树

平衡二叉树的英文名是 Self-Balancing Binary Search Tree 或者 Height-Balancing Binary Search Tree,译作自平衡的二叉查找树,或者高度平衡的二叉查找树,二叉查找树和二叉排序树是一个意思,只是叫法不同,简称平衡二叉树,也叫 AVL 树(平衡二叉树作者的名字首字母),所以平衡二叉树首先是二叉排序树,并且这个二叉排序树是左右高度平衡的,这么讲有点抽象,具体来说,平衡二叉树要求每个节点的左子树和右子树的高度差至多等于 1,这个高度(深度)差的值叫做平衡因子 BF,也就是说 BF 的值不能大于1,否则就不是平衡二叉树。

我们简单看几个例子:

1.jpeg

  • 图1不满足平衡二叉树的定义,只是普通的二叉排序树(引用了大话数据结构一书的原图,这里需要勘误);
  • 图2所示二叉树不是二叉排序树,所有不是平衡二叉树;
  • 图3不满足平衡因子小于等于1的要求,对58这个节点来说,平衡因子BF的值是3,因而不是平衡二叉树;
  • 图4满足平衡二叉树的定义,是平衡二叉树;
    我们之所以这么约束平衡二叉树,是为了保证它能够始终做到插入、删除、查找的时间复杂度是 O(logn)。

了解了什么是平衡二叉树,下面我们来看看它的实现原理。

平衡二叉树的实现原理

平衡二叉树的基本实现思路,是在构建二叉排序树的时候,每插入一个节点,都要检查这个节点的插入是否破坏了原有的平衡性,如果是的话,则找出最小不平衡子树,在保证整体二叉排序树的前提下,通过左旋或者右旋的方式将其调整为平衡子树。从而动态维护这棵平衡二叉树。

这里面有几个概念需要解释一下:

1、最小不平衡子树

距离插入节点最近的,且平衡因子绝对值大于 1 的节点为根的子树,叫做最小不平衡子树:

1.jpeg

比如上图中以存储元素 58 的节点为根的子树叫做最小不平衡子树。

2、左旋/右旋

所谓左旋和右旋指的是最小不平衡子树旋转的方向。

如果平衡因子小于 -1,即右子树高度值比较大,则需要左旋:

1.jpeg

反之,如果平衡因子大于1,即左子树高度值比较大,则需要右旋:

1.jpeg

当然为了方便你理解原理,我们这里给出的都是最简化的情况,实际处理过程中比这个更复杂。

0

评论区