• 中序不变 旋转结束后二叉树的中序始终不变, A<P<B<Q<C
  

二、简介

AVL 树（Adelson-Velsky and Landis Tree）得名于它的发明者 G. M. Adelson-Velsky 和 Evgenii Landis，他们在 1962 年的论文《An algorithm for the organization of information》中公开了这一数据结构。其实 AVL 就是在 BST 的基础上增加了一个平衡(Balance)的属性, 为的是稳固算法复杂度到 O(logn), BST 算法复杂度受到树结构的影响会游离于 O(logn)~O(n) 之间, 而加入了平衡属性之后则会降低到恒定为 O(logn)

三、基本特征

• 首先是 BST 的一种( BST 有的它都有)

• 是平衡二叉树(根节点的平衡因子绝对值不大于 1)

• 左右子树也是平衡二叉树

四、算法描述

插入, 删除之后是否需要平衡这个树? 如何平衡?

高度

为了判断一个树是否平衡? 引入了高度这个概念, 记录从树的最后一层到当前层数的距离

所以我们的节点(Node)结构定义如下

public static class Node {private int data;private int height;private Node left;private Node right;}

旋转

为了解决树的平衡问题引入了树的旋转

A, B, C, D 代表 子节点, 子树 或者 null

• 左左 左节点的左节点/子树导致的不平衡, 需要右旋
  

private Node rotateRight(Node root) {

Node t = root.left;root.left = t.right;t.right = root;

root.height = Math.max(height(root.left), height(root.right)) + 1;t.height = Math.max(height(t.left), height(t.right)) + 1;return t;}

右右 右节点的右节点/子树导致的不平衡, 需要左旋

private Node rotateLeft(Node root) {

Node t = root.right;root.right = t.left;t.left = root;

root.height = Math.max(height(root.left), height(root.right)) + 1;t.height = Math.max(height(t.left), height(t.right)) + 1;return t;}

左右 左节点的右节点/子树导致的不平衡, 需要左旋, 右旋

private Node rotateLeftRight(Node root) {root.left = rotateLeft(root.left);return rotateRight(root);}

右左 右节点的左节点/子树导致的不平衡, 需要右旋, 左旋

private Node rotateRightLeft(Node root) {root.right = rotateRight(root.right);return rotateLeft(root);}

查找

和 BST 写法一致

• 先查找根节点,

• < 根, 则找左子树;

• > 根, 则找右子树;

• = 根, 则找到返回;

public Node search(int num) {return doSearch(root, num);}

private Node doSearch(Node root, int num) {if (root == null) {return null;}

if (root.data == num) {return root;} else if (root.data > num) {return doSearch(root.left, num);} else if (root.data < num) {return doSearch(root.right, num);}return null;}

算法时间复杂度 对于 n 个节点的树 f(n) = 需要查找的次数 = 二叉树的层数 ~= O(logn)

插入

• 比对根节点, 小于就往左节点比对, 大于就往右节点比对

• 直到需要比对的节点为空, 而这个空就是你需要插入的位置

• 判断树是否平衡, 否, 则需要判断旋转类型并进行旋转变换

public void insert(int num) {root = doInsert(root, num);}

private Node doInsert(Node parent, int num) {if (parent == null) {parent = new Node(num);} else if (num > paren

《Android学习笔记总结+最新移动架构视频+大厂安卓面试真题+项目实战源码讲义》
浏览器打开：qq.cn.hn/FTe 免费领取

t.data) {parent.right = doInsert(parent.right, num);

// 判断树是否失衡 if (height(parent.right) - height(parent.left) >= 2) {// '右右'if (num > parent.right.data) {parent = rotateLeft(parent);}// '右左'else {parent = rotateRightLeft(parent);}}

} else if (num < parent.data) {parent.left = doInsert(parent.left, num);

// 判断树是否失衡 if (height(parent.left) - height(parent.right) >= 2) {// '左左'if (num < parent.left.data) {parent = rotateRight(parent);}// '左右'else {parent = rotateLeftRight(parent);}}}

// 重新计算旋转之后的高度 parent.height = Math.max(height(parent.left), height(parent.right)) + 1;

return parent;}

算法时间复杂度: f(n) = 查找插入点的比对次数logn + 一次旋转(单旋或者双旋) + 判断是否平衡 ~= O(logn)

旋转的时间复杂度 O(1) 最多需要单旋或者双旋, 另外, 判断是否平衡的时间复杂度也是 O(1) ( 主要得益于 Node 使用了 height 记录高度, 典型的空间换时间), 这样总得算法复杂度还是 比对的次数

删除

• 先查找到目标节点

• 若: 目标左子树为空, 则, 用目标右子树根节点替换目标

• 若: 目标右子树为空, 则, 用目标左子树根节点替换目标

• 若: 都不为空, 则, 选取左子树值最大节点或者右子树最小节点替换目标, 并, 递归删除替换目标的节点

• 判断树是否平衡, 否, 则需要判断旋转类型并进行旋转变换

public void remove(int num) {root = doRemove(root, num);}

private Node doRemove(Node parent, int num) {

if (parent == null) {return null;}

if (num > parent.data) {parent.right = doRemove(parent.right, num);

// 判断树是否平衡 if (height(parent.left) - height(parent.right) >= 2) {Node t = parent.right;// 右左if (t == null || height(t.right) < height(t.left)) {parent = rotateRightLeft(parent);}// 右右else {parent = rotateLeft(parent);}}