平衡二叉树（AVLTree）封装+模板实现

2018-05-27 Algorithm algorithm, tree 0 Comments Word Count: 3k(words)

简介

在计算机科学中，AVL树是最先发明的自平衡二叉查找树。在AVL树中任何节点的两个子树的高度最大差别为1，所以它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下的时间复杂度都是 $O(\log{n})$ 。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。AVL树得名于它的发明者G. M. Adelson-Velsky和E. M. Landis，他们在1962年的论文《An algorithm for the organization of information》中发表了它。

节点的平衡因子是它的左子树的高度减去它的右子树的高度（有时相反）。带有平衡因子1、0或 -1的节点被认为是平衡的。带有平衡因子 -2或2的节点被认为是不平衡的，并需要重新平衡这个树。平衡因子可以直接存储在每个节点中，或从可能存储在节点中的子树高度计算出来。

二叉查找树给我们带来了很多方便，但是由于其在有序序列插入时就会退化成单链表（时间复杂度退化成 O(n)，AVL-tree就克服了上述困难。AVL-tree是一个“加上了平衡条件的”二叉搜索树，平衡条件确保整棵树的深度为O(log n)。

AVL树是最先发明的自平衡二叉查找树。在AVL树中任何节点的两个子树的高度最大差别为一，所以它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下都是 O(log n)。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。

AVL树的所有操作都与二叉查找树相同，不同的是，这里AVL树需要做“AVL旋转”。

AVL旋转

AVL树最重要的核心部分就是AVL旋转了，这部分我的感触是，单做旋转还是挺好理解的，只不过写起代码来有点复杂，书中以插入节点为例，删除节点的部分折腾了好久。

在理解AVL旋转之前，首先得知道以下几个概念：

AVL 树节点的插入总是在叶子节点。
AVL 树在插入节点之前总是满足平衡条件的。
插入新节点后有可能满足平衡条件也有可能不满足。
当不满足平衡条件后，我们就需要对新的树进行旋转。

旋转之前，我们首先要找到一个X节点，这个X节点做如下定义：

假如我们在某一个叶子节点处插入一个新的节点后，此时这棵树的某些节点的平衡性会发生变化，那么我们从叶子节点向上到根节点的路径上第一个平衡性发生变化的节点。

基于这个X节点，考虑一件事情：
这个X节点分为左右子树，左右子树又有左右子树，1分2，2分4，所以以这个X节点为根节点的话，新插入的节点可能出现的位置有：

X的左孩子节点的左子树上**(left-left)**
X的右孩子节点的右子树上**(right-right)**
X的左孩子节点的右子树上**(left-right)**
X的右孩子节点的左子树上**(right-left)**

根据上述情况就延生出了4种旋转：
1.left-left Rotation
2.right-right Rotation
3.left-right Rotation
4.right-left Rotation

前两种属于单旋转，后两种属于双旋转，双旋转的操作可以由两次单旋转组成。

PS:AVL树的旋转还是得画图来理解，这里直接贴出书中的图了。

图片来自 C小加的博客

6节点的左子树3节点高度比右子树7节点大2，左子树3节点的左子树1节点高度大于右子树4节点，这种情况成为左左（LL）。
6节点的左子树2节点高度比右子树7节点大2，左子树2节点的左子树1节点高度小于右子树4节点，这种情况成为左右（LR）。
2节点的左子树1节点高度比右子树5节点小2，右子树5节点的左子树3节点高度大于右子树6节点，这种情况成为右左（RL）。
2节点的左子树1节点高度比右子树4节点小2，右子树4节点的左子树3节点高度小于右子树6节点，这种情况成为右右（RR）。

从图2中可以可以看出，1和4两种情况是对称的，这两种情况的旋转算法是一致的，只需要经过一次旋转就可以达到目标，我们称之为单旋转。2和3两种情况也是对称的，这两种情况的旋转算法也是一致的，需要进行两次旋转，我们称之为双旋转。

那么为什么需要双旋转呢？

这里我做出我个人的解释，在 LL 情况中，要达到平衡，是需要将失衡节点划分到右边，失衡节点的左孩子补上失衡节点的位置。这样左子树的高度 -1，右边的高度 +1，这样左右两边的个数就平衡了。当然根据BST的性质，如果失衡节点存在右孩子的话应该划也要分到右边。RR 情况与 LL 情况对称。

