平衡二叉树
定义
平衡二叉树定义(AVL)：它或者是一颗空树，或者具有以下性质的二叉树：它的左子树和右子树的深度之差(平衡因子)的绝对值不超过1，且它的左子树和右子树都是一颗平衡二叉树。
平衡因子(bf)：结点的左子树的深度减去右子树的深度，那么显然-1<=bf<=1
失去平衡的最小子树是指以离插入结点最近，且平衡因子绝对值大于1的结点作为根的子树。假设用A表示失去平衡的最小子树的根结点，则调整该子树的操作可归纳为下列四种情况。
当对一颗AVL树进行插入操作，可能会导致AVL树不平衡，此时，我们就需要做平衡处理，假设重新平衡的节点为Q，则不平衡会下列四种情况，并做出调整
在Q的左孩子的左子树插入 （LL）
在Q的左孩子的右子树插入 （LR）
在Q的右孩子的左子树插入 （RL）
在Q的右孩子的右子树插入 （RR）
参考文章
平衡处理
左平衡
所谓左平衡处理，就是某一根结点的左子树比右子树过高，从而失去了平衡。在节点的左子树进行插入操作使此节点失去平衡，需要左平衡处理。
右平衡
类似左平衡处理，所谓右平衡处理，就是某一根结点的右子树比左子树过高，从而失去了平衡。
LL
思路：先把B的右子树变为A的左子树，在把A作为B的右子树
RR
思路：先把C的左子树作为A的右子树，在把A作为C的左子树。
LR
先将A结点的左孩子B的右子树的根结点D向左上旋转提升到B结点的位置，然后再把该D结点向右上旋转提升到A结点的位置。即先使之成为LL型，再按LL型处理。
如图中所示，先将圈圈的部分进行逆时针旋转（RR旋转），使之转换为LL型，再进行LL旋转；（双旋转）
RL
如图中所示，先将圈圈的部分进行顺时针旋转（LL旋转），使之转换为RR型，再进行RR旋转；（双旋转）
代码
#include<algorithm>
#include<iostream>
#include<stdio.h>
#include<string>
#include<vector>
#include<queue>
using namespace std;
struct t
{
int data;
t *left, *right;
int height;
t() :data(0), left(NULL), right(NULL), height(0) {
}
t(int data1) :data(data1), left(NULL), right(NULL), height(0) {
}
};
int nodeheight(t *node) {
return node == NULL ? -1 : node->height;
}
int updateHeight(t *node) {
//cout << "new height " << node->data << " " << max(nodeheight(node->left), nodeheight(node->right)) + 1 << endl;;
return max(nodeheight(node->left), nodeheight(node->right)) + 1;
}
void LL(t *&node) {
if (node) {
t *p = node->left;
node->left = p->right;
updateHeight(node);
p->right = node;
updateHeight(p);
node = p;
}
}
void RR(t *&node) {
if (node) {
t *p = node->right;
node->right = p->left;
updateHeight(node);
p->left = node;
updateHeight(p);
node = p;
}
}
void LR(t *&node) {
if (node) {
RR(node->left);
LL(node);
}
}
void RL(t *&node) {
if (node) {
LL(node->right);
RR(node);
}
}
void LeftBalance(t *&node) {
cout << "leftBalance " << node->data << endl;
t *p = node->left;
if (nodeheight(p->left) < nodeheight(p->right)) {
LR(node);
}
else {
LL(node);
}
}
void RightBalance(t *&node) {
//cout << "rightBalance " << node->data << endl;
t *p = node->right;
if (nodeheight(p->left) > nodeheight(p->right)) {
RL(node);
}
else {
RR(node);
}
}
void insertNode(t *&node,int data) {
if (!node) {
node = new t(data);
}
else if (data < node->data) {
//cout << node->data <<" left: "<<data<< endl;
insertNode(node->left, data);
if (nodeheight(node->left) - nodeheight(node->right) == 2) {
LeftBalance(node);
}
}
else if (data > node->data) {
//cout << node->data << " right: " << data << endl;
insertNode(node->right, data);
if (nodeheight(node->left) - nodeheight(node->right) == -2) {
RightBalance(node);
}
}
else
cout<<node->data << "重复插入" << endl;
node->height=updateHeight(node);
}
void deleteNode(t *&node,int data) {
if (!node) {
return;
}
if (data > node->data) {
deleteNode(node->right, data);
if (nodeheight(node->left) - nodeheight(node->right) == 2) {
LeftBalance(node);
}
}
else if (data < node->data) {
deleteNode(node->left, data);
if (nodeheight(node->right) - nodeheight(node->left) == 2) {
RightBalance(node);
}
}
else {
if (!node->left) {
t *p = node;
node = node->right;
delete p;
}
else if (!node->right) {
t *p = node;
node = node->left;
delete p;
}
else {
t *p = node->left;
while (p->right) {
p = p->right;
}
node->data = p->data;
deleteNode(node->left, p->data);
}
}
}
t* createTree(vector<int> v) {
t *root = NULL;
for (int i = 0; i < v.size(); i++) {
insertNode(root,v[i]);
}
return root;
}
void visitlvr(t *root) {
if (root != NULL) {
visitlvr(root->left);
cout << root->data << " ";
visitlvr(root->right);
}
}
void visitvlr(t *root) {
if (root != NULL) {
cout << root->data << " ";
visitvlr(root->left);
visitvlr(root->right);
}
}
void visitlrv(t *root) {
if (root != NULL) {
visitlrv(root->left);
visitlrv(root->right);
cout << root->data << " ";
}
}
void visitTree(t *tree) {
visitlvr(tree);
cout << endl;
visitvlr(tree);
cout << endl;
visitlrv(tree);
cout << endl;
}
int main() {
freopen("D:/in.txt", "r", stdin);
vector<int> v;
int n;
cin >> n;
for (int i = 0; i < n; i++) {
int a;
cin >> a;
v.push_back(a);
}
t *tree = createTree(v);
visitTree(tree);
deleteNode(tree, 7);
visitTree(tree);
//visitTree(tree);
return 0;
}