AVL平衡二叉树

概述

AVL，是一种自平衡二叉树。
对于二叉树来所，如果一直插入比前一个数小的数，那么二叉树可能会退化成一个链表。因此，为了保证查询的效率，我们需要时刻保持二叉树的平衡。
对于AVL数来说，平衡的条件是左右子树的深度不会超过一。

实现

节点

我这里将叶子节点的高度设为1

//二叉树的默认高度为1
    private static class AVLNode {
        int height = 1;
        int key;
        Object value;
        AVLNode left;
        AVLNode right;

        public AVLNode(int key, Object value, AVLNode left, AVLNode right) {
            this.key = key;
            this.value = value;
            this.left = left;
            this.right = right;
        }

        public AVLNode(int key, Object value) {
            this.key = key;
            this.value = value;
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

返回、更新高度

//返回节点的高度
    private int height(AVLNode node) {
        return node == null ? 0 : node.height;
    }

    //更新节点的高度
    private void updateHeight(AVLNode node) {
        node.height = Integer.max(height(node.left), height(node.right)) + 1;
    }
1
2
3
4
5
6
7
8
9

判断是否失衡

//定义一个平衡因子，用于判断二叉树是否失衡
    private int bf(AVLNode node) {
        return height(node.left) - height(node.right);
    }
1
2
3
4

处理失衡

失衡有四种情况

1.LL

失衡节点的左边更高，失衡节点的左孩子更高或等高
对于这种情况我们只需要对失衡节点进行右旋就可以
右旋就是将失衡节点当作它左孩子的右节点，之后将失衡节点左孩子原先的右孩子挂在失衡节点的左孩子

//右旋
    private AVLNode rightRotate(AVLNode red) {
        AVLNode yellow = red.left;
        AVLNode green = yellow.right;
        yellow.right = red;
        red.left = green;
        return yellow;
    }
1
2
3
4
5
6
7
8

2.LR

失衡节点的左边更高，失衡节点的右孩子更高
对于这种情况，我们只需要对是很节点的左孩子进行一个左旋，就可以转成LL的情况，之后进行右旋就可以

//左右旋
    private AVLNode leftRightRotate(AVLNode root) {
        root.left = leftRotate(root.left);
        return rightRotate(root);
    }
1
2
3
4
5

3.RR

失衡节点的右边更高，失衡节点的右孩子更高或等高
对于这种情况我们只需要对失衡节点进行左旋就可以
左旋就是将失衡节点当作它右孩子的左节点，之后将失衡节点右孩子原先的左孩子挂在失衡节点的右孩子

//左旋
    private AVLNode leftRotate(AVLNode red) {
        AVLNode yellow = red.right;
        AVLNode green = yellow.left;
        yellow.left = red;
        red.right = green;
        return yellow;
    }
1
2
3
4
5
6
7
8

4.RL

失衡节点的右边更高，失衡节点的左孩子更高
对于这种情况，我们只需要对是很节点的右孩子进行一个右旋，就可以转成RR的情况，之后进行左旋就可以

//右左旋
    private AVLNode rightLeftRotate(AVLNode root) {
        root.right = rightRotate(root.right);
        return leftRotate(root);
    }
1
2
3
4
5

调整平衡

//调整平衡
    private AVLNode balance(AVLNode node) {
        if (node == null) {
            return null;
        }
        int bf = bf(node);
        if (bf > 1 && bf(node.left) >= 0) {
            return rightRotate(node);
        } else if (bf > 1 && bf(node.left) < 0) {
            return leftRightRotate(node);
        } else if (bf < -1 && bf(node.right) <= 0) {
            return leftRotate(node);
        } else if (bf < -1 && bf(node.right) > 0) {
            return rightLeftRotate(node);
        }
        return node;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

新增节点

//新增节点
    public void put(int key, int value) {
        root = doPut(root, key, value);
    }

    private AVLNode doPut(AVLNode node, int key, Object value) {
        if (node == null) {
            return new AVLNode(key, value);
        }
        if (key == node.key) {
            node.value = value;
        }
        if (key < node.key) {
            node.left = doPut(node.left, key, value);
        } else {
            node.right = doPut(node.right, key, value);
        }
        //利用递归，可以一步一步将高度更新回根节点
        updateHeight(node);
        return balance(node);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

删除节点

private AVLNode doRemove(AVLNode node, int key) {
        if (node == null) {
            return null;
        }
        if (key < node.key) {
            node = doRemove(node.left, key);
        } else if (key > node.key) {
            node = doRemove(node.right, key);
        } else {
            if (node.left == null) {
                node = node.right;
            } else if (node.right == null) {
                node = node.left;
            } else {
                AVLNode s = node.right;
                while (s.left != null) {
                    s = s.left;
                }
                //得到删除后驱节点的子树
                s.right = doRemove(node.right, s.key);
                s.left = node.left;
                node = s;
            }
        }
        updateHeight(node);
        return balance(node);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27