数据结构中AVL的c++实现

参考链接：http://blog.****.net/cjbct/article/details/53613436

AVL树中，最重要的便是让树重新平衡，我们称个过程为旋转。旋转包括四种，主要是由于插入位置的原因导致的。旋转的过程可以看代码中的注释部分（569行-639行），有详细的解释。

这次编写的过程中，将C++模板类的定义了和函数实现进行了分开（但是仍然在头文件中），遇到了比较多的问题。先看看代码，然后对里面我遇到的问题进行总结。

先看看AVL树的实现代码 AVLTree.h:

[cpp]view plain copy
#ifndef AVL_TREE_H  
#define AVL_TREE_H  
  
#include<iostream>  
using namespace std;  
  
  
template <typename Comparable>  
class AVLTree  
{  
  
public:  
    typedef enum _order {PREORDER, INORDER, POSTORDER} ORDER; // 通过enum定义常量  
  
public:  
    AVLTree() :m_root(nullptr){}  
    AVLTree(const AVLTree &rhs)  
    {  
        m_root = clone(rhs.m_root);  
    }  
    ~AVLTree()  
    {  
        makeEmpty();  
    }  
  
    /** 
    * 返回树的高度。空树的高度定义为-1 
    */  
    int getHeight() const  
    {  
        return m_root.height;  
    }  
  
    /** 
    * 找到树中的最小值，通过调用private的findMin实现递归 
    */  
    const Comparable & findMin() const  
    {  
        return findMin(m_root)->element;  
    }  
  
    /** 
    * 找到树中的最大值，通过调用private的findMax实现递归 
    */  
    const Comparable & findMax() const  
    {  
        return findMax(m_root)->element;  
    }  
  
    /** 
    * 当x找到时返回真，否则返回假 
    * 调用了private的那个同名函数，这个是为了递归实现 
    *（因为private中包含了一个AVLNode的指针t） 
    */  
    bool contains(const Comparable &x) const  
    {  
        return contains(x, m_root);  
    }  
  
    /** 
    * 判断树是否为空 
    */  
    bool isEmpty() const  
    {  
        return  nullptr == m_root;  
    }  
  
    /** 
    * 把树遍历一遍（顺序可以自己选择，默认为中序） 
    */  
    void printTree(ORDER or = INORDER, ostream & out = cout) const  
    {  
        if (isEmpty())  
            out << "Empty tree!" << endl;  
        else  
        {  
            switch (or)  
            {   
                case PREORDER:  
                    preOrder(m_root, cout);  
                    break;   
                case INORDER:  
                    inOrder(m_root, cout);  
                    break;  
                case POSTORDER:  
                    postOrder(m_root, cout);  
                    break;  
                default:  
                    cerr << "打印树的顺序只能为PREORDER, INORDER, POSTORDER!" << endl;  
                    break;  
            }  
        }         
    }  
  
    /** 
    * 清空树 
    */  
    void makeEmpty()  
    {  
        makeEmpty(m_root);  
    }  
  
    /** 
    * 把x插入树中，如果重复了就忽略 
    */  
    void insert(const Comparable &x)  
    {  
        insert(x, m_root);  
    }  
  
    /** 
    * 把x从树中删除。如果x不在树中就什么都不做。 
    */  
    void remove(const Comparable &x)  
    {  
        remove(x, m_root);  
    }  
  
    /** 
    * 深拷贝 
    */  
    const AVLTree & operator= (const AVLTree &rhs)  
    {  
        if (this != &rhs)  
        {  
            AVLNode *tmp = clone(rhs.m_root);  
            makeEmpty();  
            m_root = tmp;  
        }  
        return *this;  
    }  
  
  
private:  
    struct AVLNode{  
        Comparable element;  
        AVLNode *left;  
        AVLNode *right;  
        int height;  
  
        AVLNode(const Comparable &theElement,  
            AVLNode *lt,  
            AVLNode *rt,  
            int h = 0)  
            : element(theElement), left(lt), right(rt), height(h) {}  
    };  
  
    AVLNode *m_root; // 根节点  
    static const int ALLOW_IMBALANCE = 1; // 允许实施平衡的高度界限  
  
