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);
}
}
网友评论