第十章

AVL树

10.1  基本概念

AVL树的复杂程度真是比二叉搜索树高了整整一个数量级——它的原理并不难弄懂,但要把它用代码实现出来还真的有点费脑筋。下面我们来看看:

10.1.1  AVL树是什么?

AVL树本质上还是一棵二叉搜索树(因此读者可以看到我后面的代码是继承自二叉搜索树的),它的特点是:

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

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

例如:

     5              5
    / \            / \
   2   6          2   6
  / \   \        / \
 1   4   7      1   4
    /              /
   3              3

上图中,左边的是AVL树,而右边的不是。因为左边的树的每个结点的左右子树的高度之差的绝对值都最多为1,而右边的树由于结点6没有子树,导致根结点5的平衡因子为2。

10.1.2  为什么要用AVL树?

有人也许要问:为什么要有AVL树呢?它有什么作用呢?

我们先来看看二叉搜索树吧(因为AVL树本质上是一棵二叉搜索树),假设有这么一种极端的情况:二叉搜索树的结点为1、2、3、4、5,也就是:

 1
  \
   2
    \
     3
      \
       4
        \
         5

聪明的你是不是发现什么了呢?呵呵,显而易见——这棵二叉搜索树其实等同于一个链表了,也就是说,它在查找上的优势已经全无了——在这种情况下,查找一个结点的时间复杂度是O(N)!

好,那么假如是AVL树(别忘了AVL树还是二叉搜索树),则会是:

   2
  / \
 1   4
    / \
   3   5

可以看出,AVL树的查找平均时间复杂度要比二叉搜索树低——它是O(logN)。也就是说,在大量的随机数据中AVL树的表现要好得多。

10.1.3  旋转

假设有一个结点的平衡因子为2(在AVL树中,最大就是2,因为结点是一个一个地插入到树中的,一旦出现不平衡的状态就会立即进行调整,因此平衡因子最大不可能超过2),那么就需要进行调整。由于任意一个结点最多只有两个儿子,所以当高度不平衡时,只可能是以下四种情况造成的:

  1. 对该结点的左儿子的左子树进行了一次插入。

  2. 对该结点的左儿子的右子树进行了一次插入。

  3. 对该结点的右儿子的左子树进行了一次插入。

  4. 对该结点的右儿子的右子树进行了一次插入。

情况1和4是关于该点的镜像对称,同样,情况2和3也是一对镜像对称。因此,理论上只有两种情况,当然了,从编程的角度来看还是四种情况。

第一种情况是插入发生在“外边”的情况(即左-左的情况或右-右的情况),该情况可以通过对树的一次单旋转来完成调整。第二种情况是插入发生在“内部”的情况(即左-右的情况或右-左的情况),该情况要通过稍微复杂些的双旋转来处理。

关于旋转的具体理论分析和例子请参阅教科书,我实在不想在这里重新打一次了……就此省略65535个字,原谅我吧,出来混,迟早要还的。

10.2  代码实现

二叉树的代码实现如下:

///////////////////////////////////////////////////////////////////////////////
//
//  FileName    :   avltree.h
//  Version     :   0.10
//  Author      :   Luo Cong
//  Date        :   2005-1-20 17:04:31
//  Comment     :  
//
///////////////////////////////////////////////////////////////////////////////

#ifndef __AVL_TREE_H__
#define __AVL_TREE_H__

#include "../../bstree/src/bstree.h"

template<typename T>
class CAVLTree : public CBSTree<T>
{
private:
    CBTNode<T>* Insert(const T &data, CBTNode<T> *p);

public:
    CBTNode<T>* SingleRotateWithLeft(CBTNode<T> *p);
    CBTNode<T>* DoubleRotateWithLeft(CBTNode<T> *p);
    CBTNode<T>* SingleRotateWithRight(CBTNode<T> *p);
    CBTNode<T>* DoubleRotateWithRight(CBTNode<T> *p);
    CBTNode<T>* Insert(const T &data);
    CBTNode<T>* Delete(const T &data);
};

template<typename T>
inline CBTNode<T>* CAVLTree<T>::SingleRotateWithLeft(CBTNode<T> *p)
{
    CBTNode<T> *p2;

    // rotate
    p2 = p->left;
    p->left = p2->right;
    p2->right = p;

    // update parent relationship
    p2->parent = p->parent;
    p->parent = p2;
    if (p->left)
        p->left->parent = p;

    // update root node if necessary
    if (p == m_pNodeRoot)
        m_pNodeRoot = p2;

    return p2;  // New root
}

template<typename T>
inline CBTNode<T>* CAVLTree<T>::DoubleRotateWithLeft(CBTNode<T> *p)
{
    p->left = SingleRotateWithLeft(p->left);
    return SingleRotateWithLeft(p);
}

template<typename T>
inline CBTNode<T>* CAVLTree<T>::SingleRotateWithRight(CBTNode<T> *p)
{
    CBTNode<T> *p2;

    // rotate
    p2 = p->right;
    p->right = p2->left;
    p2->left = p;

    // update parent relationship
    p2->parent = p->parent;
    p->parent = p2;
    if (p->right)
        p->right->parent = p;

    // update root node if necessary
    if (p == m_pNodeRoot)
        m_pNodeRoot = p2;

    return p2;  // New root
}