    /** 
    * 用于比较两个数的大小（主要用于比较高度） 
    */  
    int max (int a, int b)  
    {  
        return a >= b ? a : b;   
    }  
  
    /** 
    * 获得节点高度,空树的高度为-1 
    */  
    inline int height(AVLNode *t) const  
    {  
        return nullptr == t ? -1 : t->height;  
    }  
  
    /** 
    * 在树t中插入元素x，如果重复则什么也不做 
    */  
    void insert(const Comparable &x, AVLNode * &t);  
  
    /** 
    * 在树t中删除元素x 
    */  
    void remove(const Comparable &x, AVLNode * &t);  
      
  
    /** 
    * 查找最小的元素, 通过递归的方法 
    */  
    AVLNode * findMin(AVLNode *t) const;  
      
  
    /** 
    * 查找最大的元素, 通过循环的方法 
    */  
    AVLNode * findMax(AVLNode *t) const;  
  
    /** 
    * 通过遍历的方法查找x是否在树（或子树）t中 
    */  
    bool contains(const Comparable &x, AVLNode * t) const;  
      
    /** 
    * 清空树 
    */  
    void makeEmpty(AVLNode * &t);  
      
    /** 
    * 按前序打印子树 
    */  
  
    void preOrder(AVLNode *t, ostream & out) const;  
    /** 
    * 按中序打印子树 
    */  
  
    void inOrder(AVLNode *t, ostream & out) const;  
    /** 
    * 按后序打印子树 
    */  
    void postOrder(AVLNode *t, ostream & out) const;  
  
    /** 
    * 复制子树 
    */  
    AVLNode * clone(AVLNode *t) const;  
  
    /** 
    * 平衡子树 
    */  
    void balance(AVLNode * &t);  
  
    /** 
    * 左旋（右子树比左子树高2，并且新插入的元素在右子树的右边） 
    * 此时以右子树(k1)为轴，它的根(k2)进行左旋 
    * 可以理解为它的根在它的左边，所以左旋（在左边旋转） 
    *      K2                           K1 
    *     /  \                         /  \ 
    *    X    k1         -----        K2   Z 
    *         / \                    /  \   \ 
    *        Y   Z                  X    Y   Z' 
    *             \ 
    *              Z' 
    * Z'可能在Z的左边，也可以在Z的右边。例子中假设在右边。 
    **/  
    void rotateWithRightChild(AVLNode * & k2);  
  
    /** 
    * 右旋（左子树比右子树高2，并且新插入的元素在左子树的左边） 
    * 此时以左子树（k1）为轴，它的根（k2）进行右旋 
    * 可以理解为它的根在它的右边，所以右旋（在右边旋转） 
    *       k2                      k1 
    *      /  \                    /  \ 
    *     k1   Z      -------     X    k2 
    *    /  \                    /     / \ 
    *   X    Y                  X'     Y   Z  
    *  / 
    * X' 
    * X'可能在X的左边，也可以在X的右边。例子中假设在左边。 
    */  
    void rotateWithLeftChild(AVLNode * & k2);  
  
    /** 
    * 左右双旋（左子树K1比右子树D高2，并且新插入的元素在左子树K1的右边K2） 
    * 第一步：对左子树k1进行一次左旋(轴为k2) 
    * 第二步：对整个树k3进行一次右旋（轴为k2） 
    *       k3                k3              k2 
    *      /  \              /  \            /  \ 
    *     k1   D    ----    k2   D  ----    k1   k3 
    *    / \               / \             / \   / \ 
    *   A   k2            k1  C           A   B  C  D 
    *       / \          / \ 
    *      B   C        A   B 
    */  
    void doubleWithLeftChild(AVLNode * & k3);  
  
    /** 
    * 右左双旋（右子树K1比左子树A高2，并且新插入的元素在右子树K1的左边K2） 
    * 第一步：对右子树k1进行一次右旋（轴为k2） 
    * 第二步：对整个树k3进行一次左旋（轴为k2） 
    *      k3              k3                 k2 
    *     /  \            /  \               /  \ 
    *    A    k1   ----  A    k2     ----  k3    k1 
    *        / \             /  \         /  \  /  \ 
    *       K2  D           B    k1      A    B C   D 
    *      / \                  /  \ 
    *     B   C                C    D 
    */  
    void doubleWithRightChild(AVLNode * & k3);  
  
