平衡二叉树AVL的左旋和右旋

AVL树

平衡二叉树是一颗自平衡的搜索二叉树，树内任何节点的左右子树的高度差不超过1。

AVL树和非AVL树

非AVL树的几种模型

右旋

image.png

针对节点8，它的左子树的高度为3，右子树高度为1，高度差超过1。并且出错的节点1和3位于8节点的左子节点4的左边。针对这种类型的非平衡树，通过右旋便可以使其重新平衡。
具体做法： 将节点8作为节点4的右子节点，节点6作为节点8的左子节点

右旋后的结果

用一个动图来表示 右旋

右旋.gif

左旋

image.png

针对节点8，它的左子树的高度是1，右子树的高度是3，高度差超过1.并且出错的节点13和15均位于节点8的右子节点12的右边，则通过左旋便可修复。

image.png

动画演示：

左旋.gif

先左旋再右旋

image.png

针对节点8，左子树的高度是3，右子树高度是1，高度差超过1。并且出错的节点5和7均位于节点8的左节点4的右边。这种情况需要先左旋再右旋便可恢复。

先左旋后

针对节点4进行左旋，左旋后变成了需要右旋的情况，可参考上面的右旋进行旋转即可。

先右旋再左旋

image.png

类似的针对12节点先进行右旋，再整体左旋，原理类似 不再赘述

代码

treeNode头文件

//
// Created by issuser on 2021/9/16.
//

#ifndef AVLTREE_TREENODE_H
#define AVLTREE_TREENODE_H
typedef int  Type;

#include <malloc.h>
class Node {
public:
    Type key;
    Node* left;
    Node* right;
    int height;

    Node(Type key,Node* left,Node* right){
        this->key=key;
        this->left=left;
        this->right=right;
        this->height=0;

    }

    ~Node(){
        this->key=NULL;
        this->left=NULL;
        this->right=NULL;
        this->height=NULL;
    }
};


#endif //AVLTREE_TREENODE_H

AVL_teee 头文件

//
// Created by issuser on 2021/9/16.
//

#ifndef AVLTREE_AVL_TREE_H
#define AVLTREE_AVL_TREE_H

#include "TreeNode.h"

class AVL_tree {
public:
    //根节点
    Node* root;
    //插入 外部调用
    void insert(Type key);
    //插入 内部循环调用
    Node* avl_insert(Node* root,Type key);
    //右旋
    Node* right_rotaion(Node* node);
    //左旋
    Node* left_rotaion(Node* node);
    //先左旋再右旋
    Node* left_right_rotaion(Node* node);
    //先右旋再左旋
    Node* right_left_rotaion(Node* node);
    //前序遍历
    void preorder_avltree(Node* tree);

};


#endif //AVLTREE_AVL_TREE_H

//
// Created by issuser on 2021/9/16.
//

#include "AVL_tree.h"
#include "android/log.h"

#define HEIGHT(p)((p==NULL)?-1:((Node*)(p))->height)

#define MAX(m,n)( (m) > (n) ? (m) : (n) )

Node *AVL_tree::avl_insert(Node *node, Type key) {
    if(node==NULL){
        node=new Node(key,NULL,NULL);
        return node;
    }
    //需要插在node的左边
    if(node->key>key){
        node->left=avl_insert(node->left,key);
        //需要插在node的右边
    } else if(node->key<key){
        node->right=avl_insert(node->right,key);
    } else{
        //不允许插入相同的key

    }
    //左子树比右子树高，出错节点位于左子树中
    if(HEIGHT(node->left)-HEIGHT(node->right)==2){
        //出错节点位于node的左子节点的左边 是需要右旋
        if(node->left->key>key){
            //右旋
            node=right_rotaion(node);
        } else{ //出错节点位于node的左节点的右边，需要先左旋再右旋
            //先左旋再右旋
            node=left_right_rotaion(node);
        }


    } else if(HEIGHT(node->right)-HEIGHT(node->left)==2){

        if(node->right->key<key){
            //左旋
            node=left_rotaion(node);
        } else{
            node=right_left_rotaion(node);
        }
    }

    //插入节点后 重新计算当前节点的高度
    node->height=MAX(HEIGHT(node->left) ,HEIGHT(node->right))+1;

    return node;


}

void AVL_tree::insert(Type key) {
    if(this->root==NULL){
        this->root=new Node(key,NULL,NULL);
        return;
    }

    this->root= avl_insert(root,key);



}
//右旋
Node* AVL_tree::right_rotaion(Node *k2) {

    Node* k1=k2->left;
    k2->left=k1->right;
    k1->right=k2;

    //旋转后 重新计算节点的高度

    k2->height=MAX(HEIGHT(k2->left),HEIGHT(k2->right))+1;
    k1->height=MAX(HEIGHT(k1->left),k2->height)+1;

    return k1;





}

Node* AVL_tree::left_rotaion(Node *k2) {
    Node* k1=k2->right;
    k2->right=k1->left;
    k1->left=k2;

    k2->height=MAX(HEIGHT(k2->left),HEIGHT(k2->right))+1;
    k1->height=MAX(k2->height,HEIGHT(k1->right))+1;
    return k1;

}

Node* AVL_tree::left_right_rotaion(Node *k3) {

    k3->left=left_rotaion(k3->left);
    return right_rotaion(k3);


}

Node* AVL_tree::right_left_rotaion(Node *k3) {
    k3->right=right_rotaion(k3->right);
    return left_rotaion(k3);
}

void AVL_tree::preorder_avltree(Node *tree) {
    if(tree!=NULL){
        __android_log_print(ANDROID_LOG_ERROR,"TAG","前序遍历====%d",tree->key);
        preorder_avltree(tree->left);
        preorder_avltree(tree->right);
    }
}