- AVL树
AVL树又称为高度平衡的二叉搜索树,是1962年有俄罗斯的数学家G.M.Adel'son-Vel'skii和E.M.Landis提出来的。它能保持二叉树的高度平衡,尽量降低二叉树的高度,减少树的平均搜索长度。
- AVL树的性质
- 左子树和右子树的高度之差的绝对值不超过1
- 树中的每个左子树和右子树都是AVL树
- 每个节点都有一个平衡因子(balance factor bf),任一节点的平衡因子是1,0,-1.(每个节点的平衡因子等于右子树的高度减去左子树的高度)
- AVL树的效率
一棵AVL树有N个节点,其高度可以保持在log2N,插入/删除/查找的时间复杂度也是log2N。
(ps:log2N是表示log以2为底N的对数,evernote不支持公式。)
//AVLTree.h #pragma once template<class K,class V> struct AVLTreeNode { AVLTreeNode<K,V>* _left; AVLTreeNode<K,V>* _right; AVLTreeNode<K,V>* _parent; K _key; V _value; int _bf; AVLTreeNode(const K& key,const V& value) :_left(NULL),_right(NULL),_parent(NULL),_key(key),_value(value),_bf(0) {} }; 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); } 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 { parent->_left = cur; cur->_parent = parent; } //更新平衡因子 while(parent) { //右孩子平衡因子加1,左孩子平衡因子减1 if(parent->_right == cur) parent->_bf ++; else if(parent->_left == cur) parent->_bf --; if(parent->_bf == 0) break; else if(parent->_bf == 1 || parent->_bf == -1) { cur = parent; parent = cur->_parent; } else //_bf = 2 || -2 { if(parent->_bf == 2) //parent->_bf == 2 { if(cur->_bf == 1) RotateL(parent); else //_bf = -1 RotateRL(parent); } else if(parent->_bf == -2) //parent->_bf == -2 { if(cur->_bf == -1) RotateR(parent); else //_bf = 1 RotateLR(parent); } return true; } } return true; } 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(ppNode == NULL) { _root = subR; subR->_parent = NULL; } else { if(ppNode->_left == parent) { ppNode->_left = subR; subR->_parent = ppNode; } else { ppNode->_right = subR; subR->_parent = ppNode; } } subR->_bf = parent->_bf = 0; } 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; //判断parent是否有父亲节点 if(ppNode == NULL) { _root = subL; subL->_parent = NULL; } else { if(ppNode->_left == parent) { ppNode->_left = subL; subL->_parent = ppNode; } else { ppNode->_right = subL; subL->_parent = ppNode; } } subL->_bf = parent->_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 == 1) { subR->_bf = 0; parent->_bf = -1; } else if(bf == -1) { parent->_bf = 0; subR->_bf = 1; } else { subR->_bf = parent->_bf = 0; } subRL->_bf = 0; } void RotateLR(Node* parent) { Node* subL = parent->_left; Node* subLR = subL->_right; int bf = subLR->_bf; RotateL(parent->_left); RotateR(parent); if(bf == 1) { subL->_bf = -1; parent->_bf = 0; } else if(bf == -1) { parent->_bf = 1; subL->_bf = 0; } else { subL->_bf = parent->_bf = 0; } subLR->_bf = 0; } void InOrder() { _InOrder(_root); cout<<endl; } int Height(Node* root) { if(root == NULL) { return 0; } int left = Height(root->_left); int right = Height(root->_right); return left > right ? (left+1) : (right+1); } bool IsBlance() { return _IsBlance(_root); } bool _IsBlance(Node* root) { if(root == NULL) { return true; } int left = Height(root->_left); int right = Height(root->_right); if((right-left) != root->_bf) { cout<<"平衡因子异常"<<root->_key<<endl; return false; } return abs(right-left < 2) && _IsBlance(root->_left) && _IsBlance(root->_right); } void _InOrder(Node* root) { if(root == NULL) { return; } _InOrder(root->_left); cout<<root->_key<<" "; _InOrder(root->_right); } protected: Node* _root; }; void TestTree() { AVLTree<int,int> tree; int a[]={16,3,7,11,9,26,18,14,15}; for(size_t i = 0; i < sizeof(a)/sizeof(a[0]); ++i) { tree.Insert(a[i],i); } tree.InOrder(); cout<<"Blance?"<<tree.IsBlance()<<endl; getchar(); } void TestTree1() { AVLTree<int,int> tree1; int array1[]={4,2,6,1,5,15,16,14}; for(size_t i = 0; i < sizeof(array1)/sizeof(array1[0]); ++i) { tree1.Insert(array1[i],i); } tree1.InOrder(); cout<<"Blance?"<<tree1.IsBlance()<<endl; getchar(); }
//Test.cpp #include<iostream> using namespace std; #include"AVLTree.h" int main() { //TestTree(); TestTree1(); getchar(); return 0; }