赞
踩
AVL树全称高度平衡二叉树,它是一种优化了的搜索二叉树。我们知道,由于搜索二叉树存在缺陷,有可能退化成单链,这样的话搜索效率就降低了。为了将二叉搜索树的效率控制在O(logN),所以对二叉搜索树加上一些条件,使得二叉搜索树高度平衡,时间复杂度为O(log N).
一 定义:
1.首先AVL树是一个二叉搜索树
2.它的左子树,右子数都是AVL树
3.它的左子树和右子数的高度差不超过1.(通常情况下,为每个结点都加一个平衡因子bf,这个平衡因子是右子树的高度减去左子树高度)
二 平衡化旋转
如果一棵树原来是平衡的二叉搜索树,现在向里面添加一个结点。造成了不平衡。这时候我们就要调整这棵树的结构,使之重新平衡。以下是造成树不平衡的结构有哪些,以及如何调整。
下面关于平衡的几点,需要注意:
1.所有的插入都是建立在平衡二叉树的基础上的
2.如果插入一个结点,树的高度不变,则它就是平衡的
3.插入之后会影响从插入点到根节点路径上结点的平衡因子
- #include<iostream>
- #include<assert.h>
- using namespace std;
- template<class V>
- struct AVLTreeNode
- {
- V _value;
- int _bf;//平衡因子右子树的高度减去左子树的高度
- AVLTreeNode< V>* _left;
- AVLTreeNode< V>* _right;
- AVLTreeNode< V>* _parent;
- AVLTreeNode( const V& value)
- :_value(value)
- , _bf(0)
- , _left(NULL)
- , _right(NULL)
- , _parent(NULL)
- {}
-
- };
- template<class V>
- class AVLTree
- {
- typedef AVLTreeNode< V> Node;
- public:
- AVLTree()
- :_root(NULL)
- {}
- AVLTree(const AVLTree< V>& t)
- {
- _root = _Copy(t._root);
- }
-
- AVLTree< V>& operator=(const AVLTree< V>& t)//现代写法
- {
- if (this != &t)
- {
- AVLTree<K, V> tmp(t);
- swap(tmp._root, _root);
- }
- return *this;
- }
- /*AVLTree< V>& operator=(const AVLTree< V> t)
- {
- swap(_root, t._root);
- return *this;
- }*/
- ~AVLTree()
- {
- _Destory(_root);
- }
- bool Isbalance()
- {
- //return _Isbalance(_root);
- int height = 0;
- return _IsbalanceOP(_root, height);
- }
- bool Insert( V& value)
- {
- Node* cur = _root;
- Node* parent = NULL;
- if (_root == NULL)
- {
- _root = new Node( value);
- return true;
- }
- while (cur)
- {
- if (cur->_value < value)
- {
- parent = cur;
- cur = cur->_right;
- }
- else if (cur->_value>value)
- {
- parent = cur;
- cur = cur->_left;
- }
- else
- {
- return false;
- }
- }
- cur = new Node(value);
- if (parent->_value>value)
- {
- parent->_left = cur;
- cur->_parent = parent;
- }
- else
- {
- parent->_right = cur;
- cur->_parent = parent;
- }
- while (parent)//更新平衡因子
- {
- if (parent->_left ==cur)
- {
- parent->_bf--;
- }
- else
- {
- parent->_bf++;
- }
- if (parent->_bf == 0)//当父亲结点的平衡因子为0,说明插入之后树高度不变仍然平衡
- {
- return true;
- }
- else if (parent->_bf == 1 || parent->_bf == -1)//本次不违反规则,但是会影响根节点到parent路径上其他结点的平衡,因此继续向上更新
- {
- cur = parent;
- parent = parent->_parent;
- }
- else if (parent->_bf == 2 || parent->_bf == -2)//已经违反平衡规则,不再更新,直接旋转
- {
-
- if (parent->_bf == 2)
- {
- if (cur->_bf == 1)
- {
- _RotateL(parent);
- return true;
- }
- else
- {
- _RotateRL(parent);
- return true;
- }
- }
- if (parent->_bf == -2)
- {
- if (cur->_bf == -1)
- {
- _RotateR(parent);
- return true;
-
- }
- else
- {
- _RotateLR(parent);
- return true;
- }
- }
- }
-
- }
- return true;
- }
- void _RotateR(Node* parent)
- {
- assert(parent);
- Node* SubL = parent->_left;
- Node* SubLR = SubL->_right;
- Node* ppNode = parent->_parent;
- parent->_left = SubLR;
- if (SubLR)
- {
- SubLR->_parent = parent;
- }
- SubL->_right = parent;
- parent->_parent = SubL;
- if (ppNode==NULL)
- {
- _root = SubL;
- SubL->_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)
- {
- assert(parent);
- Node* SubR = parent->_right;
- Node* SubRL = SubR->_left;
- Node* ppNode = parent->_parent;
- parent->_right = SubRL;
- if (SubRL)
- {
- SubRL->_parent = parent;
- }
-
- SubR->_left = parent;
- parent->_parent = SubR;
- if (ppNode == NULL)
- {
- _root = SubR;
- SubR->_parent = NULL;
- }
- else
- {
- if (ppNode->_left == parent)
- {
- ppNode->_left = SubR;
- }
- else
- {
- ppNode->_right = SubR;
- }
- SubR->_parent = ppNode;
- }
- parent->_bf = SubR->_bf = 0;
-
- }
- void _RotateLR(Node *parent)
- {
- Node* SubL = parent->_left;
- Node* SubLR = SubL->_right;
- int bf = SubLR->_bf;//计算旋转以后的根节点的bf
- _RotateL(SubL);
- _RotateR(parent);
- //如果bf为0,代表插入点就是这个结点,这个时候所有旋转后bf皆为0
- if (bf == 0)
- {
- SubL->_bf = parent->_bf = 0;
- SubLR->_bf = 0;
- }
- //当bf为1时,这个时候相当于是在给bf的右树插入,
- else if (bf == -1)
- {
- SubL->_bf = -1;
- parent->_bf = 0;
- SubLR->_bf = 0;
- }
- //当bf为-1时,这时相当于给bf的左树进行插入
- else
- {
- SubL->_bf = 0;
- parent->_bf = 1;
- SubLR->_bf = 0;
- }
-
- }
- void _RotateRL(Node* parent)
- {
- Node*SubR = parent->_right;
- Node*SubRL = SubR->_left;
- int bf = SubRL->_bf;
- _RotateR(SubR);
- _RotateL(parent);
- if (bf == 0)
- {
- parent->_bf = SubR->_bf = 0;
- 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;
-
- }
- }
- size_t Height()
- {
- return _Height(_root);
- }
- void Inorder()
- {
- _Inorder(_root);
- cout << endl;
- }
- protected:
- void _Inorder(Node* Root)
- {
- if (Root == NULL)
- {
- return;
- }
- else
- {
- _Inorder(Root->_left);
- cout << Root->_value<<" ";
- _Inorder(Root->_right);
- }
- }
- size_t _Height(Node* Root)
- {
- if (Root == NULL)
- {
- return 0;
- }
- else
- {
- int leftheight = _Height(Root->_left);
- int rightheight = _Height(Root->_right);
- return leftheight > rightheight ? leftheight + 1 : rightheight + 1;
- }
- }
- Node* _Copy(Node* Root)
- {
- Node* tmp = NULL;
-
- if (Root!=NULL)
- {
- tmp = new Node(Root->_value);
- tmp->_left = _Copy(Root->_left);
- tmp->_right = _Copy(Root->_right);
- }
- return tmp;
- }
- Node* _Destory(Node* Root)
- {
-
- if (Root != NULL)
- {
- Root->_left = _Destory(Root->_left);
- Root->_right = _Destory(Root->_right);
- delete Root;
- Root = NULL;
- }
- return Root;
- }
- bool _Isbalance(Node* Root)//时间复杂度为n^2
- {
- if (Root == NULL)
- {
- return true;
- }
- int LeftHeight = _Height(Root->_left)+1;
- int RightHeight = _Height(Root->_right)+1;
- int sub = abs(RightHeight - LeftHeight);
- return ((sub < 2) && (_Isbalance(Root->_left)) && (_Isbalance(Root->_right)));
- }
- bool _IsbalanceOP(Node* Root, int& height)
- {
- if (Root == NULL)
- {
- height = 0;
- return true;
- }
- //记录左结点和右结点高度
- int LeftHeight = 0;
- int RightHeight = 0;
- if (_IsbalanceOP(Root->_left, LeftHeight) == false)
- {
- return false;
- }
- if (_IsbalanceOP(Root->_right, RightHeight) == false)
- {
- return false;
- }
- height = LeftHeight > RightHeight ? LeftHeight + 1 : RightHeight + 1;
- return abs(RightHeight - LeftHeight) < 2;
- }
- private:
- Node* _root;
-
- };
- void TestAVLTree()
- {
- //int a1[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
- int a1[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
- AVLTree<int>t;
- for (size_t i = 0; i < sizeof(a1) / sizeof(a1[0]); i++)
- {
- t.Insert(a1[i]);
- cout <<a1[i]<<" "<< t.Isbalance() << endl;
- }
- t.Inorder();
- cout << t.Isbalance() << endl;
- AVLTree<int>t1(t);
- t1.Inorder();
-
-
- }
- int main()
- {
- TestAVLTree();
- system("pause");
- return 0;
- }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。