AVL树左旋转,右旋转代码实现

AVL树左旋转, 右旋转代码实现

我们这里先给出左旋转实现

//左旋转算法
private void leftRototate(){
    //创建新的结点, 以当前根节点的值
    Node newNode = new Node(this.value);

    //让新的结点的左子节点指向当前根节点的左子节点
    newNode.left = this.left;

    //让新的结点的右子树指向当前节点的右子节点的左子树
    newNode.right = this.right.left;

    //把当前节点的值替换成其右子节点的值
    this.value = right.value;

    //让当前结点的右子节点指向当前结点的右子节点的右子树
    right = right.right;

    //让当前结点的左子节点指向新创建的结点
    left = newNode;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

• 注意: 这个方法是在Node(结点类)中定义的, 其中的this表示的是某个结点, 具体这个方法最终是要在添加结点操作中执行, 我们最终每次调用这个方法的结点都会是我们需要左旋的结点
  • 如果是RR型最小不平衡子树, 那么需要左旋的就是最小不平衡子树的根节点
  • 如果是LR型最小不平衡子树, 那么需要左旋的就是最小不平衡子树的根节点的左子节点

然后给出右旋转实现

//右旋转算法
private void rightRotate(){
    //创建新的结点, 以当前根节点的值
    Node newNode = new Node(this.value);

    //让新的结点的右子节点指向当前根节点的右子树
    newNode.right = this.right;

    //让新结点的左子节点指向当前根节点左子节点的右子树
    newNode.left = this.left.right;

    //把当前结点的值替换为当前根节点的左子节点的值
    this.value = this.left.value;

    //让当前节点的左子节点指向当前节点的左子节点的左子树
    this.left = this.left.left;

    //让当前节点的右子节点指向新结点
    right = newNode;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

• 这个方法也是一样的, 是定义在Node结点类中的, 最终调用该方法的结点都会是需要右旋的结点,
  • 如果是LL型的最小不平衡子树, 需要右旋的结点就是最小不平衡子树的根节点
  • 如果是RL型最小不平衡子树, 需要右旋的结点就是最小不平衡子树的根节点的右子节点

注意: 我们的AVL树中是没有双旋转这个算法的, 所谓的双旋转其实就是在最小不平衡子树为LR型和RL型的时候要分别调用一次左旋和一次右旋也就是两次旋转 —> 所以说AVL树中的算法只有左旋转和右旋转, 我们只要在对应的实际去使用对应的对象去调用对应的旋转算法就能使得我们的树重新平衡化