template<typename T>
inline CBTNode<T>* CAVLTree<T>::DoubleRotateWithRight(CBTNode<T> *p)
{
    p->right = SingleRotateWithLeft(p->right);
    return SingleRotateWithRight(p);
}

template<typename T>
inline CBTNode<T>* CAVLTree<T>::Insert(const T &data)
{
    return Insert(data, m_pNodeRoot);
}

template<typename T>
inline CBTNode<T>* CAVLTree<T>::Insert(const T &data, CBTNode<T> *p)
{
    if (NULL == p)
    {
        // Create and return a one-node tree
        p = new CBTNode<T>;
        if (NULL == p)
            return NULL;
        else
        {
            p->data = data;
            p->left = NULL;
            p->right = NULL;
            if (NULL == m_pNodeRoot)
            {
                m_pNodeRoot = p;
                m_pNodeRoot->parent = NULL;
            }
        }
    }
    // left child
    else if (data < p->data)
    {
        p->left = Insert(data, p->left);
        if (p->left)
            p->left->parent = p;

        if (2 == (GetDepth(p->left) - GetDepth(p->right)))
        {
            // left tree, need to do single rotation
            if (data < p->left->data)
                p = SingleRotateWithLeft(p);
            // right tree, need to do double rotation
            else
                p = DoubleRotateWithLeft(p);
        }
    }
    // right child
    else if (data > p->data)
    {
        p->right = Insert(data, p->right);
        if (p->right)
            p->right->parent = p;

        if (2 == (GetDepth(p->right) - GetDepth(p->left)))
        {
            // right tree, need to do single rotation
            if (data > p->right->data)
                p = SingleRotateWithRight(p);
            // left tree, need to do double rotation
            else
                p = DoubleRotateWithRight(p);
        }
    }
    // else data is in the tree already, we'll do nothing!

    return p;
}

template<typename T>
inline CBTNode<T>* CAVLTree<T>::Delete(const T &data)
{
    // not completed yet.
    return NULL;
}

#endif  // __AVL_TREE_H__

测试代码:

///////////////////////////////////////////////////////////////////////////////
//
//  FileName    :   avltree.cpp
//  Version     :   0.10
//  Author      :   Luo Cong
//  Date        :   2005-1-20 17:06:50
//  Comment     :  
//
///////////////////////////////////////////////////////////////////////////////

#include "avltree.h"

int main()
{
    CAVLTree<int> avltree;

#ifdef _DEBUG
    _CrtSetDbgFlag(_CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF);
#endif

    avltree.Insert(1);
    avltree.Insert(2);
    avltree.Insert(3);
    avltree.Insert(4);
}

10.3  说明

我的AVL树是从二叉搜索树继承而来的(还记得我的二叉搜索树又是从二叉树继承来的吗?^_^)。另外,由于水平的关系,我没有写出Delete()函数来,因此如果您使用了Delete(),那是不会有效果的。-_-b...

插入的核心思路是通过递归(又是递归!)找到合适的位置,插入新结点,然后看新结点是否平衡(平衡因子是否为2),如果不平衡的话,就分成两种大情况以及两种小情况:

  1. 在结点的左儿子(data < p->data)

  2. 在结点的右儿子(data > p->data)

代码已经写得很清楚了,我就不多废话了,关键在于动手去调试,这样才能弄明白。值得说明的是,当进行了旋转之后,必定会有结点的“父结点”是需要更新的,例如:

   2
  / \
 1   4
    / \
   3   5
        \
         6

上图是调整前的,下图是调整后的:

     4
    / \
   2   5
  / \   \
 1   3   6

可以看出,根结点2不平衡,是由于它的右儿子的右子树插入了新的结点6造成的。因此,这属于“外边”的情况,要进行一次单旋转。于是我们就把结点4调整上来作为根结点,再把结点2作为4的左儿子,最后把结点2的右儿子修改为原来的结点4的左儿子。

调整后的parent指针变化规律如下:

  1. 调整前的右儿子(调整后它就变为父亲了)的parent指针应该指向调整前的父亲(调整后它就变成左儿子了)的parent指针。

  2. 调整前的父亲(调整后它就变成左儿子了)的parent指针应该指向调整前的右儿子(调整后它就变成父亲了)。

  3. 调整前的父亲的右儿子的parent指针应该指向调整前的右儿子的左儿子。

很难理解是吗?我来联系到上图说明:

  1. 调整前的右儿子是结点4,调整后,它的parent指针应该指向调整前它的父亲的parent指针,也就是NULL,因为调整前结点4的父亲是结点2,而结点2是根结点,其parent指针为NULL。

  2. 调整前的父亲是结点2,调整后,它的parent指针应该指向调整前的右儿子(结点4)。

  3. 调整前的父亲的右儿子(也就是调整后的结点2的右儿子)应该指向调整前的右儿子(结点4)的左儿子(结点3)。

这是SingleRotateWithRight()里面对parent指针的处理,SingleRotateWithLeft()里面的道理也是相通的,只是顺序有点不同。

呵呵,希望没把您弄晕。^_^

AVL树就讲到这里了,如果您有兴趣,可以把Delete()函数写完,并请给我一份以便我学习。