# AVL树（算法导论）

``````#include <iostream>
#include <algorithm>
using namespace std;

struct node // 节点
{
node *left;
node *right;
node *parent;
int data;
int h; // 树高 h >= 2 时候就得调整平衡

node() : left(nullptr), right(nullptr), parent(nullptr), data(0), h(1){}
node(int k) : left(nullptr), right(nullptr), parent(nullptr), data(k), h(1){}
};

class AVL
{
public:
AVL() : root(nullptr){}
public:
int height(node *x); // 求树的高度
void print(node *x); // 中序遍历输出
node *left_Rotate(node *x); // 左旋
node *right_Rotate(node *x); // 右旋
node *AVL_insert(node *x, node *z); // 插入
node *root;  //指向根节点的指针
};

int AVL::height(node *x)
{
if (x == nullptr)
{
return 0;
}
return x->h;
}

node* AVL::left_Rotate(node *x)  //    4          3
{								//	    \	->   /
node *y = x->right;        //        3      4
x->right = y->left;
if (y->left != nullptr)
{
y->left->parent = x;
}
y->parent = x->parent;
if (x->parent == nullptr)
{
root = y;
}
else if (x == x->parent->left)
{
x->parent->left = y;
}
else
{
x->parent->right = y;
}
y->left = x;
x->parent = y;

x->h = max(height(x->left), height(x->right)) + 1;
y->h = max(height(y->left), height(y->right)) + 1;

return y;
}

node* AVL::right_Rotate(node *x)     //   3     4
{								    //	 /  ->   \
node *y = x->left;             //   4         3
x->left = y->right;
if (y->right != nullptr)
{
y->right->parent = x;
}
y->parent = x->parent;
if (x->parent == nullptr)
{
root = y;
}
else if (x == x->parent->right)
{
x->parent->right = y;
}
else
{
x->parent->left = y;
}
y->right = x;
x->parent = y;

x->h = max(height(x->left), height(x->right)) + 1; // 更新树的高度
y->h = max(height(y->left), height(y->right)) + 1;

return y;
}

node* AVL::AVL_insert(node *x, node *z)
{
if (x == nullptr)  //  只有空树时候执行
{
root = z;
return x;
}

if (z->data < x->data)
{
if (x->left)
{
z = AVL_insert(x->left, z);
}
x->left = z;
z->parent = x;

node *y = x->right;
int hl = z->h; int hr = height(y);

if (hl - hr >= 2)
{
node *a = z->left; node *b = z->right;
if (a > b) // LL
{
return right_Rotate(x);
}
else if (a < b) // LR
{
z = left_Rotate(z);
return right_Rotate(x);
}
}
x->h = max(hl, hr) + 1;
return x;
}

if (z->data > x->data)
{
if (x->right)
z = AVL_insert(x->right, z);
x->right = z;
z->parent = x;

node *y = x->left;
int hl = height(y); int hr = z->h;

if (hr - hl >= 2)
{
node *a = z->left;
node *b = z->right;
if (a > b)
{
z = right_Rotate(z);
return left_Rotate(x);
}
else if (a < b)
{
return left_Rotate(x);
}
}
x->h = max(hl, hr) + 1;
return x;
}
}

void AVL::print(node *x)
{
if (x == nullptr)
{
return;
}
print(x->left);
cout << x->data << "  ";
print(x->right);
}

int main()
{
AVL tree;

for (int i = 0; i < 6; ++i)
{
tree.AVL_insert(tree.root, new node(i+1));
}

tree.print(tree.root);

return 0;
}``````

原文作者：AVL树
原文地址: https://blog.csdn.net/u013479704/article/details/39024965
本文转自网络文章，转载此文章仅为分享知识，如有侵权，请联系博主进行删除。