    /** 
    * 更新节点的高度 
    */  
    inline void updateHeight(AVLNode * & t)  
    {  
        t->height = max(height(t->left), height(t->right)) + 1;  
    }  
  
};  
  
  
/** 
* 复制子树 
*/  
template <typename Comparable>  
typename AVLTree<Comparable>::AVLNode *   
    AVLTree<Comparable>::clone(  
        typename AVLTree<Comparable>::AVLNode *t) const  
{  
    if (t == nullptr)  
        return nullptr;  
  
    return new AVLNode(t->element, clone(t->left), clone(t->right));  
}  
  
/** 
* 按前序打印子树 
*/  
template <typename Comparable>  
void AVLTree<Comparable>::preOrder(  
    typename AVLTree<Comparable>::AVLNode*t,   
    ostream & out) const  
{  
    if (nullptr != t)  
    {     
        out << t->element << endl;  
        preOrder(t->left, out);  
        preOrder(t->right, out);  
    }  
}  
  
  
  
/** 
* 按中序打印子树 
*/  
template <typename Comparable>  
void AVLTree<Comparable>::inOrder(  
    typename AVLTree<Comparable>::AVLNode *t,   
    ostream & out) const  
{  
    if (nullptr != t)  
    {  
        inOrder(t->left, out);  
        out << t->element << endl;  
        inOrder(t->right, out);  
    }  
}  
  
/** 
* 按后序打印子树 
*/  
template <typename Comparable>  
void AVLTree<Comparable>::postOrder(  
    typename AVLTree<Comparable>::AVLNode*t,  
    ostream & out) const  
{  
  
    if (nullptr != t)  
    {  
        postOrder(t->left, out);  
        postOrder(t->right, out);  
        out << t->element << endl;  
    }  
}  
  
  
/** 
* 清空树 
*/  
template <typename Comparable>  
void AVLTree<Comparable>::makeEmpty(  
    typename AVLTree<Comparable>::AVLNode * &t)  
{  
    if (t != nullptr)  
    {  
        makeEmpty(t->left);  
        makeEmpty(t->right);  
        delete t;  
    }  
    t = nullptr;  
}  
  
/** 
* 查找最小的元素, 通过递归的方法 
*/  
template <typename Comparable>  
typename AVLTree<Comparable>::AVLNode *   
    AVLTree<Comparable>::findMin(  
    typename AVLTree<Comparable>::AVLNode *t) const  
{  
    if (t == nullptr)  
        return nullptr;  
    if (t->left == nullptr)  
        return t;  
    return findMin(t->left);  
}  
  
/** 
* 查找最大的元素, 通过循环的方法 
*/  
template <typename Comparable>  
typename AVLTree<Comparable>::AVLNode *   
    AVLTree<Comparable>::findMax(  
    typename AVLTree<Comparable>::AVLNode *t) const  
{  
    if (t != nullptr)  
        while (t->right != nullptr)  
            t = t->right;  
    return t;  
}  
  
/** 
* 在树t中删除元素x,一定要主要保持树的平衡 
*/  
template <typename Comparable>  
void AVLTree<Comparable>::remove(  
    const Comparable &x,   
    typename AVLTree<Comparable>::AVLNode * &t)   
{  
    if (t == nullptr)  
        return; // 没有找要删除的节点x  
  
    if (x < t->element)  
        remove(x, t->left);  
    else if (t->element < x)  
        remove(x, t->right);  
    else if (t->left != nullptr &&  
        t->right != nullptr)  
    {  
        t->element = findMin(t->right)->element;  
        remove(t->element, t->right);  
    }  
    else  
    {  
        //typename AVLTree<Comparable>::AVLNode * oldNode = t;  
        auto oldNode = t; // 这一句等于上面的那长长的语句，可以看出C++11中的auto还是非常有用 的  
        t = (t->left != nullptr) ? t->left : t->right;  
        delete oldNode;  
    }  
  
    balance(t);  
}  
  
