一：AVL树介绍
AVL树本质上还是一棵二叉搜索树，它的特点是：
1.本身首先是一棵二叉搜索树。
2.带有平衡条件：每个结点的左右子树的高度之差的绝对值（平衡因子）最多为1。在本文中用分别用-1，0，1定义左边树高，等高，右边树高。平衡因子用m_bf表示。
也就是说，AVL树，本质上是带了平衡功能的二叉查找树（二叉排序树，二叉搜索树）。
二：插入算法
由于AVL树具有BST树的特性，所以它的插入算法思路上和BST树基本步骤是相同的，不过在BST树插入算法的基础上增加了由于平衡因子的变动，平衡化平衡因子的步骤，使得整棵树达到平衡因子绝对值不超过1的高度平衡。
在AVL树插入的过程中，为了使树再次平衡，需要作相应的旋转，分为单旋转和双旋转。又细分为左旋转，右旋转，左右旋转，右左旋转。
下面将就其中的主要情况加以说明：
（1）左旋转
左旋转的情况如图所示：
当我们插入元素出现类似的情况时，就需要左旋转来出马了。ptr是传给旋转函数的参数，我们先让ptr走到它的右孩子，用ptr表示旋转后的最上面的节点（有可能为根节点），用sub_left表示旋转后位置在左侧的节点，sub_right表示旋转后位置在右侧的节点（该图还未出现）。下文同此处。当出现上图情况是，我们只需用sub_left替换ptr的左孩子即可，并修改相应的平衡因子。不过有一点很重要，ptr的左孩子并不一定像图中那样为空，所以若要有左孩子，需要先将左孩子赋给sub_left的右孩子。
代码体现如下：
template <typename T>
void avl_tree<T>::rotate_left(node_type *&ptr)
{
auto sub_left = ptr; //先指定sub_left
ptr = ptr->right_child; //ptr走到它的右孩子
sub_left->right_child = ptr->left_child; //将ptr的左孩子覆盖sub_left的右孩子
ptr->left_child = sub_left; //旋转
sub_left->m_bf = ptr->m_bf = 0; //调整平衡因子
}
（2）右旋转
右旋转和左旋转代码只是镜像关系，就不重述一遍了。
（3）先左旋，后右旋
我们插入时可能碰到上面的情况，可以针对3、7进行左旋转，sub_left替换ptr的左孩子，再对7、16进行右旋转，sub_right替换ptr的右孩子。注意，若ptr有左右孩子，要将ptr的左孩子挂在sub_left的右孩子上，将ptr的右孩子挂在sub_left的左孩子上。
不过双旋转需要注意的是，平衡因子的情况不会像单旋转那么简单了，还可能出现下面的情况：
在这种情况中，2和18结点都是必须的，否则新插入9元素会直接导致3、7、9不平衡，程序直接执行左单旋转，而我们现在要讨论的是双旋转。
图中新增元素9或5，则3、7先左旋转，7、16后右旋转。分情况如下：
1.ptr的平衡因子为0：
ptr平衡因子为0时，如图2.1，经过双旋转后，参与旋转的节点平衡因子都为0。
2.ptr的平衡因子为1：
ptr平衡因子为1时，如图2.2，经过旋转后，sub_right的平衡因子为0，sub_left的平衡因子为-1。
3.ptr的平衡因子为-1：
ptr的平衡因子为-1时，如图2.3，经过旋转后，sub_right的平衡因子为1，sub_left的平衡因子为0。
上述三种情况概括了双旋转平衡因子的变化情况，代码体现如下：
template <typename T>
void avl_tree<T>::rotate_left_right(node_type *&ptr)
{
auto sub_right = ptr;
auto sub_left = ptr->left_child;
ptr = sub_left->right_child;
sub_left->right_child = ptr->left_child;
ptr->left_child = sub_left;
if(ptr->m_bf <= 0) //根据调整平衡因子
sub_left->m_bf = 0;
else
sub_left->m_bf = -1;
sub_right->left_child = ptr->right_child;
ptr->right_child = sub_right;
if(ptr->m_bf >= 0) //根据ptr调整平衡因子
sub_right->m_bf = 0;
else
sub_right->m_bf = 1;
ptr->m_bf = 0; //此句千万不能忘，否则平衡因子出错！
}
(4)先右旋，再左旋
和上面只是镜像关系，不再赘述。
三：删除算法
我将删除算法的核心也分以下几幅图来描述。
（1）当删除节点之后，它的父节点pre_tmp的平衡因子为+1/-1，表明该节点的子树高度并没有改变，只有有一条分支短了一截。如图所示，这种情况说明删除元素后，整棵树依旧平衡，直接退出即可。
（2）当删除节点之后，该父节点pre_tmp平衡因子为0，那么只能保证以父节点为根的子树平衡，整棵树的平衡还需要继续回溯其祖父节点ppre_tmp，循环执行，直至栈空。
（3）当删除节点之后，该父节点pre_tmp平衡因子为-2/+2（以下以-2为例，与+2为镜像关系，不赘述），有三种情况：
i.pre_tmp的较高的子树的头个节点（如下图90）平衡因子为0，注意：为0！，此时我们可以直接进行一次右旋转。但是，在这种情况下，一定要修改平衡因子！因为该情况下，pre_tmp较高的子树的头个节点（如下图90），它的左右子树个数一定为2！当执行右旋转时，我们的旋转函数会将转函数内部默认将ptr和sub_right的平衡因子修改为0，所以在此处执行完单旋转函数后，必须令ptr的平衡因子为1，令sub_right的平衡因子为-1。下图的镜像情况为左旋转的情况，左旋转结束后令ptr平衡因子为-1，令sub_left的平衡因子为1即可，不再赘述。
ii.pre_tmp的较高的子树的头个节点平衡因子为1，由于与pre_tmp的平衡因子-2反号，如下图，直接进行先左旋转，再右旋转即可。
注意：我们的旋转函数已经讨论过类似形式的树的平衡化及平衡因子的修改，此处不必再修改平衡因子。如果下图中结点2若存在孩子节点，那么就转化为情况 i了，就必须追加修改平衡因子。
iii.pre_tmp的较高的子树的头个节点的平衡因子为-1，与pre_tmp同号，直接进行单旋转即可。不必再修改平衡因子。
四：AVL树代码
#ifndef _AVLTREE_H
#define _AVLTREE_H
#include <iostream>
#include <assert.h>
#include <stack>
using namespace std;
template <typename T>
class avl_tree;
template <typename T>
class avl_node{
friend class avl_tree<T>;
public:
avl_node() : m_data(T()), left_child(nullptr), right_child(nullptr)
{}
avl_node(T data, avl_node<T> *left = nullptr, avl_node<T> *right = nullptr)
: m_data(data), left_child(left), right_child(right)
{}
~avl_node() = default;
private:
T m_data;
int m_bf;
avl_node<T> *left_child;
avl_node<T> *right_child;
};
template <typename T>
class avl_tree{
typedef avl_node<T> node_type;
public:
avl_tree() : root(nullptr)
{}
~avl_tree();
public:
bool insert_elem(const T&);
bool remove_elem(const T&);
void inorder_traverse()const;
protected:
void destroy_tree(node_type *&);
bool insert_elem(node_type *&, const T&);
bool remove_elem(node_type *&, const T&);
void inorder_traverse(node_type *)const;
protected:
void rotate_left(node_type *&);
void rotate_right(node_type *&);
void rotate_left_right(node_type *&);
void rotate_right_left(node_type *&);
private:
node_type *root;
};
//public interface
template <typename T>
avl_tree<T>::~avl_tree()
{
//destroy_tree(root);
}
template <typename T>
bool avl_tree<T>::insert_elem(const T& val)
{
insert_elem(root, val);
}
template <typename T>
bool avl_tree<T>::remove_elem(const T& val)
{
remove_elem(root, val);
}
template <typename T>
void avl_tree<T>::inorder_traverse()const
{
inorder_traverse(root);
}
//protected interface
template <typename T>
void avl_tree<T>::destroy_tree(node_type *&t)
{
if(t != NULL){
destroy_tree(t->left_child);
destroy_tree(t->right_child);
delete t;
}
}
template <typename T>
void avl_tree<T>::inorder_traverse(node_type *t)const
{
if(t != nullptr){
inorder_traverse(t->left_child);
cout << t->m_data << " ";
inorder_traverse(t->right_child);
}
}
template <typename T>
bool avl_tree<T>::insert_elem(node_type *&t, const T& val)
{
node_type *tmp = t;
node_type *pre_tmp = nullptr;
stack<node_type* > st; //用栈来保存路径，当插入元素后，通过出栈回溯，平衡化祖先节点
int lable; //标签
while(tmp != nullptr){ //首先查找要插入的地方
pre_tmp = tmp;
st.push(pre_tmp);
if(val == tmp->m_data)
return false;
else if(val < tmp->m_data)
tmp = tmp->left_child;
else
tmp = tmp->right_child;
}
tmp = new node_type(val); //新节点生成
if(t == nullptr){ //如果t为空，根节点
t = tmp;
}
else{
if(tmp->m_data < pre_tmp->m_data){ //左子树
pre_tmp->left_child = tmp;
}
else{
pre_tmp->right_child = tmp; //右子树
}
while(!st.empty()){
pre_tmp = st.top();
st.pop();
if(pre_tmp->left_child == tmp)
pre_tmp->m_bf--; //平衡因子-1
else
pre_tmp->m_bf++; //平衡因子+1
if(pre_tmp->m_bf == 0)
break;
else if(pre_tmp->m_bf == -1 || pre_tmp->m_bf == 1)
tmp = pre_tmp;
else{
lable = pre_tmp->m_bf > 0 ? 1 : -1; //标签，用来记录父节点平衡因子符号
if(tmp->m_bf == lable){ //same symbol，同号，单旋转
if(lable == 1){ //(L -- \)
rotate_left(pre_tmp);
}
else{ //(R -- /)
rotate_right(pre_tmp);
}
}
else{
if(lable == -1){ //(LR -- <) //不同号，双旋转
rotate_left_right(pre_tmp);
}
else{ //(RL -- >)
rotate_right_left(pre_tmp);
}
}
break; //!!! don't forget! 由于修改后已经平衡，必须break，否则会继续回溯，可能导致segmentation fault
}
}
if(st.empty())
t = pre_tmp; //如果栈空，即位头节点
else{ //不空，链接
auto pre_tmp_ = st.top();
if(pre_tmp->m_data < pre_tmp_->m_data)
pre_tmp_->left_child = pre_tmp;
else
pre_tmp_->right_child = pre_tmp;
}
}
return true;
}
template <typename T>
bool avl_tree<T>::remove_elem(node_type *&t, const T& val)
{
assert(t != nullptr);
node_type *tmp = t;
node_type *pre_tmp = nullptr;
node_type *ppre_tmp = nullptr;
node_type *it_tmp = nullptr;
stack<node_type*> st;
int sign, lable; //符号标记
int flag = 0; //子树标记，下文具体解释
while(tmp != nullptr){
if(tmp->m_data == val) //找到跳出循环
break;
pre_tmp = tmp;
st.push(pre_tmp);
if(tmp->m_data > val)
tmp = tmp->left_child;
else
tmp = tmp->right_child;
}
if(tmp == nullptr) //未找到，返回
return false;
else if(tmp->left_child != nullptr && tmp->right_child != nullptr){
pre_tmp = tmp; //将有两个孩子的节点转化为只有一个孩子的节点，方法是寻找它中序遍历的直接前驱或后继
st.push(pre_tmp);
it_tmp = tmp->left_child;
while(it_tmp->right_child != nullptr){
pre_tmp = it_tmp;
st.push(pre_tmp);
it_tmp = it_tmp->right_child;
}
tmp->m_data = it_tmp->m_data; //覆盖要删除的节点
tmp = it_tmp; //tmp指向要删除的节点，函数结束前会delete tmp
}
if(tmp->left_child != nullptr){ //这样的判断方式会导致删除一个节点下两个没有孩子节点的节点时，由于左孩子均为空，直接跳入else
it_tmp = tmp->left_child;
}
else{
it_tmp = tmp->right_child;
}
if(pre_tmp == nullptr)
t = it_tmp;
else{
if(pre_tmp->left_child == tmp){ //上面直接跳入else，但我们在此处加上flag，用来识别它到底是pre_tmp的左孩子还是右孩子。
flag = 0;
pre_tmp->left_child = it_tmp;
}
else{
flag = 1;
pre_tmp->right_child = it_tmp;
}
while(!st.empty()){
pre_tmp = st.top();
st.pop();
if(pre_tmp->left_child == it_tmp && flag == 0)//此处flag=0，防止pre_tmp的左孩子为空，右孩子同样为空，直接进入else
pre_tmp->m_bf++;
else
pre_tmp->m_bf--;
if(!st.empty())
{
ppre_tmp = st.top();
if(ppre_tmp->left_child == pre_tmp)
{
sign = -1; //sign用来识别是祖父节点的左孩子还是右孩子，下文链接会用上
flag = 0;
}
else{
sign = 1;
flag = 1;
}
}
else
sign = 0; //栈空，它的祖先节点不存在，pre_tmp即为根节点，但是这里也要写上，否则sign的值会遗留下来
if(pre_tmp->m_bf == -1 || pre_tmp->m_bf == 1)
break; //已经平衡，直接跳出
if(pre_tmp->m_bf != 0){ //m_bf为+2/-2
if(pre_tmp->m_bf < 0){
lable = -1; //lable表示父节点符号，下面会用来区分同号异号
it_tmp = pre_tmp->left_child;
}
else{
lable = 1;
it_tmp = pre_tmp->right_child;
}
if(it_tmp->m_bf == 0){ //pre_tmp的较高子树的头节点m_bf为0
if(lable == -1){
rotate_right(pre_tmp);
pre_tmp->m_bf = 1;
pre_tmp->right_child->m_bf = -1;
}
else{
rotate_left(pre_tmp);
pre_tmp->m_bf = -1;
pre_tmp->left_child->m_bf = 1;
}
break; //直接跳出，并没有链接，需要下文写上链接
}
if(it_tmp->m_bf == lable){ //同号
lable == 1 ? rotate_left(pre_tmp) : rotate_right(pre_tmp);
}
else{ //异号
lable == -1 ? rotate_left_right(pre_tmp)
: rotate_right_left(pre_tmp);
}
//sign == -1 ? ppre_tmp->left_child = pre_tmp //不能写成这样，因为sign值可能为0，会直接进入后者
// : ppre_tmp->right_child = pre_tmp; //!!!!! sign maybe 0 ! not only1 or -1 !!! warning!
if(sign == -1)
ppre_tmp->left_child = pre_tmp;
else if(sign == 1) //else if正确方式
ppre_tmp->right_child = pre_tmp;
}
it_tmp = pre_tmp; //回溯
}
if(st.empty()) //栈为空，根节点
t = pre_tmp;
else{ //这一段else参考书上没有，书是错的，如果不写此处，290break直接跳出while循环，会导致链接不上，数据丢失
ppre_tmp = st.top();
if(ppre_tmp->m_data > pre_tmp->m_data)
ppre_tmp->left_child = pre_tmp;
else
ppre_tmp->right_child = pre_tmp;
}
}
delete tmp;
tmp = nullptr;
return true;
}
template <typename T>
void avl_tree<T>::rotate_left(node_type *&ptr) //左旋转
{
auto sub_left = ptr;
ptr = ptr->right_child;
sub_left->right_child = ptr->left_child;
ptr->left_child = sub_left;
sub_left->m_bf = ptr->m_bf = 0;
}
template <typename T>
void avl_tree<T>::rotate_right(node_type *&ptr) //右旋转
{
auto sub_right = ptr;
ptr = ptr->left_child;
sub_right->left_child = ptr->right_child;
ptr->right_child = sub_right;
sub_right->m_bf = ptr->m_bf = 0;
}
template <typename T>
void avl_tree<T>::rotate_left_right(node_type *&ptr) //左右旋转
{
auto sub_right = ptr;
auto sub_left = ptr->left_child;
ptr = sub_left->right_child;
sub_left->right_child = ptr->left_child;
ptr->left_child = sub_left;
if(ptr->m_bf <= 0)
sub_left->m_bf = 0;
else
sub_left->m_bf = -1;
sub_right->left_child = ptr->right_child;
ptr->right_child = sub_right;
if(ptr->m_bf >= 0)
sub_right->m_bf = 0;
else
sub_right->m_bf = 1;
ptr->m_bf = 0; //不要漏写
}
template <typename T>
void avl_tree<T>::rotate_right_left(node_type *&ptr) //右左旋转
{
auto sub_left = ptr;
auto sub_right = ptr->right_child;
ptr = sub_right->left_child;
sub_right->left_child = ptr->right_child;
ptr->right_child = sub_right;
if(ptr->m_bf >= 0)
sub_right->m_bf = 0;
else
sub_right->m_bf = 1;
sub_left->right_child = ptr->left_child;
ptr->left_child = sub_left;
if(ptr->m_bf <= 0)
sub_left->m_bf = 0;
else
sub_left->m_bf = -1;
ptr->m_bf = 0;
}
#endif /*avl_tree.h*/
五：测试代码
#include "avl_tree.h"
#define ElemType int
int main()
{
//ElemType array[] = {50, 60, 79}; //rotate_left
//ElemType array[] = {50, 20, 10}; //rotate_right
//ElemType array[] = {16, 3, 7}; //rotate_left_right
//ElemType array[] = {16, 3, 18, 2, 7, 9};
//ElemType array[] = {16, 3, 18, 2, 7, 5};
//ElemType array[] = {16, 30, 12, 31, 20, 21}; //rotate_right_left
//ElemType array[] = {16, 30, 12, 31, 20, 17};
//ElemType array[] = {16,3,7,11,9,26,18,14,15};
ElemType array[] = {80, 50, 100, 40, 60, 90, 140, 45, 83, 95, 150, 81, };
//ElemType array[] = {16, 12};
avl_tree<int> avl;
size_t len = sizeof(array) / sizeof(ElemType);
for(size_t i=0; i<len; ++i){
avl.insert_elem(array[i]);
}
avl.inorder_traverse();
cout << endl;
avl.remove_elem(140);
//avl.remove_elem(3);
//avl.remove_elem(9);
avl.inorder_traverse();
cout << endl;
return 0;
}
测试结果：
（写文不易，转载请注明出处）
转载请注明原文地址: https://ju.6miu.com/read-1298276.html
