二叉查找树是个好东西，他让查找，插入，删除，这些常用操作变得高效，但是，他是存在问题的，那就是，在坏的输入序列下，树会退化成链表，这就很尴尬了，于是为了避免这种情况的发生，我们需要一种数据结构，可以自动对树进行调整，我们希望树尽量平衡，于是我们使用平衡因子作为指标，保持任意节点左右子树深度差不超过1，这就可以让树的深度很理想了（接近log2N)，如何对树进行调整呢？我们通过旋转来完成他。
#include <iostream>
#include <queue> class AVLT{//小于向左，大于等于向右,元素类型需支持 <
private:
typedef int Element;
struct AVLTNode{
Element data;
AVLTNode *left;
AVLTNode *right;
int Deepth;
AVLTNode();
~AVLTNode();
bool isLeaf()const;
void nodeInsect(const Element &e);
void nodeDelete(const Element &e);
const AVLTNode *Find(const Element &e)const;
const Element& Min()const;
const Element& Max()const;
void nodeTraverseFrist(std::ostream& os = std::cout)const;
void nodeTraverseMid(std::ostream& os = std::cout)const;
void nodeTraverseLast(std::ostream& os = std::cout)const;
void nodeTraverselevel(std::ostream& os = std::cout)const;
const AVLTNode & operator =(const AVLTNode &T);
void swapdata(AVLTNode&a, AVLTNode&b)const;
void SingleLeftRotation();
void SingleRightRotation();
void DoubleRightLeftRotation();
void DoubleLeftRightRotation();
inline void renewDeepth();
inline int max(int a, int b)const;
};
AVLTNode *node;
int number_of_Node;
public:
AVLT();
AVLT(Element *arr, int size);
AVLT(const AVLT &T);
~AVLT();
bool empty()const;
const Element& Max()const;
const Element& Min()const;
const AVLT &operator = (const AVLT&T);
void TraverseFrist(std::ostream& os = std::cout)const;
void TraverseLast(std::ostream& os = std::cout)const;
void TraverseMid(std::ostream& os = std::cout)const;
void Traverselevel(std::ostream& os = std::cout)const;
void Insect(const AVLT::Element &e);
bool Delete(const AVLT::Element &e);
int Deepth();
int Node();
const AVLTNode* find(const Element &e)const;
}; AVLT::AVLTNode::AVLTNode():left(NULL), right(NULL), Deepth(){}
AVLT::AVLTNode::~AVLTNode(){
delete left;
delete right;
}
bool AVLT::AVLTNode::isLeaf()const{
return left == NULL&&right == NULL;
}
void AVLT::AVLTNode::nodeInsect(const Element &e){
if (Deepth == ){
Deepth = ;
data = e;
return;
}
if (e<data){
if (left == NULL){
left = new AVLTNode;
}
left->nodeInsect(e);
if (right){
if (left->Deepth - right->Deepth > ){
if (e<left->data){
this->SingleRightRotation();
}
else{
this->DoubleLeftRightRotation();
}
}
}
else{
if (left->Deepth > ){
if (e<left->data){
this->SingleRightRotation();
}
else{
this->DoubleLeftRightRotation();
}
}
}
renewDeepth();
}
else{
if (right == NULL){
right = new AVLTNode;
}
right->nodeInsect(e);
if (left){
if (right->Deepth - left->Deepth > ){
if (e<right->data){
this->DoubleRightLeftRotation();
}
else{
this->SingleLeftRotation();
}
}
}
else{
if (right->Deepth > ){
if (e<right->data){
this->DoubleRightLeftRotation();
}
else{
this->SingleLeftRotation();
}
}
}
renewDeepth();
}
return;
}
void AVLT::AVLTNode::nodeDelete(const Element &e){
if (e<data){
if (left){
if (left->isLeaf()){
delete left;
left = NULL;
}
else
left->nodeDelete(e);
{
int rd = right ? right->Deepth : ;
int ld = left ? left->Deepth : ;
if (rd - ld >){
if (right->left){
DoubleRightLeftRotation();
}
else{
SingleLeftRotation();
}
}
renewDeepth();
}
}
return;
}
else{
if (data<e){
if (right){
if (right->isLeaf()){
delete right;
right = NULL;
}
else
right->nodeDelete(e);
{
int rd = right ? right->Deepth : ;
int ld = left ? left->Deepth : ;
if (ld - rd >){
if (left->right){
DoubleLeftRightRotation();
}
else{
SingleRightRotation();
}
}
renewDeepth();
}
return;
}
}
else{
if (left == NULL&&right){
AVLTNode *t = right;
if (left)
delete left;
left = t->left;
right = t->right;
data = t->data;
Deepth -= ;
t->left = t->right = NULL;
delete t;
return;
}
else{
if (right == NULL && left){
AVLTNode *t = left;
if (right)
delete right;
right = t->right;
left = t->left;
data = t->data;
Deepth -= ;
t->left = t->right = NULL;
delete t;
return;
}
else{ AVLTNode *t = left;
while (t->right)
t = t->right;
Element te = t->data;
if (left->isLeaf()){
delete left;
left = NULL;
}
else
left->nodeDelete(te);
data = te;
return;
}
}
}
}
std::cout << "return false" << std::endl;
return;
}
AVLT::AVLTNode const *AVLT::AVLTNode::Find(const Element &e)const{
if (e<data){
if (left)
return left->Find(e);
}
else{
if (data<e){
if (right)
return right->Find(e);
}
else{
return this;
}
}
return NULL;
}
const AVLT::Element& AVLT::AVLTNode::Max()const{
const AVLTNode *t = this;
while (t->right)
t = t->right;
return t->data;
}
const AVLT::Element& AVLT::AVLTNode::Min()const{
const AVLTNode *t = this;
while (t->left)
t = t->left;
return t->data;
}
void AVLT::AVLTNode::nodeTraverseFrist(std::ostream& os)const{
os << this->data << ' ';
if (left)
this->left->nodeTraverseFrist();
if (right)
this->right->nodeTraverseFrist();
}
void AVLT::AVLTNode::nodeTraverseMid(std::ostream& os )const{
if (left)
this->left->nodeTraverseMid();
os << this->data << ' ';
if (right)
this->right->nodeTraverseMid();
}
void AVLT::AVLTNode::nodeTraverseLast(std::ostream& os )const{
if (left)
this->left->nodeTraverseLast();
if (right)
this->right->nodeTraverseLast();
os << this->data << ' ';
}
void AVLT::AVLTNode::nodeTraverselevel(std::ostream& os)const{
std::queue<AVLTNode> q;
q.push(*this);
while (!q.empty()){
AVLTNode p = q.front();
q.pop();
os << p.data << ' ';
if (p.left){
q.push(*(p.left));
}
if (p.right){
q.push(*(p.right));
}
}
}
const AVLT::AVLTNode & AVLT::AVLTNode::operator =(const AVLTNode &T){
if (Deepth == ){
Deepth = ;
data = T.data;
}
if (T.left){
if (left == NULL){
left = new AVLTNode;
}
*left = *T.left;
if (right){
Deepth = max(left->Deepth, right->Deepth) + ;
}
else{
Deepth = left->Deepth + ;
}
}
if (T.right){
if (right == NULL){
right = new AVLTNode;
}
*right = *T.right;
if (left){
Deepth = max(left->Deepth, right->Deepth) + ;
}
else{
Deepth = right->Deepth + ;
}
}
return *this;
}
void AVLT::AVLTNode::swapdata(AVLTNode&a, AVLTNode&b)const{
Element t;
t = a.data;
a.data = b.data;
b.data = t;
}
void AVLT::AVLTNode::SingleLeftRotation(){
AVLTNode *a = right;
right = a->right;
a->right = a->left;
a->left = left;
left = a;
if (a->right&&a->left){
a->Deepth = max(a->left->Deepth, a->right->Deepth) + ;
}
else
if (a->left){
a->Deepth = a->left->Deepth + ;
}
else{
a->Deepth = ;
}
swapdata(*this, *a);
}
void AVLT::AVLTNode::SingleRightRotation(){
AVLTNode *a = left;
left = a->left;
a->left = a->right;
a->right = right;
right = a;
if (a->right&&a->left){
a->Deepth = max(a->left->Deepth, a->right->Deepth) + ;
}
else
if (a->left){
a->Deepth = a->left->Deepth + ;
}
else{
a->Deepth = ;
}
swapdata(*this, *a);
}
void AVLT::AVLTNode::DoubleLeftRightRotation(){
this->left->SingleLeftRotation();
this->SingleRightRotation();
}
void AVLT::AVLTNode::DoubleRightLeftRotation(){
this->right->SingleRightRotation();
this->SingleLeftRotation();
}
inline void AVLT::AVLTNode::renewDeepth(){
Deepth = max(left ? left->Deepth : , right ? right->Deepth : ) + ;
}
inline int AVLT::AVLTNode::max(int a, int b)const{
return a > b ? a : b;
} AVLT::AVLT():node(NULL), number_of_Node(){
}
AVLT::AVLT(Element *arr, int size) : node(NULL), number_of_Node(){
node = new AVLTNode;
for (int i = ; i < size; i++)
this->Insect(arr[i]);
}
AVLT::AVLT(const AVLT &T) : node(NULL), number_of_Node(){
*this = T;
}
AVLT::~AVLT(){
delete node;
}
bool AVLT::empty()const{
return node == NULL;
}
const AVLT::Element& AVLT::Max()const{
return node->Max();
}
const AVLT::Element& AVLT::Min()const {
return node->Min();
}
const AVLT &AVLT::operator = (const AVLT&T){
delete node;
node = new AVLTNode;
number_of_Node = T.number_of_Node;
*node = *T.node;
return *this;
}
void AVLT::TraverseFrist(std::ostream& os )const{
if (node)
node->nodeTraverseFrist(os);
}
void AVLT::TraverseLast(std::ostream& os )const{
if (node)
node->nodeTraverseLast(os);
}
void AVLT::TraverseMid(std::ostream& os )const{
if (node)
node->nodeTraverseMid(os);
}
void AVLT::Traverselevel(std::ostream& os )const{
if (node)
node->nodeTraverselevel(os);
}
void AVLT::Insect(const AVLT::Element &e){
number_of_Node++;
if (node == NULL){
node = new AVLTNode;
}
node->nodeInsect(e);
}
bool AVLT::Delete(const AVLT::Element &e){
if (node){
if (node->isLeaf()){
delete node;
node = NULL;
}
else
node->nodeDelete(e);
number_of_Node--;
return true;
}
else{
return false;
}
}
int AVLT::Deepth(){
return node->Deepth;
}
int AVLT::Node(){
return number_of_Node;
}
const AVLT::AVLTNode*AVLT::find(const AVLT::Element &e)const {
if (node)
return node->Find(e);
else
return NULL;;
}
std::ostream& operator << (std::ostream& os, const AVLT& T){
T.TraverseFrist(os);
return os;
}
const AVLT& find();
这样看上去，AVL树似乎完胜普通的二叉查找树，但是现实是，坏的序列往往很少出现，很多时候，普通二叉树因为不需要判断平衡因子，旋转这些操作，效率反而更高，但是他一旦对上坏的序列就无计可施了，想能防住坏的序列，但又不想每次都旋转，于是就有伸展树这种数据结构，他只在坏的序列出现时旋转，但是只有“坏到一定
程度才旋转”，于是会出现比较坏但坏得不彻底的尴尬情况，伸展树无法保证每次操作都是O（log2N)，但是能保证M次操作时间复杂度为O（Mlog2N）。