AVL树中旋转算法的调用

AVL树中旋转算法的调用

在AVL树中旋转算法的调用肯定是在添加元素和删除元素的时候调用(这里我们以添加元素为例)

因为我们的AVL树几乎和BST(二分搜索树)的实现一模一样, 其实AVL树就是自平衡的二分搜索树, 所以我们就只需要在添加一个节点之后判断树是否还是平衡的, 如果不平衡则调用对应的旋转算法让树重新平衡化就可以了

• 这里我们先仅仅给出旋转算法的调用, 最终我们会将整个添加元素的方法给出

// ==== 添加结点完成 ====
//当添加完一个节点之后, 如果左子树高度 - 右子树高度 > 1, 说明不平衡, 并且类型为L开头
if(leftHeight() - rightHeight() > 1){
    //如果它的左子节点的左子树高度大于它的右子树高度, 说明类型为LL
    if(left != null && left.leftHeight() > left.rightHeight()){
        //直接对当前节点进行一个右旋即可 --> 当前节点就是此时LL型的最小不平衡子树的根节点
        rightRotate();
    }else{ //说明为LR型(此时肯定是左子节点的右子树高度大于左子树高度)
        //先对当前节点的左子节点进行一个左旋 --> 就能得到一个LL型最小不平衡子树
        left.leftRototate();

        //再对当前节点进行一个右旋 ---> 也就是是对转换之后的LL型最小不平衡子树进行了一个右旋
        rightRotate();
    }
}

//当添加完一个节点之后, 如果右子树高度 - 左子树高度 > 1, 说明不平衡, 并且最小不平衡子树类型以R开头
if(rightHeight() - leftHeight() > 1){
    //如果它的右子节点的右子树高度大于它的左子树高度, 说明类型为RR型
    if(right != null && right.rightHeight() > right.leftHeight()){
        //直接对当前节点进行一个左旋即可
        leftRototate();
    }else{ //说明为RL型
        //先对当前节点的右子节点进行一个右旋
        right.rightRotate();

        //然后对当前节点进行一个左旋
        leftRototate();
    }
}
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

这里我们完整的给出Node节点类中的递归的添加节点的方法:

/**
     * @param node 这个node是待添加的结点
     */
public void add(Node node){
    //这个递归方法我们每次递归的时候是改变的方法的调用者

    //1.判断入参
    // 注意: 这个时候只是我们对入参的判断 , 并不是递归的结束条件
    if(node == null){//如果待添加结点是一个null的时候那么我们就不用添加这个节点了, 直接就退出就可以了
        return; //由于此时我们实现的递归方法是没有返回值的, 所以这个时候我们我们直接退出就可以了
    }

    //如果node的值不为空, 那么就说明这个节点是合法的, 所以我们就要来判断这个节点要添加的位置
    if(node.value < this.value) {//如果这个时候node节点的value值要小于我们的this的value的值, 那么我们肯定是要去左子树上继续查找, 所以这个时候我们就要使用左子节点来递归调用此方法
        if(this.left != null){
            //如果当前节点的左子节点不为空的时候此时我们才继续向左子树去遍历,如果这个时候左子节点为空了, 那么就表明这个位置其实我们是已经找到了
            this.left.add(node);
        }else{
            //如果当前节点的左子节点为空, 那么就证明这个位置就是我们节点要添加的位置, 我们此时就就将我们的节点直接放到当前节点的左子节点的位置即可
            this.left = node;
        }
    }else { //如果node的值(也就是待添加结点的值大于或者是等于我们当前节点的value值的时候我们就要向右子树上进行遍历)
        // 这个时候一定要注意: 我们此时如果等于的时候也是向右子树去查找位置了, 就说明最后的时候我们如果两个结点的值是一样大的, 那儿我们将这个节点添加到了右子树上
        // 对应的如果执行其他的二叉排序树的操作的时候如果我们要判断两个值相同的情况的时候我们就要去右子树上去看
        if(this.right != null) {
            //判断当前节点的右子节点是否为null ,如果不为空的时候我们就递归的向右子树进行一个遍历
            this.right.add(node);

        }else{
            //如果此时当前节点的右子节点为空了,那么就表示我们找到了待插入节点的插入位置, 我们直接将我们的待插入节点插入即可
            this.right = node;
        }
    }

    // ==== 添加结点完成 ====
    //当添加完一个节点之后, 如果左子树高度 - 右子树高度 > 1, 说明不平衡, 并且类型为L开头
    if(leftHeight() - rightHeight() > 1){
        //如果它的左子节点的左子树高度大于它的右子树高度, 说明类型为LL
        if(left != null && left.leftHeight() > left.rightHeight()){
            //直接对当前节点进行一个右旋即可 --> 当前节点就是此时LL型的最小不平衡子树的根节点
            rightRotate();
        }else{ //说明为LR型(此时肯定是左子节点的右子树高度大于左子树高度)
            //先对当前节点的左子节点进行一个左旋 --> 就能得到一个LL型最小不平衡子树
            left.leftRototate();

            //再对当前节点进行一个右旋 ---> 也就是是对转换之后的LL型最小不平衡子树进行了一个右旋
            rightRotate();
        }
    }

    //当添加完一个节点之后, 如果右子树高度 - 左子树高度 > 1, 说明不平衡, 并且最小不平衡子树类型以R开头
    if(rightHeight() - leftHeight() > 1){
        //如果它的右子节点的右子树高度大于它的左子树高度, 说明类型为RR型
        if(right != null && right.rightHeight() > right.leftHeight()){
            //直接对当前节点进行一个左旋即可
            leftRototate();
        }else{ //说明为RL型
            //先对当前节点的右子节点进行一个右旋
            right.rightRotate();

            //然后对当前节点进行一个左旋
            leftRototate();
        }
    }
}
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