/** 
* 在树t中插入元素x，如果重复则什么也不做 
*/  
template <typename Comparable>  
void AVLTree<Comparable>::insert(  
    const Comparable &x,   
    typename AVLTree<Comparable>::AVLNode * &t)   
{  
    if (nullptr == t)  
        t = new AVLNode(x, nullptr, nullptr);  
    else if (x < t->element)  
    {  
        insert(x, t->left); // 如果带插入的值小于目前的节点，则插入在左子树  
        /* 
        if (height(t->left) - height(t->right) == 2) // 插入后如果节点的左子树比右子树高2 
        { 
            if (x < t->left->element) 
                rotateWithLeftChild(t); // 右旋 
            else 
                doubleWithLeftChild(t); // 左-右双旋 
        } 
        */  
  
    }  
    else if (t->element < x)  
    {  
        insert(x, t->right);// 如果带插入的值大于目前的节点，则插入在右子树  
        /* 
        if (height(t->right) - height(t->left) == 2)// 插入后如果节点的右子树比左子树高2 
        { 
            if (t->right->element < x) 
                rotateWithRightChild(t); // 左旋 
            else 
                doubleWithRightChild(t); // 右-左双旋 
        } 
        */  
  
    }  
    else  
        ; // 表示在树中找到了x，则什么也不做  
  
    balance(t); // 每次完成插入都检查子树是否平衡（并且默认更新节点t的高度）  
}  
  
/** 
* 平衡子树 
*/  
template <typename Comparable>  
void AVLTree<Comparable>::balance(  
    typename AVLTree<Comparable>::AVLNode * &t)  
{  
    if (nullptr == t)  
        return;  
    // 如果左子树的高度与右子树高度差大于实施平衡调整的限度  
    if (height(t->left) - height(t->right) > AVLTree<Comparable>::ALLOW_IMBALANCE)  
    {  
        // 判断是左子树的左边高还是右边高，如果左子树左边高  
        if (height(t->left->left) >= height(t->left->right))  
        {  
            rotateWithLeftChild(t);   //那么就是右旋
        }  
        else  
        {   
            doubleWithLeftChild(t);  //那么就是先右旋再左旋
        }  
  
    }  
    // 如果右子树的高度与左子树高度差大于实施平衡调整的限度  
    else if (height(t->right) - height(t->left) > AVLTree<Comparable>::ALLOW_IMBALANCE)  
    {  
          //如果右面子树高，那么就左旋
        if (height(t->right->right) >= height(t->right->left))  
        {  
            rotateWithRightChild(t);  
        }  
//左面子树高，那么就先右旋再左旋
        else  
        {  
            doubleWithRightChild(t);  
        }  
    }  
    else  
        ;  
  
    updateHeight(t);  
}  
  
/** 
* 通过遍历的方法查找x是否在树（或子树）t中 
*/  
template <typename Comparable>  
bool AVLTree<Comparable>::contains(  
    const Comparable &x,   
    typename AVLTree<Comparable>::AVLNode * t) const  
{  
    if (t == nullptr) // 遍历中未找到元素的中止条件  
        return false;  
    else if (x < t->element)  
        return contains(x, t->left);  
    else if (t->element < x)  
        return contains(x, t->right);  
    else // 如果 x 不大于 也 不小于t所指的节点中的元素，则x==t->element  
        return true;  
}  
  
/** 
* 右旋（左子树比右子树高2，并且新插入的元素在左子树的左边） 
* 此时以左子树（k1）为轴，它的根（k2）进行右旋 
* 可以理解为它的根在它的右边，所以右旋（在右边旋转） 
*       k2                      k1 
*      /  \                    /  \ 
*     k1   Z      -------     X    k2 
*    /  \                    /     / \ 
*   X    Y                  X'     Y   Z 
*  / 
* X' 
* X'可能在X的左边，也可以在X的右边。例子中假设在左边。 
*/  
template <typename Comparable>  
void AVLTree<Comparable>::rotateWithLeftChild(  
    typename AVLTree<Comparable>::AVLNode * & k2)  
{  
    //typename AVLTree<Comparable>::AVLNode * k1 = k2->left; // 获得k2的左节点  
    auto k1 = k2->left; // 使用auto定义  
    // 开始旋转  
//先将k1->right（也就是图中的Y，赋值给k2的左子树）
//然后将k2的所有节点赋值给k1的右子树
    k2->left = k1->right;   
    k1->right = k2;  
    //更新高度, 先更新k2可以，更新k1时减少一次height函数的调用  
    k2->height = max(height(k2->left), height(k2->right)) + 1;//等价于updateHeight(k2)  
    k1->height = max(height(k1->left), k2->height) + 1;  
  
    k2 = k1;  //更新根节点
      
}  
  
