数据结构之AVL树

之前的博客，实现了数据结构中最基本的树形结构——二叉搜索树，下一步实现AVL树。这真的是很头疼的一颗树，无论是插入还是删除，都得分多种情况来讨论，其中的控制逻辑很繁琐。在编写代码之前，首先要想清楚在插入和删除的时候各个分支到底怎么处理，然后去编写代码。起码我现在看这部分内容，还是十分拧巴。多看看的话，应该会熟悉一点吧。

首先编写test.h:

#include<iostream> #include<stack> #include<assert.h> using namespace std; template<class Type> class AVLTree; template<class Type> class AVLNode { friend class AVLTree<Type>; public: AVLNode() : data(Type()), leftChild(NULL), rightChild(NULL),bf(0) {} AVLNode(Type d, AVLNode<Type>*left=NULL, AVLNode<Type>*right=NULL) :data(d), leftChild(left), rightChild(right),bf(0) {} ~AVLNode() {} public: Type GetData()const {return data;} AVLNode<Type>* GetLeftChild()const {return leftChild;} AVLNode<Type>* GetRightChild()const {return rightChild;} public: void SetData(Type d) {data = d;} void SetLeftChild(AVLNode<Type> *left) {leftChild = left;} void SetRightChild(AVLNode<Type> *right) {rightChild = right;} private: Type data; AVLNode<Type> *leftChild; AVLNode<Type> *rightChild; int bf; }; template<class Type> class AVLTree { public: AVLTree() : root(NULL) {} public: bool Insert(const Type &x) { return Insert(root, x); } bool Remove(const Type &x) { return Remove(root, x); } protected: //bool Remove(AVLNode<Type> *&t, const Type &x); bool Remove(AVLNode<Type> *&t, const Type &x) { AVLNode<Type> *pr = NULL, *p = t, *q, *ppr; int d, dd = 0; stack<AVLNode<Type>*> st; while (p != NULL) { if (x == p->data) break; pr = p; st.push(pr); if (x < p->data) { p = p->leftChild; } else { p = p->rightChild; } } if(p == NULL) return false; if (p->leftChild != NULL && p->rightChild != NULL) { pr = p;st.push(pr); q = p->leftChild; while (q->rightChild != NULL) { pr = q;st.push(pr); q = q->rightChild; } p->data = q->data; p = q; } if(p->leftChild != NULL) q = p->leftChild; else q = p->rightChild; if(pr == NULL) t = q; else{ if(pr->leftChild == p) pr->leftChild = q; else pr->rightChild = q; while(st.empty() == false) { st.pop(); if(pr->rightChild == q) pr->bf--; else pr->bf++; if(st.empty() == false) { ppr = st.top(); dd = (ppr->leftChild == pr) ? -1 : 1; } else dd = 0; if(pr->bf == 1 || pr->bf == -1) break; if(pr->bf != 0) { if(pr->bf < 0){d = -1; q = pr->leftChild;} else{d = 1; q = pr->rightChild;} if(q->bf == 0) { if(d == -1) {RotateR(pr);pr->bf = 1; pr->leftChild->bf = -1;} else{RotateL(pr); pr->bf = -1; pr->rightChild->bf = 1;} break; } if(q->bf == d) { if(d == -1) RotateR(pr); else RotateL(pr); } else { if(d == -1) RotateLR(pr); else RotateRL(pr); } if(dd == -1) ppr->leftChild = pr; else if(dd == 1) ppr->rightChild = pr; } q = pr; } if(st.empty() == true) t = pr; } delete p ;return true; } bool Insert(AVLNode<Type> *&t, const Type &x) { AVLNode<Type> *pr = NULL; AVLNode<Type> *p = t; stack<AVLNode<Type>*> st; while(p != NULL) { if(x == p->data) return false; pr = p; st.push(pr); if(x < p->data) p = p->leftChild; else p = p->rightChild; } p = new AVLNode<Type>(x); if(pr == NULL) { t = p; return true; } if(p->data < pr->data) pr->leftChild = p; else pr->rightChild = p; while(!st.empty()) { pr = st.top(); st.pop(); if(pr->leftChild == p) pr->bf--; else pr->bf++; if(pr->bf == 0) break; else if(pr->bf==1 || pr->bf==-1) p = pr; else { if(pr->bf < 0) { if(p->bf < 0) // / { RotateR(pr); } else // < { RotateLR(pr); } } else { if(p->bf > 0) // \ { RotateL(pr); } else // > { RotateRL(pr); } } break; } } if(st.empty()) t = pr; else { AVLNode<Type> *q = st.top(); if(q->data > pr->data) q->leftChild = pr; else q->rightChild = pr; } return true; } protected: void RotateR(AVLNode<Type> *& ptr) { AVLNode<Type> *subR = ptr; ptr = subR->leftChild; subR->leftChild = ptr->rightChild; ptr->rightChild = subR; ptr->bf = subR->bf = 0; } void RotateL(AVLNode<Type> *& ptr) { AVLNode<Type> *subL = ptr; ptr = subL->rightChild; subL->rightChild = ptr->leftChild; ptr->leftChild = subL; ptr->bf = subL->bf = 0; } void RotateLR(AVLNode<Type> *& ptr) { AVLNode<Type>*subR = ptr; AVLNode<Type>*subL = ptr->leftChild; ptr = subL->rightChild; //左转 subL->rightChild = ptr->leftChild; ptr->leftChild = subL; if(ptr->bf <= 0) subL->bf = 0; else subL->bf = -1; subR->leftChild = ptr->rightChild; ptr->rightChild = subR; if(ptr->bf >= 0) subR->bf = 0; else subR->bf = 1; ptr->bf = 0; } void RotateRL(AVLNode<Type> *& ptr) { AVLNode<Type> *subL = ptr; AVLNode<Type> *subR = ptr->rightChild; ptr = subR->leftChild; subR->leftChild = ptr->rightChild; ptr->rightChild = subR; if(ptr->bf >= 0) subR->bf = 0; else subR->bf = 1; subL->rightChild = ptr->leftChild; ptr->leftChild = subL; if(ptr->bf == 1) subL->bf = -1; else subL->bf = 0; ptr->bf = 0; } private: AVLNode<Type> *root; };

测试程序test.cpp:

#include"Test.h" void main() { int ar[] = {16,3,7,11,9,26,18,14,15}; int n = sizeof(ar) / sizeof(int); AVLTree<int> avl; for(int i=0; i<n; ++i) { avl.Insert(ar[i]); } avl.Remove(11); return; }

我的笔记本上有三个C++的编译器，分别是年代很久远的VC++6.0，clion,codeblocks,后面两个都是gcc的编译器。我本人比较偏爱cb,但是它在调试查看变量反面实在是短板，前面两个表现都不错，值得表扬。我就在想是不是cb的设置有问题呢？

AVL树真的很难啊。。。