数据结构-AVL树_在空avl树中依次插入8 12 35 27 19 64,树中度为1的节点个数为

背景

二分搜索树BST在极端情况下，会退化成链表结构。 比如1，2，3，4，5

因此衍生出维持平衡二叉树的研究，比如AVL树

什么是平衡二叉树呢？
一颗满的二叉树一定是平衡二叉树：

满二叉树：除了叶子节点之外，其他节点都有左右两个节点。
完全二叉树是平衡二叉树
线段树也是平衡二叉树

2 AVL树

AVL树的定义：
对于任意一个节点来说，左子树与右子树的高度差不能超过1. 同时AVL树也是二分搜索树，所以满足二分搜索树的性质，即左子树小于父节点，右子树大于父节点，同时其子树又是二分搜索树，比如以下这个例子：

标注节点的高度值，之后可以计算出平衡因子
平衡因子：针对每个节点的左右子数的高度差
以下例子展示说明下节点高度的标注以及平衡因子：红色字体即为平衡因子

2.1 节点

首先我们定义节点：里面增加一个height用于计算每个节点的高度。

public class Node<K extends Comparable<K>, V> {

    public K key;
    public V value;
    public Node<K,V> left, right;
    public int height;

    public Node(K key, V value){
        this.key = key;
        this.value = value;
        left = null;
        right = null;
        this.height = 1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

2.2 平衡因子的计算

其次说明一下平衡因子的计算以及判断是否是二叉搜索树以及平衡树，这样后面才可以针对是否平衡进行调整。
平衡因子的计算：

// 计算节点的平衡因子
    private int getBalanceFactor(Node<K,V> node) {
        if (node == null) {
            return 0;
        }
        else {
            return getHeight(node.left) - getHeight(node.right);
        }
    }
1
2
3
4
5
6
7
8
9

2.3 树的一些判断（是否是二分搜索树，是否平衡）

判断该树是否是二叉搜索树：

private boolean isBST(Node<K,V> node) {

        List<K> keys = new ArrayList<>();
        inOrder(node, keys);
        for (int i = 1; i <= keys.size() - 1; i++) {
            if (keys.get(i-1).compareTo(keys.get(i)) > 0) {
                return false;
            }
        }
        return true;
    }
    private boolean isBST() {

        return isBST(this.root);
    }

    private void inOrder(Node<K,V> node, List<K> keys) {
        if (node == null) {
            return;
        }
        inOrder(node.left, keys);
        keys.add(node.key);
        inOrder(node.right, keys);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

判断该树是否平衡：

private boolean isBalanced() {
        return isBalanced(root);
    }
    private boolean isBalanced(Node<K,V> node) {

        if (node == null) {
            return true;
        }
        int balanceFactor = getBalanceFactor(node);
        if (Math.abs(balanceFactor) > 1) {
            return false;
        }

        return isBalanced(node.left) && isBalanced(node.right);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

2.4 平衡树的旋转（LL,RR,LR,RL)

什么时间平衡性会被破坏？
当我们插入或者删除一个节点时，其父亲节点或者祖先节点有可能会被破坏掉。新插入一个节点需要更新其父亲节点以及祖先节点的高度值，这时候可能就会导致高度差超过1，就会失衡。沿着插入的节点向上回溯进而维持平衡。 针对删除一个节点也是一样，会导致父亲节点以及祖先节点的高度值发生变化，可能破坏原本的平衡，进而需要针对其父节点或者祖先节点进行平衡维护。

2.4.1 LL(插入的元素在不平衡节点的左侧的左侧）

先举个例子，在初始化时或者插入元素时，有可能平衡被破坏，如下图所示：
(1) 插入12，8，5进行初始化

(2) 在一棵树增加一个元素时，插入数字2时，平衡被打破

以上就是插入的元素在不平衡节点的左侧的左侧，假设原先平衡，但是插入z之后不再平衡，

这时候只需要进行右旋转即可恢复平衡状态：
令
y.left = x.right(T3)
x.right = y
进而实现旋转：

其实现代码如下：

// 右旋转
    private Node<K,V> rightRotate(Node<K,V> y) {
        Node<K,V> x = y.left;
        Node<K,V> t3 = x.right;

        x.right = y;
        y.left = t3;

        // 因为y失衡，此时调整会导致x,y的高度发生变化
        y.height = Math.max(getHeight(y.left), getHeight(y.right)) + 1;
        x.height = Math.max(getHeight(x.left), getHeight(x.right)) + 1;
        return x;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13

2.4.2 RR（即插入的点在不平衡节点的右侧的右侧）

即
y.right = x.left(T3)
x.left = y
完成一次左旋转即可，参考代码如下：

// 左旋转
    private Node<K,V> leftRotate(Node<K,V> y) {
        Node<K,V> x = y.right;
        Node<K,V> t3 = x.left;

        x.left = y;
        y.right = t3;

        y.height = Math.max(getHeight(y.left), getHeight(y.right)) + 1;
        x.height = Math.max(getHeight(x.left), getHeight(x.right)) + 1;

        return x;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13

2.4.3 LR（待插入的节点在不平衡节点的左侧的右侧）

由图可知，他是先针对x节点进行了一次左旋转，将模式转成为LL模型，然后再进行一次右旋转，即达到树的平衡。

2.4.4 RL（即待插入的节点在不平衡节点的右侧的左侧）

这种情况是先针对x进行一次右旋转，然后变成RR类型，在对y进行左旋转维持平衡。
以上就是插入节点Z导致不平衡的四种情况（LL,RR,LR,RL)，主要是借助左右旋转来保持平衡。删除情况为了维护平衡也是一样的四种情况，其java代码参考如下:
添加元素代码:

private Node add(Node<K,V> node, K key, V value){

        if(node == null){
            size ++;
            return new Node(key, value);
        }

        if(key.compareTo(node.key) < 0) {
            node.left = add(node.left, key, value);
        } else if(key.compareTo(node.key) > 0) {
            node.right = add(node.right, key, value);
        } else {// key.compareTo(node.key) == 0 {
            node.value = value;
        }

        node.height = 1 + Math.max(getHeight(node.left), getHeight(node.right));

        int balanceFactor = getBalanceFactor(node);
        /*if (Math.abs(balanceFactor) > 1) {
            System.out.println("balance factor above 1, balanceFactor = " + balanceFactor);
        }*/

        // 平衡的四种情况的代码维护
        // LL
        if (balanceFactor > 1 && getBalanceFactor(node.left) >= 0) {
            return rightRotate(node);
        }

        // RR
        if (balanceFactor < -1 && getBalanceFactor(node.right) <= 0) {
            return leftRotate(node);
        }

        // LR
        if (balanceFactor > 1 && getBalanceFactor(node.left) < 0 ) {
            node.left = leftRotate(node.left);
            return rightRotate(node);
        }

        // RL
        if (balanceFactor < -1 && getBalanceFactor(node.right) > 0) {
            node.right = rightRotate(node.right);
            return leftRotate(node);
        }
        return 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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

删除元素代码：

private Node<K,V> remove(Node<K,V> node, K key){

        if( node == null )
            return null;

        Node<K,V> retNode;

        if( key.compareTo(node.key) < 0 ){
            node.left = remove(node.left , key);
            retNode = node;
        }
        else if(key.compareTo(node.key) > 0 ){
            node.right = remove(node.right, key);
            retNode = node;
        }
        else{   // key.compareTo(node.key) == 0

            // 待删除节点左子树为空的情况
            if(node.left == null){
                Node rightNode = node.right;
                node.right = null;
                size --;
                retNode = rightNode;
            }

            // 待删除节点右子树为空的情况
             else if(node.right == null){
                Node leftNode = node.left;
                node.left = null;
                size --;
                retNode = leftNode;
            }
            else {
                // 待删除节点左右子树均不为空的情况

                // 找到比待删除节点大的最小节点, 即待删除节点右子树的最小节点
                // 用这个节点顶替待删除节点的位置
                Node<K, V> successor = minimum(node.right);
                //successor.right = removeMin(node.right);
                successor.right = remove(node.right, successor.key);
                successor.left = node.left;

                node.left = node.right = null;

                retNode = successor;
            }

        }

        if (retNode == null) {
            return null;
        }
        retNode.height = 1 + Math.max(getHeight(retNode.left), getHeight(retNode.right));

        int balanceFactor = getBalanceFactor(retNode);
        /*if (Math.abs(balanceFactor) > 1) {
            System.out.println("balance factor above 1, balanceFactor = " + balanceFactor);
        }*/

        // 平衡的四种情况的代码维护
        // LL
        if (balanceFactor > 1 && getBalanceFactor(retNode.left) >= 0) {
            return rightRotate(retNode);
        }

        // RR
        if (balanceFactor < -1 && getBalanceFactor(retNode.right) <= 0) {
            return leftRotate(retNode);
        }

        // LR
        if (balanceFactor > 1 && getBalanceFactor(retNode.left) < 0 ) {
            retNode.left = leftRotate(retNode.left);
            return rightRotate(retNode);
        }

        // RL
        if (balanceFactor < -1 && getBalanceFactor(retNode.right) > 0) {
            retNode.right = rightRotate(retNode.right);
            return leftRotate(retNode);
        }
        return retNode;

    }

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85