AVL树
AVL树又称为高度平衡的二叉搜索树，是1962年有俄罗斯的数学家G.M.Adel'son-Vel'skii和E.M.Landis提出来的。它能保持二叉树的高度 平衡，尽量降低二叉树的高度，减少树的平均搜索长度AVL树的性质
1. 左子树和右子树的高度之差的绝对值不超过1
2. 树中的每个左子树和右子树都是AVL树
3. 每个节点都有一个平衡因子(balance factor--bf),任一节点的平衡因子是-1,0,1。(每个节点的平衡因子等于右子树的高度减去左子 树的高度 )
AVL树的效率
一棵AVL树有N个节点，其高度可以保持在log2N，插入/删除/查找的时间复杂度也是log2N。
当出现不平衡的情况时的四种情况：
1.只需要右旋（汉子笔画为一“撇”），无论在黄（son）的左边插入还是右边插入，红（grandparent）的平衡因子，绿（parent）的平衡因子总能保持为0；
2.只需要左旋（汉子笔画为一“捺”）与情况1类似，此处就不再累赘；
3.左右旋（汉字笔画为一“撇”，一“捺”）
（1）绿的平衡因子为 0。有且只有一种可能；
（2）绿的平衡因子为-1。在绿（son）的左边插入，红（grandparent）的平衡因子为1，黄（parent）的平衡因子为0，绿（son）的平衡因子为0；
（3）绿的平衡因子为1。在绿（son）的右边插入，红（grandparent）的平衡因子为0，黄（parent）的平衡因子为-1，绿（son）的平衡因子为0；
4.右左旋（汉字笔画为一“捺”，一“撇”），情况与左右旋类似；
Now 图画完了~~ 大体思想了解了 闲话就不多叙述了--直接上代码
//AVLTree 的节点类
template<class K,class V>
struct AVLTreeNode
{
typedef AVLTreeNode<K, V> Node;
AVLTreeNode(const K& key, const V& value)
:_left(NULL), _right(NULL), _parent(NULL)
, _balance(), _key(key), _value(value)
{} Node * _left;
Node * _right;
Node * _parent;
int _balance;
K _key;
V _value;
};
//AVLTree （这个就是AVLTree 的类）
template<class K,class V>
class AVLTree
{
typedef AVLTreeNode<K, V> Node;
public:
AVLTree()
:_root(NULL)
{}
public:
//增加节点
bool _Push(const K& key, const V& value);
void _LeftSpin(Node *& parent);
void _RightSpin(Node * & parent);
void _LeftRightSpin(Node *& _RightSpinparent);
void _RightLeftSpin(Node *& parent); //查找结点
Node* _Find(const K& key); //修改节点
bool _Change(const K& key,const V& value); //检测
void _LevelOrder();
void _InOrder(){ InOrder(_root); }
int _Depth(){ Depth(_root); }
void InOrder(Node * root);
int Depth(Node * root);
protected:
Node * _root;
};
//AVLTree的构建
//增加节点
template<class K,class V>
bool AVLTree<K, V>::_Push(const K& key, const V& value)
{
if (_root == NULL)
{
_root = new Node(key, value);
return true;
}
else //如果要根节点不为空
{
Node * insert = new Node(key, value);
Node * cur = _root;
Node * parent = NULL;
while (cur) //找插入的位置
{
parent = cur;
if (key > cur->_key)
{
cur = cur->_right;
}
else if (key < cur->_key)
{
cur = cur->_left;
}
else
{
return false;
}
}
if (key > parent->_key) //将该节点插入到parent的右边
{
parent->_right = insert;
insert->_parent = parent;
}
else //将该节点插入到parent的左边
{
parent->_left = insert;
insert->_parent = parent;
}
cur = insert; //cur指向新插入的节点
while (parent) //向上调节平衡因子
{
if (cur->_key > parent->_key)
{
parent->_balance++;
}
else
{
parent->_balance--;
}
if (parent->_balance == || parent->_balance == || parent->_balance == -) //当_balance == 0 说明已经平衡了。_balance == 2 || _balance == -2 说明需要调整了
{
break;
}
cur = parent;
parent = cur->_parent;
} if (parent && (parent->_balance == || parent->_balance == -)) //如果_balance == 2 || _balance == -2
{
if (parent->_balance == )
{
if (cur->_balance == )
{
_LeftSpin(parent); //上面的情况2
}
else
{
_RightLeftSpin(parent); //上面的情况4 }
}
else if(parent->_balance == -)
{
if (cur->_balance == -) {
_RightSpin(parent); //上面的情况1
}
else
{
_LeftRightSpin(parent); //上面的情况3 }
}
}
return true;
}
}
//左旋（按照上面的来敲带码，其实是很简单滴）
template<class K, class V>
void AVLTree<K, V>::_LeftSpin(Node *& parent)
{
Node* son = parent->_right;
Node* grandparent = parent->_parent; parent->_right = son->_left;
if (son->_left)
{
son->_left->_parent = parent;
}
son->_left = parent;
parent->_parent = son; son->_parent = grandparent;
if (grandparent)
{
if (parent->_key > grandparent->_key)
{
grandparent->_right = son;
}
else
{
grandparent->_left = son;
}
} parent->_balance = ; //将平衡因子置为零
son->_balance = ; if (_root == parent)
{
_root = son;
}
parent = son;
}
//左右旋
template<class K, class V>
void AVLTree<K, V>::_LeftRightSpin(Node *& parent)
{
Node * son = parent->_left;
bool left = false;
bool right = false;
if (son->_right->_balance == -) //如图，如果son 的 balance == -1 调整好后 grandparent 的 平衡因子为 1；即 (当前parent->right == 1);
{
left = true;
}
else if (son->_right->_balance == ) //如图，如果 son 的 balance == 1 调整好后 parent 的 平衡因子为 -1；即（当前parent->left == -1）;
{
right = true;
}
_LeftSpin(son); //（这里有一个坑：参数传的是引用，所以实参不能传(grandparent->_left)否则就会有神奇的事情发生^_^ ~~ 这里要小心再小心！！！前车之鉴呀大兄弟）
_RightSpin(parent);
if (left)
{
parent->_right->_balance = ;
}
else if (right)
{
parent->_left->_balance = -;
}
}