二叉搜索树之AVL树

AVL树的概念

二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当于在顺

序表中搜索元素，效率低下。因此，两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年 发明了一种

解决上述问题的方法：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过

1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。

一棵AVL树或者是空树，或者是具有以下性质的二叉搜索树：

它的左右子树都是AVL树

左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)

平衡因子bf = 右子树高度 - 左子树高度

如果一棵二叉搜索树是高度平衡的，它就是AVL树。如果它有n个结点，其高度可保持在O(log_2 n)，搜索时间

复杂度O(log_2 n)。

AVL树的插入

AVL树节点在定义时维护一个平衡因子，具体节点定义如下：

static class TreeNode{public int val;public int bf;//平衡因子public TreeNode left;public TreeNode right;public TreeNode parent;public TreeNode(int val){this.val = val;}}

AVL树的插入过程可以分为两步：

1. 按照二叉搜索树的方式插入新节点

2. 调整节点的平衡因子

按照二叉搜索树的方式插入新节点：

    public boolean insert(int val){TreeNode node = new TreeNode(val);if (root == null){root = node;return true;}TreeNode parent = null;TreeNode cur = root;while (cur != null){if (cur.val < val){parent = cur;cur = cur.right;}else if (cur.val == val){return false;}else {parent = cur;cur = cur.left;}}if (parent.val < val){parent.right = node;}else {parent.left = node;}node.parent = parent;cur = node;}

调整节点的平衡因子

//平衡因子的修改while (parent != null){//先看cur是parent的左还是右  决定平衡因子是++还是--if (cur == parent.right){//如果是右树，那么右树高度增加 平衡因子++parent.bf++;}else {//如果是左树，那么左树高度增加 平衡因子--parent.bf--;}//检查当前的平衡因子 是不是绝对值 1  0  -1if (parent.bf == 0){//说明已经平衡了break;}else if (parent.bf == 1 || parent.bf == -1){//继续向上去修改平衡因子cur = parent;parent = cur.parent;}else {if (parent.bf == 2){//右树高-》需要降低右树的高度if (cur.bf == 1){//左单旋rotateLeft(parent);}else {//cur.bf == -1rotateRL(parent);}}else {//parent.bf == -2 左树高-》需要降低左树的高度if (cur.bf == -1){//右单旋rotateRight(parent);}else {//cur.bf == 1//左右双旋rotateLR(parent);}}//上述代码走完就已经平衡了break;}}

左单旋-插入位置在较高右子树的右侧：（parent.bf = 2, cur.bf = 1）

  //左单旋private void rotateLeft(TreeNode parent) {TreeNode subR = parent.right;TreeNode subRL= subR.left;parent.right = subRL;subR.left = parent;if (subRL != null){subRL.parent = parent;}TreeNode pParent = parent.parent;parent.parent = subR;if (parent == root){root = subR;root.parent = null;}else {if (pParent.left == parent){pParent.left = subR;}else {pParent.right = subR;}subR.parent = pParent;}subR.bf = 0;parent.bf = 0;}

右单旋-插入位置在较高左子树的左侧：（parent.bf = -2, cur.bf = -1）

//右单旋private void rotateRight(TreeNode parent) {TreeNode subL = parent.left;TreeNode subLR = subL.right;parent.left = subLR;subL.right = parent;if (subLR != null){subLR.parent = parent;}//必须先记录当前的父亲的父亲节点TreeNode pParent = parent.parent;parent.parent = subL;//检查当前节点是不是根节点if (parent == root){root = subL;root.parent = null;}else {//不是根节点，判断这颗子树是左子树还是右子树if (pParent.left == parent){pParent.left = subL;}else {pParent.right = subL;}subL.parent = pParent;}subL.bf = 0;parent.bf = 0;}

左右双旋-插入位置在较高左子树的右侧：（parent.bf = -2, cur.bf = 1）