/** 
* 左旋（右子树比左子树高2，并且新插入的元素在右子树的右边） 
* 此时以右子树(k1)为轴，它的根(k2)进行左旋 
* 可以理解为它的根在它的左边，所以左旋（在左边旋转） 
*      K2                           K1 
*     /  \                         /  \ 
*    X    k1         -----        K2   Z 
*         / \                    /  \   \ 
*        Y   Z                  X    Y   Z' 
*             \ 
*              Z' 
* Z'可能在Z的左边，也可以在Z的右边。例子中假设在右边。 
**/  
template <typename Comparable>  
void AVLTree<Comparable>::rotateWithRightChild(  
    typename AVLTree<Comparable>::AVLNode * & k2)  
{  
    //typename AVLTree<Comparable>::AVLNode * k1 = k2->right;  
    auto k1 = k2->right; // 使用auto定义  
    // 开始旋转  
    k2->right = k1->left;  
    k1->left = k2;  
    //更新高度, 先更新k2可以减少一次height函数的调用  
    k2->height = max(height(k2->left), height(k2->right)) + 1;  
    k1->height = max(k2->height, height(k1->right)) + 1;   
  
    k2 = k1;  
}  
  
/** 
* 左右双旋（左子树K1比右子树D高2，并且新插入的元素在左子树K1的右边K2） 
* 第一步：对左子树k1进行一次左旋(轴为k2) 
* 第二步：对整个树k3进行一次右旋（轴为k2） 
*       k3                k3              k2 
*      /  \              /  \            /  \ 
*     k1   D    ----    k2   D  ----    k1   k3 
*    / \               / \             / \   / \ 
*   A   k2            k1  C           A   B  C  D 
*       / \          / \ 
*      B   C        A   B 
* 注：一般来说，只会有B或C一个存在，就会进行树的平衡调整 
*/  
template <typename Comparable>  
void AVLTree<Comparable>::doubleWithLeftChild(  
    typename AVLTree<Comparable>::AVLNode * & k3)  
{  
    rotateWithRightChild(k3->left);  //先进行一次左旋
    rotateWithLeftChild(k3);  //再进行一次右旋
}  
  
  
/** 
* 右左双旋（右子树K1比左子树A高2，并且新插入的元素在右子树K1的左边K2） 
* 第一步：对右子树k1进行一次右旋（轴为k2） 
* 第二步：对整个树k3进行一次左旋（轴为k2） 
*      k3              k3                 k2 
*     /  \            /  \               /  \ 
*    A    k1   ----  A    k2     ----  k3    k1 
*        / \             /  \         /  \  /  \ 
*       K2  D           B    k1      A    B C   D 
*      / \                  /  \ 
*     B   C                C    D 
*注：一般来说，只会有B或C一个存在，就会进行树的平衡调整 
*/  
template <typename Comparable>  
void AVLTree<Comparable>::doubleWithRightChild(  
    typename AVLTree<Comparable>::AVLNode * & k3)  
{  
    rotateWithLeftChild(k3->right);  
    rotateWithRightChild(k3);  
}  
#endif  //AVL_TREE_H  

我就按代码行序来总结：

1、定义了一个private clone函数（217行，296行），供拷贝构造函数（17行）和赋值操作符函数调用（122行）。

2、分别定义了public函数和对应的private函数，从而能够使用递归的方式实现一些功能，比如findMax和findMin。

