平衡二叉树

平衡二叉树

基本介绍:

1. AVL树的名字来源于它们的发明作者G.M.Adelson-Velsky和E.M.Landis

   • AVL树是最先发明的自平衡二分查找树, 简称平衡二叉树

     • 自平衡二叉树: Self-Balancing Binary Search Tree

2. 平衡二叉树也叫做平衡二叉搜索树(Self-Balancing Binary Seaerch Tree), 又称之为AVL树, 使用平衡二叉树可以保证查询效率较高

   • 如果单纯的时候普通的二分搜索树时针对有序序列的建树就会导致严重的右倾或者是左倾, 就会导致创建的二分搜索树成为一个类似链表的结构, 效率将会大大的降低
     • 如果是类似链表的结构, 我们查询的时间复杂度就会是O(n), 如果是平衡的二叉树结果, 查询的效率是O(log n)

3. AVL树是一棵空树或者它的左右两个子树的高度差不超过1, 并且左右两个子树也都要是一颗平衡二叉树

平衡二叉树的常用实现方法有: 红黑树, AVL, 替罪羊树, Treap, 伸展树等 (这里的AVL指的是AVL算法)

• Treap是树堆: 树是二叉搜索树, 堆是二叉堆(大顶堆和小顶堆都可以)

• 替罪羊树是一种依靠重构操作维持平衡的重量平衡树, 也是一种自平衡二叉树

• 伸展树(Splay Tree): 伸展树并不需要高度(平衡因子)等平衡(也就是伸展树是一种特殊的自平衡二叉树, 伸展树的结构可能不是平衡的, 但是各种操作的均摊时间复杂度却都是O(log n), 也就是达到了平衡二叉树的各种操作的时间复杂度)

  • 这里的伸展是一种特殊的旋转方式

• 红黑树: 红黑树并不是一种严格的自平衡二叉树(红黑树中结点的左子树和右子树的高度差可能大于1, 红黑树就是通过牺牲严格的平衡, 换取插入和删除操作时进行的旋转操作较少)

  • 红黑树的整体性能优于AVL树
  • 红黑树的红黑规则让我们可以在最坏时间复杂度为O(log n)的时间内完成查找操作

AVL树的查找, 插入, 删除操作在平均和最坏情况下都是O(log n), 这得益于它时刻维护着二叉树的平衡

• 因此: AVL如何维护二叉树的平衡是我们学习的重点: 这里我们要掌握"左旋"和"右旋"算法, 我们的双旋转也是基于左旋和右旋实现的, 所以其实我们要学习的只有左旋和右旋算法

AVL树相关概念:

1. 平衡因子:

   • 将二叉树上结点的左子树高度减去右子树的高度的值称之为该节点的平衡因子

     • 平衡因子 : 简称:BF, Balance Factor

   • 对于平衡二叉树中所有结点的BF的取值范围为[-1, 1]

2. 最小不平衡子树:

   • 因为我们一般都是插入和删除的时候才会导致树的不平衡, 所以最小不平衡子树就是指:距离插入或者删除结点最近的, 且平衡因子的绝对值大于1的结点为根节点的子树
     • 我们后面会讲到的LL型, RR型, RL型, 和LR型, 其实都是指的不平衡子树的类型, 也就是LL型不平衡子树, RR型不平衡子树, RL型不平衡子树, LR型不平衡子树

我们为什么要提出AVL树(AVL平衡二叉树):

通过一个案例来理解: 给你一个数列{1, 2, 3, 4, 5, 6}, 要求创建一颗二叉排序树(BST), 并且分析问题所在:

如果是使用上述数列构建一颗二叉排序树, 那么得到的二叉排序树如下:

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-biMoqa3q-1669121534504)(E:\非凡英才\数据结构(java)]\数据结构图解\有序序列构建的不平衡BST(二分搜索树).png)

上述构建的BST(二分搜索树)的问题分析:

1. 左子树全部为空, 从形式上看起来更加像是一个单链表
2. 查询速度明显会变慢, 不能发挥BST的查询速度快的优势, 如果是一个平衡的BST, 那么查询的速度应该是在O(log n)的时间复杂度上, 而此时显然是一个不平衡的BST, 此时查询的速度是O(n), 所以速度直接是降低了一个级别的