而在 LR 情况中，我们是需要把失衡节点划到右边，失衡节点的左孩子的右孩子替补失衡节点原来的位置。但我们的节点存储结构有不能获得前驱节点的限制，我们只有后继关系，即我们只能通过失衡节点访问其他节点，所以不能直接把LR孩子放上来，而是分成两步调整。

// 这里的描述太那啥了，得搞点图说明下

AVL-Tree实现

AVL-Tree是一个二叉排序树，其基本操作也跟它类似，唯一需要注意的就是在插入，删除节点后，需要对树进行调整，让树的每个节点保持平衡。

节点的平衡因子是通过计算其左子树和右子树的差得来的，这里有两种考虑方式：

每次都计算一次（递归求深度）。
将平衡因子作为一个成员变量保存在节点中，平衡性发生变化的时候更新。

本文采取的是第一种方式，关于两种方式利弊的比较：

// 不想写？自己百度吧，反正就是第一种方法从上到下递归存在重复调用增加时间开销，第二种平衡性变化时候需要update 失衡位置 balanceFactor

另外，这里我用了C++类封装，为了学习还顺便使用了模板，所以类的声明和实现都放在了一个文件中，感觉内容太多，还是分开来比较好。

// AVLNode.h

#ifndef __AVLNODE_H__
#define __AVLNODE_H__

#include <iostream>
#include <vector>
#include <algorithm>

template <typename KeyType>
class AVLNode{
public:
    KeyType key;
    AVLNode * left;
    AVLNode * right;
    AVLNode() : key(0), left(NULL), right(NULL) {}
    AVLNode(KeyType k) :key(k), left(NULL), right(NULL) {}
};
#endif

// AVLTree.h

#ifndef AVLTREE_AVLTREE_H
#define AVLTREE_AVLTREE_H

#include "AVLNode.h"

//AVL树的模板实现
template <typename KeyType>
class AVLTree
{
    //类型定义
    typedef AVLNode<KeyType> AVLNode;
    typedef AVLTree<KeyType> AVLTree;

private:
    AVLNode * avlroot;
    //求树的高度
    int __height(const AVLNode *root);
    //高度差（平衡因子）
    int __diff(const AVLNode*root);

    //AVL4种旋转：左左，左右，右右，右左
    //X定义为插入位置节点到根节点的路径上平衡条件被改变的节点中最深的那个节点
    //X通过递归返回的方式找到
    //左左：插入点位于X的左孩子节点的左子树
    //左右：插入点位于X的左孩子节点的右子树
    //右右：插入点位于X的右孩子节点的右子树
    //右左：插入点位于X的右孩子节点的左子树

    //单旋转
    AVLNode * __ll_Rotation(AVLNode *root);//left-left rotation
    AVLNode * __rr_Rotation(AVLNode *root);//right-right rotation
    //双旋转
    AVLNode * __lr_Rotation(AVLNode *root);//left-right rotation
    AVLNode * __rl_Rotation(AVLNode *root);//right-left rotation


	//平衡操作
    AVLNode * __Balance(AVLNode *root);
    //插入的内部实现
    AVLNode * __Insert(AVLNode *root, const KeyType &k);
    //中序遍历的两种重载
    // 1. 直接输出中序遍历节点
    void __InorderTraversal(const AVLNode* root);
    // 2. 结果保存到vector中
    void __InorderTraversal(const AVLNode*root, std::vector<KeyType>&vec);
	//判断是否是叶子节点
    bool __isLeaf(AVLNode* const &node) {return (node->left == nullptr && node->right == nullptr) ? true : false};
    //判断是否有两个孩子
    bool __isNodeWithTwoChild(AVLNode * const &node);
	//查找的内部实现
    AVLNode* __search(AVLNode *const root, const KeyType &k);
	//删除树的所有节点
    void __deleteTree(AVLNode * root);
	//删除节点
    AVLNode* __Delete(AVLNode * root, const KeyType& k);
	//求当前根节点最小（一路向左）
    AVLNode* __treeMin(AVLNode *root);
    //求当前根节点的最大（一路向右）
    AVLNode* __treeMax(AVLNode *root);


public:
    AVLTree(){ avlroot = nullptr; }//默认构造函数
    ~AVLTree();//析构函数删除树中所有节点
    AVLTree(const std::vector<KeyType>&);//构造函数，容器构造
    AVLTree(const KeyType * arr, size_t len);//构造函数，数组构造
    void InorderTraversal();//中序遍历外部接口
    void InorderTraversal(std::vector<KeyType>&);//中序遍历外部接口重载2
    bool Delete(const KeyType &k);//删除节点的外部接口
    void Insert(const KeyType & k);//插入节点的外部接口
    bool IsEmpty(){ return avlroot == nullptr; } //树空？
    bool search(const KeyType &k);//查询外部接口
};
#endif //AVLTREE_AVLTREE_H

