平衡搜索树-AVLTree

AVL树

又称为高度平衡的二叉搜索树。它能保持二叉树的高度平衡，尽量降低二叉树的高度，减少树的平均搜索长度。

AVL树的性质

1. 左子树和右子树的高度之差的绝对值不超过1
2. 树中的每一个左子树和右子树都是AVL树
3. 每个节点都有一个平衡因子，任一节点的平衡因子是-1或0或1.（每个节点的平衡因子等于右子树的高度减去左子树的高度，即：bf = rightHeigh - leftHeight）

AVL树的效率

一颗AVL树有N个节点，其高度可以保持在log2N（表示log以2为底N的对数），插入/删除/查找的时间复杂度也是log2N.

更新平衡因子

1. cur在parent左，p bf - -
2. cur在parent 右，p bf++
   
   • p == 0；p树高度不变
   • |p| == 1;高度变了，继续更新
   • |p| == 2；不再更新，旋转平衡起来

插入

1. 右单旋转—— RotateR
2. 左单旋转—— RotateL
3. 右左双旋转— RotateRL
4. 左右双旋转— RotateLR

右单旋转

void RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if(subLR)subLR->_parent = parent;subL->_right = parent;Node* ppNode = parent->_parent ;parent->_parent = subL;if(parent == _root){_root = subL;_root->_parent = NULL;}else{if(ppNode->_left == parent){ppNode->_left = subL;}else{ppNode->_right = subL;}subL->_parent = ppNode;}parent->_bf = subL->_bf = 0;}

左单旋转

void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if(subRL)subRL->_parent = parent;subR->_left = parent;Node* ppNode = parent->_parent ;parent->_parent = subR;if(parent == _root){_root = subR;_root->_parent = NULL;}else{if(ppNode->_right == parent) {ppNode->_right = subR;}else{ppNode->_left = subR;}subR->_parent = ppNode;}parent->_bf = subR->_bf = 0;}

右左双旋转

void RotateRL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;int bf = subRL->_bf;RotateR(parent->_right);RotateL(parent);if(bf == 0){subR->_bf = parent->_bf = subRL->_bf = 0;}else if(bf == 1){parent->_bf = -1;subR->_bf = 0;subRL->_bf = 0;}else{parent->_bf = 0;subR->_bf = 1;subRL->_bf = 0;}}

左右双旋转

左右的图和右左图类似

 void RotateLR(Node* parent)   //左右双旋 {  Node* subL = parent->_left;  Node* subLR = subL->_right;  int bf = subLR->_bf;  RotateL(subL);  RotateR(parent);  if (bf == 0)  parent->_bf =subLR->_bf= subL->_bf = 0;  else if (bf == 1)  {  parent->_bf = subLR->_bf = 0;  subL->_bf = -1;  }  else if (bf == -1)  {  parent->_bf = 1;  subL->_bf = subLR->_bf = 0;  }  }  

判断是不是平衡二叉树：

具体代码实现看这篇文章：
https://blog.csdn.net/qq_37941471/article/details/79748878

代码实现：

• AVLTree.h
• test.cpp

AVLTree.h

