【数据结构】AVL树

1、AVL树简介

????? AVL树本质上还是一棵二叉搜索树，又称高度平衡的二叉搜索树。它能保持二叉树的高度平衡，尽量降低二叉树的高度，减少树的平均搜索长度。对于二叉搜索树的介绍和实现，可查看本人上一篇博客。

2、AVL树的特点

1）本身首先是一棵二叉搜索树。?

2）带有平衡条件：每个结点的左右子树的高度之差的绝对值（平衡因子）最多为1。

3）树中的每个左子树和右子树都是AVL树。

4）每个结点都有一个平衡因子，任一结点的平衡因子是-1,1.

注：结点的平衡因子 = 右子树高度 - 左子树高度

3、AVL树的效率

一棵AVL树有N个结点，其高度可以保持在lgN，插入/删除/查找的时间复杂度也是lgN。

AVL树的复杂程度真是比二叉搜索树高了整整一个数量级――它的原理并不难弄懂，但要把它用代码实现出来还真的有点费脑筋。下面我们来看看AVL树实现的接口，通过三叉链进行结点的实现。

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?=?K(),?const?V&?value?=?V())//加上K()和V()，可缺省构造
??:_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)
?{}
?void?Insert(const?K&?key,?const?V&?value);
?Node*?Find(const?K&?key);
?int?Height();
?bool?IsBalance();
?void?PrintAVLTree();
private:
?Node*?_Find(Node*?root,?const?K&?key);
?void?_RotateL(Node*&?parent);
?void?_RotateR(Node*&?parent);
?void?_RotateLR(Node*&?parent);
?void?_RotateRL(Node*&?parent);
?int?_Height(Node*?root);
?bool?_IsBalance(Node*?root);
?void?_PrintAVLTree(Node*?root);
protected:
?Node*?_root;
};

下面对插入进行元素的分析：

1）判断树是否为空，为空时，新建根结点。

2）查找插入的key是否存在，存在就退出函数，不存在就执行3）。

3）找到插入key的位置，然后插入结点cur。

4）更新平衡因子：从cur开始向上其父结点进行更新平衡因子，如果结点的平衡因子不满足AVL树，进行旋转调节平衡因子。

template<class?K,class?V>
void?AVLTree<K,V>::Insert(const?K&?key,?const?V&?value)
{
?if?(_root?==?NULL)
?{
??_root?=?new?Node(key,?value);
??return;
?}
?if?(Find(key))//存在key
?{
??return;
?}
?Node*?prev?=?NULL;
?Node*?cur?=?_root;
?while?(cur)//插入key的位置cur
?{
??if?(key?<?cur->_key)
??{
???prev?=?cur;
???cur?=?cur->_left;
??}
??else?if?(key?>?cur->_key)
??{
???prev?=?cur;
???cur?=?cur->_right;
??}
?}
?cur?=?new?Node(key,?value);//插如结点cur
?if?(prev->_key?>?key)
?{
??prev->_left?=?cur;
??cur->_parent?=?prev;
?}
?else?if?(prev->_key?<?key)
?{
??prev->_right?=?cur;
??cur->_parent?=?prev;
?}
?//prev为cur的上一个结点，即为cur是prev的父亲结点
?prev?=?cur;
?cur?=?prev->_parent;
?while?(cur)
?{
??//更新平衡因子：从插如的cur开始向上更新平衡因子
??cur->_bf?=?_Height(cur->_right)?-?_Height(cur->_left);
??if?(cur->_bf?!=?-1?&&?cur->_bf?!=?1?&&?cur->_bf?!=?0)//不满足AVL树的结点，进行旋转调节平衡因子
??{//平衡因子为2时，一定存在右子树；平衡因子为-2时，一定存在左子树
????//左单旋：2?1（平衡因子）
????if?(cur->_bf?==?2?&&?cur->_right->_bf?==?1)
????{
?????_RotateL(cur);//引用传递
????}
????//右单旋：-2?-1
????else?if?(cur->_bf?==?-2?&&?cur->_left->_bf?==?-1)
????{
?????_RotateR(cur);
????}
????//左右旋转：-2?1
????else?if?(cur->_bf?==?-2?&&?cur->_left->_bf?==?1)
????{
?????_RotateLR(cur);
????}
????//右左旋转:2?-1
????else?if?(cur->_bf?==?2?&&?cur->_right->_bf?==?-1)
????{
?????_RotateRL(cur);
????}
??}
??prev?=?cur;
??cur?=?cur->_parent;
?}
}

进行旋转调节平衡因子，分四种情况：