旋转操作

template <typename KeyType>
AVLNode * AVLTree::__ll_Rotation(AVLNode *root)
{
    AVLNode * tmp;
    tmp = root->left;
    root->left = tmp->right;
    tmp->right = root;
    return tmp;
}

template <typename KeyType>
AVLNode * AVLTree::__rr_Rotation(AVLNode *root)
{
    AVLNode* tmp;
    tmp = root->right;
    root->right = tmp->left;
    tmp->left = root;
    return tmp;
}

template <typename KeyType>
AVLNode * AVLTree::__lr_Rotation(AVLNode *root)
{
    AVLNode * tmp;
    tmp = root->left;
    root->left = __rr_Rotation(tmp);
    return __ll_Rotation(root);
}

template <typename KeyType>
AVLNode * AVLTree::__rl_Rotation(AVLNode *root)
{
    AVLNode * tmp;
    tmp = root->right;
    root->right = __ll_Rotation(tmp);
    return __rr_Rotation(root);
}

AVLTree 插入

template <typename KeyType>
AVLNode * AVLTree::__Insert(AVLNode * root, const KeyType& k)
{
    if (nullptr == root)
    {
        root = new AVLNode(k);
        return root;
    }//递归返回条件
    else if (k < root->key)
    {
        root->left = __Insert(root->left, k);//递归左子树
        //balance operation
        root = __Balance(root);//平衡操作包含了四种旋转
    }
    else if (k>root->key)
    {
        root->right = __Insert(root->right, k);//递归右子树
        //balance operation
        root = __Balance(root);//平衡操作包含了四种旋转
    }
    return root;
}

AVLTree 删除

//删除节点的私有成员实现
template <typename KeyType>
AVLNode * AVLTree::__Delete(AVLNode *root, const KeyType& k)
{
    if (nullptr == root)
        return root;
    if (!search(k))//查找删除元素是否存在
    {
        std::cerr << "Delete error , key not find" << std::endl;
        return root;
    }

    if (k == root->key)//根节点
    {
        if (__isNodeWithTwoChild(root))//左右子树都非空
        {
            if (__diff(root) > 0)//左子树更高，在左边删除
            {
                root->key = __treeMax(root->left)->key;//以左子树的最大值替换当前值
                root->left = __Delete(root->left, root->key);//删除左子树中已经替换上去的节点
            }
            else//右子树更高，在右边删除
            {
                root->key = __treeMin(root->right)->key;
                root->right = __Delete(root->right, root->key);
            }
        }
        else//有一个孩子、叶子节点的情况合并
        {
            //if (!__isLeaf(root))
            AVLNode * tmp = root;
            root = (root->left) ? (root->left) :( root->right);
            delete tmp;
            tmp = nullptr;
        }
    }//end-if
    else if (k < root->key)//往左边删除
    {
        root->left = __Delete(root->left, k);//左子树中递归删除
        //判断平衡的条件与在插入时情况类似
        if (__diff(root) < -1)//不满足平衡条件，删除左边的后，右子树变高
        {
            if (__diff(root->right) > 0)
            {
                root = __rl_Rotation(root);
            }
            else
            {
                root = __rr_Rotation(root);
            }
        }
    }//end else if
    else
    {
        root->right = __Delete(root->right, k);
        if (__diff(root) > 1)//不满足平衡条件
        {
            if (__diff(root->left) < 0)
            {
                root = __lr_Rotation(root);
            }
            else
            {
                root = __ll_Rotation(root);
            }
        }
    }
    return root;
}