//#pragma once
#include <iostream>
using namespace std;template<class K,class V>
struct AVLTreeNode
{K _key;V _value;int _bf;AVLTreeNode<K,V>* _left;AVLTreeNode<K,V>* _right;AVLTreeNode<K,V>* _parent;AVLTreeNode(const K& key,const V& value):_key(key),_value(value),_bf(0),_left(NULL),_right(NULL),_parent(NULL){}
};template<class K,class V>
class AVLTree
{typedef AVLTreeNode<K,V> Node;
public:AVLTree():_root(NULL){}//插入bool Insert(const K& key,const V& value){if(_root == NULL){_root = new Node(key,value);return true;}Node* cur = _root;Node* parent = NULL;while(cur){if( cur->_key < key)//根 < 插入的节点{parent = cur;cur = cur->_right;}else if( cur->_key > key){parent = cur;cur = cur->_left ;}else{return false;}}cur = new Node(key,value);if(parent->_key < key){parent->_right = cur;cur->_parent = parent;}else if(parent->_key > key){parent->_left = cur;cur->_parent = parent;}//更新平衡因子 //1.cur在parent左，p bf-- //2.cur在parent 右，p bf++//p == 0；p树高度不变//|p| == 1;高度变了，继续更新//|p| == 2；不再更新，旋转平衡起来while(parent){if(cur == parent->_left){parent->_bf--;}else{parent->_bf++;}if(parent->_bf == 0){break;}else if(parent->_bf == 1 || parent->_bf == -1){//从树下往上更新cur = parent;parent = cur->_parent;}else if(parent->_bf == -2 || parent->_bf == 2){if(parent->_bf == 2){if(cur->_bf == 1){RotateL(parent);}else //-1{RotateRL(parent);}}else // -2{if(cur->_bf == -1){RotateR(parent);}else // 1{RotateLR(parent);}}}break;}}void InOrder(){_InOrder(_root);cout<<endl;}void _InOrder(Node* root)//中序遍历 左中右{if(root == NULL)return;_InOrder(root->_left);cout<<root->_key<<" ";_InOrder(root->_right);}
//右单旋转void RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if(subLR)subLR->_parent = parent;subL->_right = parent;Node* ppNode = parent->_parent ;parent->_parent = subL;if(parent == _root){_root = subL;_root->_parent = NULL;}else{if(ppNode->_left == parent){ppNode->_left = subL;}else{ppNode->_right = subL;}subL->_parent = ppNode;}parent->_bf = subL->_bf = 0;}//左单旋转void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if(subRL)subRL->_parent = parent;subR->_left = parent;Node* ppNode = parent->_parent ;parent->_parent = subR;if(parent == _root){_root = subR;_root->_parent = NULL;}else{if(ppNode->_right == parent) {ppNode->_right = subR;}else{ppNode->_left = subR;}subR->_parent = ppNode;}parent->_bf = subR->_bf = 0;}//右左双旋转void RotateRL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;int bf = subRL->_bf;RotateR(parent->_right);RotateL(parent);if(bf == 0){subR->_bf = parent->_bf = subRL->_bf = 0;}else if(bf == 1){parent->_bf = -1;subR->_bf = 0;subRL->_bf = 0;}else{parent->_bf = 0;subR->_bf = 1;subRL->_bf = 0;}}//左右双旋转void RotateLR(Node* parent)   //左右双旋 {  Node* subL = parent->_left;  Node* subLR = subL->_right;  int bf = subLR->_bf;  RotateL(subL);  RotateR(parent);  if (bf == 0)  parent->_bf =subLR->_bf= subL->_bf = 0;  else if (bf == 1)  {  parent->_bf = subLR->_bf = 0;  subL->_bf = -1;  }  else if (bf == -1)  {  parent->_bf = 1;  subL->_bf = subLR->_bf = 0;  }  }  //判断是不是平衡搜索树//1. 递归——时间复杂度n^2// （递归的次数*每次递归的次数）// 每个节点的遍历*高度（也是遍历整个树）//bool IsBalance() //{ // int depth = 0;// return _IsBalance(_root); //} //int MaxDepth(Node* root) //{ //if (NULL == root) // return 0; //int left = MaxDepth(root->_left)+1; //int right = MaxDepth(root->_right) + 1; //return left > right ? left : right; //} //bool _IsBalance(Node* root)//{
    // //递归的终止条件// if(root == NULL)// {
    // return true;// }// int leftHeight = MaxDepth(root->_left);// int rightHeight = MaxDepth(root->_right);// return abs(rightHeight-leftHeight) < 2// && _IsBalance(root->_left)// && _IsBalance(root->_right);//}//2. 优化——时间复杂度O(n)——高度只遍历一次bool IsBalance() {  int depth = 0;return _IsBalance(_root,depth);  } bool _IsBalance(Node* root,int& depth){if(root == NULL){return true;}int left = 0;int right = 0;if(_IsBalance(root->_left,left)&&_IsBalance(root->_right,right)){if( abs(left-right) > 1 )return false;depth = (left > right ? left : right)+1;return true;}return false;}/* bool _IsBalance(Node* root,int& depth) { if(root == NULL){depth = 0;return true;}int leftdepth = 0;int rightdepth = 0;if(_IsBalance(root->_left,leftdepth) == false)return false;if(_IsBalance(root->_right,rightdepth) == false)return false;if(rightdepth - leftdepth != root->_bf){cout << root->_key << "平衡因子异常" << endl; return false; }depth = leftdepth > rightdepth ? leftdepth+1 : rightdepth+1;} */
private:Node* _root;
};

test.cpp

#include "AVLTree.h"void testAVLTree()
{AVLTree<int, int> t;  int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };int depth = 0;for (size_t i = 0; i < sizeof(a) / sizeof(a[0]); i++)  {  t.Insert(a[i], i);  cout << "isbalance?"<<t.IsBalance() <<"插入"<< a[i] << endl;  }  t.InOrder();  t.IsBalance();  AVLTree<int, int> t1;  int a1[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };  for (size_t i = 0; i < sizeof(a1) / sizeof(a1[0]); i++)  {  t1.Insert(a1[i], i);  cout << "isbalance?" << t1.IsBalance() << "插入" << a1[i] << endl;  }  t1.InOrder();  
}int main()
{testAVLTree();return 0;
}