3、树的深度优先遍历分为三种，前序遍历，中序遍历和后序遍历，因此在打印树的函数中，可以通过参数指定是通过什么方法进行遍历。为了更加清楚的表现出遍历的形式，使用enum定义了一些常量（13行），供printTree（71行使用）。由于printTree有两个参数，而且都有默认的参数。由于有默认参数的形参应该放在形参列表的末尾，而且我觉得经常使用的参数时调整打印的顺序，第一个参数是接收打印顺序，第二个参数时接收打印到的输出流。然后通过switch语句选择打印的方式，调用不同的私有函数。

在应用程序部分，就能使用t.printTree(AVLTree<int>::INORDER);来清晰明白的调用需要使用的打印方法（t是一个AVLTree<int>类型的对象）。

4、135行定义AVLNode中，保存了节点的高度信息（这是一般的二叉搜索树没有的）

5、在二叉搜索树的程序中，定义remove函数和insert函数为const，这是因为一般的二叉搜索树其实只是保存了一个指向根节点的指针，const可以保证指针的值不变，但是所指的根节点里面的内容（注意：指针的内容没变）如果修改了，也是可以通过编译的。然而在AVL树中，我们可能会因为调整数的平衡使得根节点所指的向的节点，比如本来指向A节点，由于调整树，可能树根就变成B节点了，这时候A和B的地址是不一样的，所以AVLTree对象中的成员m_root的值会变化，因此remove函数和insert函数不能再为const了。

6、149行定义了一个静态常量。由于静态常量需要在一开始就赋值，所以在类定义的时候就赋值了。

7、224~280行是如何旋转的方法，函数的定义在（569行-639行）。里面写了我是如何理解左旋右旋的，并且附上了过程图。

8、我以前定义模板类的时候都把成员函数的实现写在类定义里面。这次我把成员函数的实现分离出来了，遇到了不少问题。最主要的就是在135行定义了一个AVLNode的struct，如果在分离形势下要使用这个结构体类型的对象，应该显式的声明其为AVLNode<T> 中的类型：typename AVLTree<Comparable>::AVLNode。

9、在类的成员函数实现的过程中，可以使用auto免去写长长的类型的痛苦：比如427~428行。

10、562行也可以像注释那样写，但是563行直接写可以免去调用一次height函数

然后是我的测试代码：testDemo.cpp

[cpp]view plain copy
#include<iostream>  
#include<random>  
#include<ctime>  
using namespace std;  
  
#include"AVLTree.h"  
  
int main()  
{  
    AVLTree<int> t; // 创建一个AVL叉搜索树  
  
    int a[16] = { 1, 2, 3, 4, 5, 6,  
        7, 8, 9, 10, 11, 12,  
        13, 14, 15, 16 };  
  
    cout << "==== 测试插入(先插入1~8，插入15~9)：" << endl;  
    for (size_t i = 0; i < 8; ++i)  
    {  
        t.insert(a[i]);  
    }  
  
    for (size_t i = 15; i >= 8; --i)  
    {  
        t.insert(a[i]);  
    }  
      
    cout << "==== 测试中序打印：" << endl;  
    t.printTree(AVLTree<int>::INORDER);  
    cout << "==== 测试前序打印：" << endl;  
    t.printTree(AVLTree<int>::PREORDER);  
  
      
    cout << "==== 测设删除：" << endl;  
    for (size_t i = 0; i < 16; i+=2)  
    {  
        t.remove(i);  
    }  
    t.printTree();  
      
    cout << "==== 测试拷贝构造函数：" << endl;  
    AVLTree<int> t2(t);  
    t2.printTree();  
      
    cout << "==== 测试赋值操作：" << endl;  
    AVLTree<int> t3;  
    t3 = t;  
    t.printTree();  
      
    cout << "==== 测试最大最小值：" << endl;  
    cout << "最大值：" << t.findMax() << endl;  
    cout << "最小值：" << t.findMin() << endl;  
      
    return 0;  
  
}  

运行结果如图：

数据结构中AVL的c++实现

通过中序，我们可以看出这个树是一棵二叉搜索树，然后通过中序和前序，我画出了树的形状

数据结构中AVL的c++实现

可以看出，这棵树是平衡的，也就是说这个AVL树的旋转算法的实现目前来看没有问题

以下是后面的结果

数据结构中AVL的c++实现

数据结构中AVL的c++实现

相关推荐