平衡二叉排序树——AVLTree
一颗平衡二叉排序树，要么是空树，要么是具有如下性质的二叉排序树：
- 左子树与右子树高度之差的绝对值小于等于1
- 左子树和右子树也是平衡二叉树
引入平衡二叉树的目的是提高查找效率，其平均查找长度为O(logn)
结点平衡因子（bf）定义为：结点左子树深度与右子树深度之差。（-1,0,1）
平衡二叉树的旋转方法有两种：LL型 与 RR型。
书上提到的 RL型 和 LR型 是可以通过LL型和RR型得到的。
可以参考 数据结构——用C语言描述 P286页 （讲的挺好的）
AVLTree的数据结构：
|
1 2 3 4 5 6 7 8 9 10 11 |
template<class T> class TreeNode { public: T data; //数据 int h; //高度 unsigned int freq;//频率——重复出现次数 TreeNode* lchild;//左孩子 TreeNode* rchild;//右孩子 TreeNode():lchild(NULL),rchild(NULL),freq(1),h(0){} }; |
AVLTree类的定义：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
template<class T> class AVLTree { public: AVLTree():root(),FR(){} //构造 void Insert(T x); //插入 bool Delete(T x); //删除 TreeNode <T> *Search(T x); //查找 void Traverse(); //遍历 void Clear(); //清空 bool Empty(); //判空 void Create(); //创建 private: TreeNode<T> *root; TreeNode<T> *FR; void Pri_Insert(TreeNode<T>* &root, T x, TreeNode<T>* &FR); //插入 bool Pri_Delete(TreeNode<T>* &root, T x, TreeNode<T>* &FR); //删除 TreeNode<T>* Pri_Search(TreeNode<T>* root,T x); //查找 void Pri_Clear(TreeNode<T>* &root); //清空 bool Pri_Empty(TreeNode<T>* root); //判空 void Pri_LDR(TreeNode<T>* root); //中序遍历 void Pri_RotateLL(TreeNode<T>* &A,TreeNode<T>* &FA); //LL型旋转 void Pri_RotateLR(TreeNode<T>* &A,TreeNode<T>* &FA); //LR型旋转 void Pri_RotateRL(TreeNode<T>* &A,TreeNode<T>* &FA); //RL型旋转 void Pri_RotateRR(TreeNode<T>* &A,TreeNode<T>* &FA); //RR型旋转 int Pri_Height(TreeNode<T>* root); //树的高度 int Pri_Bf(TreeNode<T>* root); //计算平衡因子 }; |
以上是头文件。
接下来是具体的实现。
首先是 LL RR LR RL 的实现. A是根结点，FA是根结点的父节点（看书…）
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 |
//LL型旋转 template <class T> void AVLTree<T>::Pri_RotateLL(TreeNode<T>* &A,TreeNode<T>* &FA) { //LL型旋转 TreeNode<T> *B = A->lchild; A->lchild = B->rchild; B->rchild = A; if(NULL==FA) { root = B; } else if(A == FA->lchild) { FA->lchild = B; } else { FA->rchild = B; } A->h = max( Pri_Height(A->lchild) , Pri_Height(A->rchild) )+1; B->h = max( Pri_Height(B->lchild) , Pri_Height(B->rchild) )+1; } //RR型旋转 template <class T> void AVLTree<T>::Pri_RotateRR(TreeNode<T>* &A,TreeNode<T>* &FA) { //RR型旋转 TreeNode<T> *B = A->rchild; A->rchild = B->lchild; B->lchild = A; if(NULL==FA) { root = B; } else if(A == FA->lchild) { FA->lchild = B; } else { FA->rchild = B; } A->h = max( Pri_Height(A->lchild) , Pri_Height(A->rchild) )+1; B->h = max( Pri_Height(B->lchild) , Pri_Height(B->rchild) )+1; } //LR型旋转 template <class T> void AVLTree<T>::Pri_RotateLR(TreeNode<T>* &A,TreeNode<T>* &FA) { //对左子树进行RR旋转 Pri_RotateRR(A->lchild,A); //对当前树进行LL旋转 Pri_RotateLL(A,FA); } //RL型旋转 template <class T> void AVLTree<T>::Pri_RotateRL(TreeNode<T>* &A,TreeNode<T>* &FA) { //对右子树进行LL旋转 Pri_RotateLL(A->rchild,A); //对当前子树进行RR旋转 Pri_RotateRR(A,FA); } |
插入函数：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 |
//插入 template <class T> void AVLTree<T>::Pri_Insert(TreeNode<T>* &root, T x ,TreeNode<T>* &FR) { //如果根节点为空，可以直接插入。 if(NULL == root) { root = new TreeNode<T>; root->data = x; return ; } //如果x比根结点的值大，插入到右边 if(root->data > x) { Pri_Insert(root->lchild,x,root); if(2 == Pri_Bf(root)) { if(x < root->lchild->data) Pri_RotateLL(root, FR); else Pri_RotateLR(root, FR); } } //如果x比根结点的值小，插入到左边 else if(root->data < x) { Pri_Insert(root->rchild, x, root); if(-2 == Pri_Bf(root)) { if(x > root->rchild->data ) Pri_RotateRR(root, FR); else Pri_RotateRL(root, FR); } } //相等的情况，频率 +1（完成排序） else { (root->freq) += 1; } //计算高度 root->h = max( Pri_Height(root->lchild) , Pri_Height(root->rchild) )+1; } |
删除函数：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 |
//删除 template <class T> bool AVLTree<T>::Pri_Delete(TreeNode<T>* &root, T x, TreeNode<T>* &FR) { //如果根结点为空，返回false if(NULL == root) { return false; } //如果 x 比根结点小，到左子树删除 if(x < root->data ) { bool bl = Pri_Delete(root->lchild,x,root); if(Pri_Bf(root) == -2) { if(Pri_Bf(root->rchild) == -1) { Pri_RotateRR(root,FR); } else if(Pri_Bf(root->rchild) == 1) { Pri_RotateRL(root,FR); } } return bl; } //如果 x 比根结点大，到右子树删除 else if(x > root->data) { bool bl = Pri_Delete(root->rchild,x,root); if(Pri_Bf(root) == 2) { if(Pri_Bf(root->lchild) == 1) { Pri_RotateLL(root,FR); } else if(Pri_Bf(root->lchild) == -1) { Pri_RotateLR(root,FR); } } return bl; } //当前节点就是要删除的 else { //有两个子节点 if(root->lchild && root->rchild) { //temp指向节点的右儿子 TreeNode<T>* temp = root->rchild; while(temp->lchild != NULL) { //找到右子树中值最小的节点 temp=temp->lchild; } //把右子树中最小节点的值赋值给本节点 root->data = temp->data; root->freq = temp->freq; //删除右子树中最小值的节点 Pri_Delete(root->rchild,temp->data,root); if(Pri_Bf(root->lchild)==1) { Pri_RotateLL(root,FR); } else if(Pri_Bf(root->lchild)==-1) { Pri_RotateLR(root,FR); } } //有1个或0个子节点 else { TreeNode<T>* temp = root; //有右儿子或者没有儿子 if(root->lchild == NULL) { root = root->rchild; } //有左儿子 else if(root->rchild == NULL) root = root->lchild; delete(temp); temp=NULL; } } //如果删除完后，根结点不为空，计算高度. //否则直接返回. if(NULL != root) root->h = max( Pri_Height(root->lchild) , Pri_Height(root->rchild) )+1; return true; } |
其他实现函数：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 |
//查找 template <class T> TreeNode<T>* AVLTree<T>::Pri_Search(TreeNode<T>* root,T x) { //如果根结点为空，则不存在 //否则递归查找 if(NULL == root) { return NULL; } if(root->data > x) { return Pri_Search(root->lchild,x); } else if(root->data < x) { return Pri_Search(root->rchild,x); } else return root; } //清空 template <class T> void AVLTree<T>::Pri_Clear(TreeNode<T>* &root) { //如果不为空，则删除左右子树，然后删除自身。 if(root) { if(root->lchild) Pri_Clear(root->lchild); if(root->rchild) Pri_Clear(root->rchild); delete(root); root = NULL; } } //判空 template <class T> bool AVLTree<T>::Pri_Empty(TreeNode<T>* root) { //判断根结点是否为空即可 return NULL==root; } //中序遍历 template <class T> void AVLTree<T>::Pri_LDR(TreeNode<T>* root) { if(NULL == root) return; //遍历 左中右 （中序） Pri_LDR(root->lchild); std::cout << root->data << " "; Pri_LDR(root->rchild); } //树的高度 template <class T> int AVLTree<T>::Pri_Height(TreeNode<T>* root) { //非空返回高度 , 空返回 -1 if(NULL != root) { return root->h; } else return -1; } //平衡因子 template <class T> int AVLTree<T>::Pri_Bf(TreeNode<T>* root) { if(NULL == root) return 0; return Pri_Height(root->lchild) - Pri_Height(root->rchild); } |
接口的实现：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 |
//插入 template <class T> void AVLTree<T>::Insert(T x) { Pri_Insert(root,x,FR); } //删除 template <class T> bool AVLTree<T>::Delete(T x) { return Pri_Delete(root,x,FR); } //查找 template <class T> TreeNode <T>* AVLTree<T>::Search(T x) { return Pri_Search(root,x); } //遍历 template <class T> void AVLTree<T>::Traverse() { Pri_LDR(root); std::cout << std::endl; } //清空 template <class T> void AVLTree<T>::Clear() { Pri_Clear(root); } //判空 template <class T> bool AVLTree<T>::Empty() { return Pri_Empty(root); } //创建 template <class T> void AVLTree<T>::Create() { T temp; while(cin >> temp) { Pri_Insert(root,temp,FR); } } |
测试 main 函数：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 |
int main() { AVLTree<int> tree; tree.Clear(); tree.Create(); tree.Insert(1); TreeNode <int> *s = tree.Search(2); if(s!=NULL) { cout << s->data << endl; } else{ cout << "Not Exist" << endl; } if(tree.Empty()) { cout << "Empty" << endl; } else { cout << "Not Empty" << endl; } if(tree.Delete(3)) { cout << "Delete Success" << endl; } else { cout << "Not Exist" << endl; } tree.Traverse(); tree.Clear(); } |
先这样存着吧…难…敲了一天…
【Search】【Sort】平衡二叉排序树——AVLTree