（1）左单旋：cur的平衡因子为2，cur->_right的平衡因子为1。

（2）右单旋：cur的平衡因子为-2，cur->_left的平衡因子为-1。

（3）左右旋转：cur的平衡因子为-2，cur->_left的平衡因子为1。

（4）右左旋转：cur的平衡因子为-2，cur->_right的平衡因子为-1。

左右旋转和右左旋转可通过调用左单旋和右单旋进行，注意结束后重置平衡因子。

如果不是很清楚，可以自己画图进行分析。

左单旋：

template<class?K,?class?V>
void?AVLTree<K,?V>::_RotateL(Node*&?parent)
{
?Node*?subR?=?parent->_right;
?Node*?subRL?=?subR->_left;
?parent->_right?=?subRL;//1
?subR->_parent?=?parent->_parent;//1
?subR->_left?=?parent;//2
?parent->_parent?=?subR;//2
?if?(subRL)//注意不为空，进行链接
??subRL->_parent?=?parent;
?parent->_bf?=?subR->_bf?=?0;
?//进行subR的父亲结点和subR的链接
?if?(subR->_parent?==?NULL)//为空时，parent为根结点，更改根结点
??_root?=?subR;
?else//不为空，进行链接
?{
??if?(subR->_parent->_key?>?subR->_key)
???subR->_parent->_left?=?subR;
??else
???subR->_parent->_right?=?subR;
?}
?parent?=?subR;
}

右单旋：

template<class?K,?V>::_RotateR(Node*&?parent)
{
?Node*?subL?=?parent->_left;
?Node*?subLR?=?subL->_right;
?//不能变换顺序
?parent->_left?=?subL->_right;//1
?subL->_parent?=?parent->_parent;//1
?subL->_right?=?parent;//2
?parent->_parent?=?subL;//2
?if?(subLR)//注意不为空，进行链接
??subLR->_parent?=?parent;
?parent->_bf?=?subL->_bf?=?0;
?//进行subL的父亲结点和subL的链接
?if?(subL->_parent?==?NULL)//为空时，parent为根结点，更改根结点
??_root?=?subL;
?else//不为空，进行链接
?{
??if?(subL->_parent->_key?>?subL->_key)
???subL->_parent->_left?=?subL;
??else
???subL->_parent->_right?=?subL;
?}
?parent?=?subL;
}

左右旋转：

template<class?K,?V>::_RotateLR(Node*&?parent)
{
?Node*?pNode?=?parent;//需重新定义parent，在进行左右旋转后，parent指向发生了变化
?Node*?subLNode?=?pNode->_left;
?Node*?subLRNode?=?subLNode->_right;
?_RotateL(parent->_left);
?_RotateR(parent);
?//在单旋时，parent和subL的平衡因子都为0，在进行左右旋转和右左旋转会出错,故重新设置平衡因子
?//subLRNode的平衡因子存在三种情况：为0，为-1，为1。subLRNode的平衡因子影响parent和subL的平衡因子
?if?(subLRNode->_bf?==?1)
?{
??pNode->_bf?=?1;
??subLNode->_bf?=?0;
?}
?else?if?(subLRNode->_bf?==?-1)
?{
??pNode->_bf?=?0;
??subLNode->_bf?=?-1;
?}
?else
?{
??parent->_bf?=?0;
??subLNode->_bf?=?0;
?}
}

右左旋转：

template<class?K,?V>::_RotateRL(Node*&?parent)
{
?Node*?pNode?=?parent;
?Node*?subRNode?=?pNode->_right;
?Node*?subRLNode?=?subRNode->_left;
?_RotateR(parent->_right);
?_RotateL(parent);
?if?(subRLNode->_bf?==?1)
?{
??pNode->_bf?=?-1;
??subRNode->_bf?=?0;
?}
?else?if?(subRLNode->_bf?==?-1)
?{
??pNode->_bf?=?0;
??subRNode->_bf?=?1;
?}
?else
?{
??pNode->_bf?=?0;
??subRNode->_bf?=?0;
?}
}

测试用例如下：

void?AVLTreeTest()
{
?AVLTree<int,?int>?avlt;
?//int?arr[10]?=?{?16,?3,?7,?11,?9,?26,?18,?14,?15,?23?};
?int?arr[10]?=?{?4,?2,?6,?1,?5,?16,?14?};
?for?(int?i?=?0;?i?<?10;?++i)
?{
??avlt.Insert(arr[i],?i);
??avlt.PrintAVLTree();
?}
?cout?<<?avlt.IsBalance()?<<?endl;
}