  //左右双旋private void rotateLR(TreeNode parent) {TreeNode subL = parent.left;TreeNode subLR= subL.right;int bf = subLR.bf;rotateLeft(parent.left);rotateRight(parent);if (bf == -1){subL.bf = 0;subLR.bf = 0;parent.bf = 1;}else if (bf == 1){subL.bf = -1;subLR.bf = 0;parent.bf = 0;}}

右左双旋-插入位置在较高右子树的左侧：（parent.bf = 2, cur.bf = -1）

private void rotateRL(TreeNode parent) {TreeNode subR = parent.right;TreeNode subRL = subR.left;int bf = subRL.bf;rotateRight(parent.right);rotateLeft(parent);if (bf == 1){subR.bf = 0;subRL.bf = 0;parent.bf = -1;}else if (bf == -1){subR.bf = 1;subRL.bf = 0;parent.bf = 0;}}

AVL树插入操作的完整代码+验证代码

public class AVLTree {static class TreeNode{public int val;public int bf;//平衡因子public TreeNode left;public TreeNode right;public TreeNode parent;public TreeNode(int val){this.val = val;}}//根节点public TreeNode root;public boolean insert(int val){TreeNode node = new TreeNode(val);if (root == null){root = node;return true;}TreeNode parent = null;TreeNode cur = root;while (cur != null){if (cur.val < val){parent = cur;cur = cur.right;}else if (cur.val == val){return false;}else {parent = cur;cur = cur.left;}}if (parent.val < val){parent.right = node;}else {parent.left = node;}node.parent = parent;cur = node;//平衡因子的修改while (parent != null){//先看cur是parent的左还是右  决定平衡因子是++还是--if (cur == parent.right){//如果是右树，那么右树高度增加 平衡因子++parent.bf++;}else {//如果是左树，那么左树高度增加 平衡因子--parent.bf--;}//检查当前的平衡因子 是不是绝对值 1  0  -1if (parent.bf == 0){//说明已经平衡了break;}else if (parent.bf == 1 || parent.bf == -1){//继续向上去修改平衡因子cur = parent;parent = cur.parent;}else {if (parent.bf == 2){//右树高-》需要降低右树的高度if (cur.bf == 1){//左单旋rotateLeft(parent);}else {//cur.bf == -1rotateRL(parent);}}else {//parent.bf == -2 左树高-》需要降低左树的高度if (cur.bf == -1){//右单旋rotateRight(parent);}else {//cur.bf == 1//左右双旋rotateLR(parent);}}//上述代码走完就已经平衡了break;}}return true;}private void rotateRL(TreeNode parent) {TreeNode subR = parent.right;TreeNode subRL = subR.left;int bf = subRL.bf;rotateRight(parent.right);rotateLeft(parent);if (bf == 1){subR.bf = 0;subRL.bf = 0;parent.bf = -1;}else if (bf == -1){subR.bf = 1;subRL.bf = 0;parent.bf = 0;}}//左右双旋private void rotateLR(TreeNode parent) {TreeNode subL = parent.left;TreeNode subLR= subL.right;int bf = subLR.bf;rotateLeft(parent.left);rotateRight(parent);if (bf == -1){subL.bf = 0;subLR.bf = 0;parent.bf = 1;}else if (bf == 1){subL.bf = -1;subLR.bf = 0;parent.bf = 0;}}//左单旋private void rotateLeft(TreeNode parent) {TreeNode subR = parent.right;TreeNode subRL= subR.left;parent.right = subRL;subR.left = parent;if (subRL != null){subRL.parent = parent;}TreeNode pParent = parent.parent;parent.parent = subR;if (parent == root){root = subR;root.parent = null;}else {if (pParent.left == parent){pParent.left = subR;}else {pParent.right = subR;}subR.parent = pParent;}subR.bf = 0;parent.bf = 0;}//右单旋private void rotateRight(TreeNode parent) {TreeNode subL = parent.left;TreeNode subLR = subL.right;parent.left = subLR;subL.right = parent;if (subLR != null){subLR.parent = parent;}//必须先记录当前的父亲的父亲节点TreeNode pParent = parent.parent;parent.parent = subL;//检查当前节点是不是根节点if (parent == root){root = subL;root.parent = null;}else {//不是根节点，判断这颗子树是左子树还是右子树if (pParent.left == parent){pParent.left = subL;}else {pParent.right = subL;}subL.parent = pParent;}subL.bf = 0;parent.bf = 0;}//中序遍历public void inorder(TreeNode root){if (root == null)return;inorder(root.left);System.out.print(root.val + " ");inorder(root.right);}private int height(TreeNode root){if (root == null)return 0;int leftHeight = height(root.left);int rightHeight = height(root.right);return leftHeight > rightHeight ? leftHeight+1 : rightHeight+1;}public boolean isBalanced(TreeNode root){if (root == null)return true;int leftHeight = height(root.left);int rightHeight = height(root.right);if (rightHeight-leftHeight != root.bf){System.out.println("这个节点："+root.val + "有异常!");return false;}return Math.abs(leftHeight-rightHeight) <= 1&& isBalanced(root.left)&& isBalanced(root.right);}
}

AVL树的删除

因为AVL树也是二叉搜索树，可按照二叉搜索树的方式将节点删除，然后再更新平衡因子，只不过与删除不

同的是，删除节点后的平衡因子更新，最差情况下一直要调整到根节点的位置。

1、找到需要删除的节点

2、按照搜索树的删除规则删除节点--参考https://blog.csdn.net/crazy_xieyi/article/details/127627063

3、更新平衡因子，如果出现了不平衡，进行旋转。--单旋，双旋

AVL树的性能分析

AVL树是一棵绝对平衡的二叉搜索树，其要求每个节点的左右子树高度差的绝对值都不超过1，这样可以保证查询

时高效的时间复杂度，即 。但是如果要对AVL树做一些结构修改的操作，性能非常低下，比如：插入时要

维护其绝对平衡，旋转的次数比较多，更差的是在删除时，有可能一直要让旋转持续到根的位置。因此：如果需要

一种查询高效且有序的数据结构，而且数据的个数为静态的(即不会改变)，可以考虑AVL树，但一个结构经常修

改，就不太适合。