首页 > 代码库 > 二叉树学习三：AVL树
二叉树学习三：AVL树
1、AVL树：
1）其左子树(TL)与右子树(TR)是AVL树；
2）|HL-HR|<=1，其中HL和HR是TL和TR的高度；
3）高度为h的AVL树，结点数2*h-1。
AVL树查找，插入，删除在平均和最坏情况下都是O(logn)，插入和删除可能需要一次或多次旋转重新达到平衡。AVL树的旋转平衡思路：以不平衡点为根的子树高度应保持不变，新结点插入后，向根回溯到第一个原平衡因 子不为0的结点。旋转方法如下：
1）LL型：左旋转
2）RR型：右旋转
3）LR型：在不平衡的儿结点先进行右旋转，然后进行左旋转。
4）RL型：在不平衡的儿结点先进行左旋转，然后里德右旋转
注意在旋转过程中涉及的最小树应该保持搜索二叉树的性质。
AVL树的C++实现核心部分是平衡旋转：
1 #include "stdafx.h" 2 #include<time.h> 3 #include<stdlib.h> 4 #include<iostream> 5 using namespace std; 6 7 typedef struct AVLTree{ 8 int ndata; 9 AVLTree* pLchild; 10 AVLTree* pRchild; 11 int nheight; 12 }AVLTree; 13 14 AVLTree* LLRotate(AVLTree* pRoot); 15 AVLTree* RRRotate(AVLTree* pRoot); 16 AVLTree* LRRotate(AVLTree* pRoot); 17 AVLTree* RLRotate(AVLTree* pRoot); 18 19 int Compare(int a,int b){ 20 return(a > b ? a : b); 21 } 22 int Height(AVLTree* pRoot){ 23 if (NULL==pRoot) 24 { 25 return -1; 26 } 27 else 28 { 29 return(pRoot->nheight); 30 } 31 } 32 33 AVLTree* Insert(AVLTree* pRoot, int nData){ 34 if (NULL==pRoot) 35 { 36 pRoot = new AVLTree; 37 pRoot->ndata =http://www.mamicode.com/ nData; 38 pRoot->nheight = 0; 39 pRoot->pLchild = NULL; 40 pRoot->pRchild = NULL; 41 } 42 else if (pRoot->ndata>nData) 43 { 44 pRoot->pLchild = Insert(pRoot->pLchild, nData); 45 if (Height(pRoot->pLchild) - Height(pRoot->pRchild)==2) 46 { 47 if (pRoot->pLchild->ndata>nData) 48 { 49 pRoot = LLRotate(pRoot); 50 } 51 else 52 { 53 pRoot = LRRotate(pRoot); 54 } 55 } 56 } 57 else if (pRoot->ndata<nData) 58 { 59 pRoot->pRchild = Insert(pRoot->pRchild, nData); 60 if (Height(pRoot->pRchild) - Height(pRoot->pLchild) == 2) 61 { 62 if (pRoot->pRchild->ndata<nData) 63 { 64 pRoot = RRRotate(pRoot); 65 } 66 else 67 { 68 pRoot = RLRotate(pRoot); 69 } 70 } 71 } 72 pRoot->nheight = Compare(Height(pRoot->pLchild), Height(pRoot->pRchild)) + 1; 73 return pRoot; 74 } 75 76 //LL旋转 77 AVLTree* LLRotate(AVLTree* pRoot){ 78 AVLTree* pTemp; 79 80 pTemp = pRoot->pLchild; 81 pRoot->pLchild = pTemp->pRchild; 82 pTemp->pRchild = pRoot; 83 84 pRoot->nheight = Compare(Height(pRoot->pLchild), Height(pRoot->pRchild)) + 1; 85 pTemp->nheight = Compare(Height(pTemp->pLchild), pRoot->nheight) + 1; 86 return pTemp; 87 } 88 89 //RR旋转 90 AVLTree* RRRotate(AVLTree* pRoot){ 91 AVLTree* pTemp; 92 93 pTemp = pRoot->pRchild; 94 pRoot->pRchild = pTemp->pLchild; 95 pTemp->pLchild = pRoot; 96 97 pRoot->nheight = Compare(Height(pRoot->pLchild), Height(pRoot->pRchild)) + 1; 98 pTemp->nheight = Compare(Height(pTemp->pRchild), pRoot->nheight) + 1; 99 return pTemp;100 }101 102 //LR旋转103 AVLTree* LRRotate(AVLTree* pRoot){104 pRoot->pLchild = RRRotate(pRoot->pLchild);105 return LLRotate(pRoot);106 }107 108 //RL旋转109 AVLTree* RLRotate(AVLTree* pRoot){110 pRoot->pRchild = LLRotate(pRoot->pRchild);111 return RRRotate(pRoot);112 }113 114 //输出树115 void PrintTree(AVLTree* pRoot){116 if (NULL==pRoot)117 {118 return;119 }120 static int n = 0;121 PrintTree(pRoot->pLchild);122 cout << ++n << "\t" << pRoot->ndata << "\t" << pRoot->nheight << "\n";123 PrintTree(pRoot->pRchild);124 }125 126 int main()127 {128 AVLTree* pRoot = NULL;129 srand((unsigned int)time(NULL));130 for (int i = 0; i < 10; i++)131 {132 pRoot = Insert(pRoot, rand() % 100);133 }134 PrintTree(pRoot);135 return 0;136 }
二叉树学习三：AVL树
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。