?平衡二叉查找树(AVL Tree)
平衡二叉查找树是空树或者一种结构平衡的二叉查找树，即叶节点高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
如果在AVL树中进行插入或删除节点，可能导致AVL树失去平衡，这种失去平衡的二叉树可以概括为四种姿态：LL（左左）、RR（右右）、LR（左右）、RL（右左）。
LL：LeftLeft，也称“左左”。插入或删除一个节点后，根节点的左孩子（Left Child）的左孩子? ? ? ?（Left?Child）还有非空节点，导致根节点的左子树高度比右子树高度高2，AVL树失去平衡。
RR：RightRight，也称“右右”。插入或删除一个节点后，根节点的右孩子（Right Child）的右孩子 （Right Child）还有非空节点，导致根节点的右子树高度比左子树高度高2，AVL树失去平衡。
LR：LeftRight，也称“左右”。插入或删除一个节点后，根节点的左孩子（Left Child）的右孩子（Right Child）还有非空节点，导致根节点的左子树高度比右子树高度高2，AVL树失去平衡。
RL：RightLeft，也称“右左”。插入或删除一个节点后，根节点的右孩子（Right Child）的左孩子（Left Child）还有非空节点，导致根节点的右子树高度比左子树高度高2，AVL树失去平衡。
平衡二叉树的最少结点数：n(h)=n(h-1)+n(h-2)+1
给定结点数为n的AVL树的最大高度为O(log2 n)
平衡二叉树的调整
左单旋
treePtr singleLeft(treePtr T){
treePtr tmpPtr;
tmpPtr = T;
T = T->Left;
tmpPtr->Left = T->Right;
T->Right = tmpPtr;
tmpPtr->Height = max(GetHeight(tmpPtr->Left),GetHeight(tmpPtr->Right))+1;
T->Height = max(GetHeight(T->Left),GetHeight(T->Right))+1;
return T;
}右单旋
treePtr singleRight(treePtr T){
treePtr tmpPtr;
tmpPtr = T;
T = T->Right;
tmpPtr->Right = T->Left;
T->Left = tmpPtr;
tmpPtr->Height = max(GetHeight(tmpPtr->Left),GetHeight(tmpPtr->Right))+1;
T->Height = max(GetHeight(T->Left),GetHeight(T->Right))+1;
return T;
}LR旋转
左结点进行右单旋，然后对其父结点（即当前结点）进行左单旋；
treePtr LeftRight(treePtr T){
T->Left = singleRight(T->Left);
return singleLeft(T);
}RL旋转
右结点进行左单旋，然后对其父结点（即当前结点）进行右单旋；
treePtr RightLeft(treePtr T){
T->Right = singleLeft(T->Right);
return singleRight(T);
}例题：Root of AVL Tree
An AVL tree is a self-balancing binary search tree. In an AVL tree, the heights of the two child subtrees of any node differ by at most one; if at any time they differ by more than one, rebalancing is done to restore this property. Figures 1-4 illustrate the rotation rules.
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
?Now given a sequence of insertions, you are supposed to tell the root of the resulting AVL tree.
Input Specification:
Each input file contains one test case. For each case, the first line contains a positive integer?N?(≤20) which is the total number of keys to be inserted. Then?N?distinct integer keys are given in the next line. All the numbers in a line are separated by a space.
Output Specification:
For each test case, print the root of the resulting AVL tree in one line.
Sample Input 1:
5
88 70 61 96 120?Sample Output 1:
70Sample Input 2:
7
88 70 61 96 120 90 65Sample Output 2:
88Demo:
#include<iostream>
using namespace std;
typedef struct tree* treePtr;
struct tree{
int Data=0;
int Height=0;
treePtr Left=NULL;
treePtr Right=NULL;
};
int GetHeight(treePtr T){ //获取深度
if(!T) return -1;
else return T->Height;
}
treePtr singleLeft(treePtr T){ //左单旋
treePtr tmpPtr;
tmpPtr = T;
T = T->Left;
tmpPtr->Left = T->Right;
T->Right = tmpPtr;
tmpPtr->Height = max(GetHeight(tmpPtr->Left),GetHeight(tmpPtr->Right))+1;
T->Height = max(GetHeight(T->Left),GetHeight(T->Right))+1;
return T;
}
treePtr singleRight(treePtr T){ //右单旋
treePtr tmpPtr;
tmpPtr = T;
T = T->Right;
tmpPtr->Right = T->Left;
T->Left = tmpPtr;
tmpPtr->Height = max(GetHeight(tmpPtr->Left),GetHeight(tmpPtr->Right))+1;
T->Height = max(GetHeight(T->Left),GetHeight(T->Right))+1;
return T;
}
treePtr LeftRight(treePtr T){ //LR旋转
T->Left = singleRight(T->Left);
return singleLeft(T);
}
treePtr RightLeft(treePtr T){ //RL旋转
T->Right = singleLeft(T->Right);
return singleRight(T);
}
treePtr NewTree(int t, treePtr T){ //增加结点并完成平衡
if(T == NULL){
T = new tree;
T->Data = t;
T->Left = NULL;
T->Right = NULL;
T->Height = 0;
}
else if(t < T->Data){
T->Left = NewTree (t, T->Left);
if(GetHeight(T->Left) - GetHeight(T->Right) == 2){
if(t < T->Left->Data) T = singleLeft(T);
else T = LeftRight(T);
}
}
else if(t > T->Data){
T->Right = NewTree (t, T->Right);
if(GetHeight(T->Right) - GetHeight(T->Left) == 2){
if(t > T->Right->Data) T = singleRight(T);
else T = RightLeft(T);
}
}
T->Height = max(GetHeight(T->Left), GetHeight(T->Right)) + 1;
return T;
}
int main(){
int N;
int data;
treePtr tree = NULL;
cin>>N;
while(N--){
cin>>data;
tree = NewTree(data, tree);
}
if(tree) cout<<tree->Data<<endl;
return 0;
}