1:AVL 树简介
二叉搜索树在一般情况下其搜索的时间复杂度为 O(logn), 但某些特殊情况下会退化为链表, 导致树的高度变大且搜索的时间复杂度变为 O(n), 发挥不出树这种数据结构的优势, 因此平衡二叉树便应运而生, 通过保证树的高度来保证查询的时间复杂度为 O(logn), 想想人类实在是太聪明了!
2: 构造 AVL 树
在构造一棵 AVL 树的时候如何保持平衡呢? 其手段便是通过各种旋转变换来调整以此保证整棵树的高度, 调整的原则是左右子树的高度不能大于 1 的绝对值 (平衡因子) 先来介绍下旋转的方法吧.
2.1:LL 型
当插入元素后构成 LL 型, 如下图所示, 则以 2 为支, 高右转, 把 3 右旋下来保证平衡.
2.2:RR 型
当插入元素后构成 RR 型, 如下图所示, 则以 2 为支, 高左转, 把 1 左旋转下来保证平衡.
2.3:LR 型
当插入元素后构成 LR 型, 如下图所示, 先 2,3 整体左旋, 在根据 LL 型进行右旋转来保证平衡.
2.4:RL 型
当插入元素后构成 RL 型, 如下图所示, 先将 5 右转, 在与 6 进行交换, 在根据 RR 型进行旋转来保证平衡.
2.5: 其他情况
当因为插入一个元素而导致出现两个不平衡点, 应该调整距离插入节点最近的不平衡点
2.6: 自测题
测试题: 以关键字序列 {16,3,7,11,9,26,18,14,15} 构造一颗 AVL 树
2.7:java 实现 AVL 的构造
- package AVL;
- /**
- * @author admin
- * @version 1.0.0
- * @ClassName AVLTree.java
- * @Description TODO
- * @createTime 2020 年 03 月 30 日 18:28:00
- */
- public class AVLTree {
- /**
- * 获取左右节点的高度差, 即平衡因子
- * @param root
- * @return
- */
- public int getBalance(Node root) {
- return root==null?0:getHeight(root.left)-getHeight(root.right);
- }
- /**
- * 获取节点的高度
- * @param root
- * @return
- */
- public int getHeight(Node root) {
- return root == null ? 0 : root.height;
- }
- /**
- * 更新节点的高度
- * @param root
- * @return
- */
- private int updateHeight(Node root) {
- if (root == null)
- return 0;
- return Math.max(updateHeight(root.left), updateHeight(root.right)) + 1;
- }
- /**
- * LL 型, 右旋操作
- *
- * @param root
- * @return
- */
- public Node rightRotate(Node root) {
- Node node = root.left;
- root.left = node.right;
- node.right = root;
- root.height = updateHeight(root);
- node.height = updateHeight(node);
- return node;
- }
- /**
- * RR 型, 左旋操作
- * @param root
- * @return
- */
- public Node leftRotate(Node root) {
- Node node = root.right;
- root.right = node.left;
- node.left = root;
- root.height = updateHeight(root);
- node.height = updateHeight(node);
- return node;
- }
- public Node insert(Node node, int data) {
- // 当节点为空, 直接插入
- if (node == null) {
- return (new Node(data));
- }
- // 当插入元素 < node.data, 往 node 的左子树进行插入;>node.data, 往 node 的右子树插入
- if (node.data> data) {
- node.left = insert(node.left, data);
- } else {
- node.right = insert(node.right, data);
- }
- // 更新节点的高度
- node.height = updateHeight(node);
- // 获取平衡因子(左子树高度 - 右子树高度)
- int balDiff = getBalance(node);
- // 右旋
- if (balDiff> 1 && data <node.left.data) {
- return rightRotate(node);
- }
- // 左旋
- if (balDiff < -1 && data> node.right.data) {
- return leftRotate(node);
- }
- // 先左旋在右旋
- if (balDiff> 1 && data> node.left.data) {
- node.left = leftRotate(node.left);
- return rightRotate(node);
- }
- // 先右旋在左旋
- if (balDiff < -1 && data < node.right.data) {
- node.right = rightRotate(node.right);
- return leftRotate(node);
- }
- return node;
- }
- }
- class Node {
- int data;
- Node left;
- Node right;
- int height;
- public Node(Integer data) {
- this.data = data;
- height = 1;
- }
- }
3:AVL 树的删除
3.1: 删除叶子节点
3.2: 删除只拥有左子树或右子树的节点
3.3: 删除既拥有左子树又有右子树的节点
3.4: 自测题
将上一道自测题的图依次删除 16,15,11 节点, 画出最后的结果
参考链接
数据可视化网站: https://visualgo.net/zh
哔哩哔哩讲 AVL: https://www.bilibili.com/video/BV1xE411h7dd
来源: https://www.cnblogs.com/zengcongcong/p/12770809.html