bst, avl, c++, inheritance, template, two days - 行者无疆 始于足下 - 行走,思考,在路上

bst, avl, c++, inheritance, template, two days

xiaohanyu posted @ Thu, 03 Dec 2009 06:03:53 +0800 in Algorithm with tags c++ windows bst avl , 3935 readers

鉴于大二上年幼无知加上某些特殊的原因,导致我大三才开始修读高级数据结构。同一屋子大二的小朋友们上课,百般滋味,心中自知。第一次课迟到了,下课的时候随便找了两个学弟,算是组了个队,并申请做Project1(因为开始的Project)会比较简单。

实践起来也不是很难,就是让你比较下BinarySearchTree, AVL Tree和Splay Tree的插入删除效率的问题。两个学弟看样子都不愿意编码,于是乎,编码的重担就落在了我这个学长身上。可是只有我自己知道,我数据结构学的实在不咋的,C++又是个半吊子。唉,谁让咱是学长呢?

学长嘛,自然要有个学长的样子。于是乎,C++、Template、Inheritance、Polymorphism,能用上的都用上……呵呵。不过主要是想练一下手。C++ Primer虽然看了大半,却没有多少应用的机会。这也算是一个练习吧。

写着写着就知道,C++的强大是一把双刃剑,强大到你无法驾驭,尤其是应用了模板后,各种小问题,都是以前闻所未闻的。比如模板的分离编译问题,看书,查资料就花了两个小时。加上昨天下午吐血恶心的同步时序电路的逻辑实验,做的我都想哭了。所以这么看上去很简单的project,我竟然写了接近两天,倍感惭愧。

不过总算出来了。但是有个瑕疵,avl的删除功能有些小问题,可能跟Balance函数和指针的引用问题有关。gdb我用的不熟,转到强大的windows下的visual studio 2008下,调试了3个小时,找到错误所在,但是却不知道怎么改正。泪奔。

计算几何最终还是低空坠毁,唉,不提也罢,看来以后不能乱选课,选了课不能随便混混。混不好就低空坠毁。你说你没事选这么一门前沿课程干嘛,你是这块料嘛……

计算几何过后开始准备计算理论的期中考试。什么有穷自动机,正则语言,上下文无关文法,等等,计算理论基础的中文版,每个小时3页,龟速前进,发现还是太抽象,看不大懂,又找来一本计算理论导引,两本结合着看,顿觉顺畅很多,看来计算机的书还是要原汁原味的英文啊。

感觉计算理论期中还不错。周一被导师叫去公司,让我参加项目,大意是让我写一个TextArea。项目代码有四万左右,光理清这个体系,补windows编程的基础知识就花了我三四天的时间。终于搞明白了什么叫windows ce,什么叫GDI,学会了windows下svn的基本用法。可是看windows ce的书还是一头雾水,什么HINSTANCE,WINAPI WinMain(),叉叉的。基本流程我还不懂。于是去找windows经典书目的书单,看到多人推荐Charles Petzoldwindows程序设计,吐血买了下来,花了150元。Microsoft的书真tn的贵。

不过书是好书。周六周日周一断续看了三天,看了四章,120页,顿时明白了很多。个人windows的技术更新太快,不想unix,二十年前的vim、emacs、grep,等,万古不变。掌握win32 API才是一切的根本。永远不要指望跟上Microsoft的脚步。

只不过到现在导师的项目还没有开工,我还夸下海口自不量力要一周写出来。这可如何是好。还有图形学作业,操作系统作业,实验的作业,呃……少壮不努力,老大做it,大二不学习,大三干苦力。要努力。恩。

BinarySearchTree.h:

#ifndef _BINARYSEARCHTREE_H_
#define _BINARYSEARCHTREE_H_

#include <iostream>
#include <stack>
using namespace std;

/// 三种遍历方式
#define PREORDERTRAVERSE 0
#define INORDERTRAVERSE 1
#define POSTORDERTRAVERSE 2

/// 求两个元素的最大值
#define max(x, y) ((x > y) ? (x) : y)

/**
 * @class BinaryNode
 * @brief 树的结点,为了方便BST和AVL用了同一种结构。BST中所有结点的height域为默认值
 */

template<typename Comparable>
struct BinaryNode
{
    Comparable element;
    BinaryNode* left;
    BinaryNode* right;

    int height;

    BinaryNode(const Comparable &theElement, BinaryNode *lt, BinaryNode *rt, const int theHeight = 0)
        : element(theElement), left(lt), right(rt), height(theHeight) {}
};

/**
 * @class BinarySearchTree
 * @brief 实现了常见的删除,插入功能。并作为AVL树的基类
 */

template<typename Comparable>
class BinarySearchTree
{
public:
    BinarySearchTree();

    ~BinarySearchTree();

    BinaryNode<Comparable>*& GetRoot();
   
    void BuildBinaryTree(Comparable *x, int length);

    const Comparable& FindMin() const;
    const Comparable& FindMax() const;
    bool Contains(const Comparable &x) const;
    bool IsEmpty() const;
    void TraverseTree(int type);

    void MakeEmpty();

    virtual void Insert(const Comparable &x);
    virtual void Remove(const Comparable &x);


private:
    BinaryNode<Comparable> *root;   
    virtual void Insert(const Comparable &x, BinaryNode<Comparable> *&t) const;
    virtual void Remove(const Comparable &x, BinaryNode<Comparable> *&t) const;
    BinaryNode<Comparable>* FindMin(BinaryNode<Comparable> *&t) const;
    BinaryNode<Comparable>* FindMax(BinaryNode<Comparable> *&t) const;
    bool Contains(const Comparable &x, BinaryNode<Comparable> *&t) const;
    void MakeEmpty(BinaryNode<Comparable> *&t);

    void PreOrderTraverse(BinaryNode<Comparable> *&t);
    void InOrderTraverse(BinaryNode<Comparable> *&t);
    void PostOrderTraverse(BinaryNode<Comparable> *&t);
};

/**
 * 构造函数,默认root=NULL
 *
 *
 * @return
 */

template<typename Comparable>
BinarySearchTree<Comparable>::BinarySearchTree() : root(NULL){}

/**
 * 析构函数
 *
 *
 * @return
 */

template<typename Comparable>
BinarySearchTree<Comparable>::~BinarySearchTree()
{
    MakeEmpty();
}

/**
 * 得到根节点的引用
 *
 *
 * @return 返回根节点的引用
 */

template<typename Comparable>
BinaryNode<Comparable>*& BinarySearchTree<Comparable>::GetRoot()
{
    return root;
}

/**
 * 建立BST树,通过数组的方式传入元素,调用Insert(x)函数
 *
 * @param x
 * @param length
 */

template<typename Comparable>
void BinarySearchTree<Comparable>::BuildBinaryTree(Comparable *x, int length)
{
    for (int i = 0; i < length; ++i)
    {
        Insert(x[i]);
    }
}

/**
 * @return BST中的最小值
 */

template<typename Comparable>
const Comparable& BinarySearchTree<Comparable>::FindMin() const
{   
    return FindMin(root)->element;
}

/**
 * @return BST中的最大值
 */

template<typename Comparable>
const Comparable& BinarySearchTree<Comparable>::FindMax() const
{
    return FindMax(root)->element;
}

/**
 * 测试x是否在BST中,调用私有函数Contains(x, root)
 *
 * @param x
 *
 * @return
 */

template<typename Comparable>
bool BinarySearchTree<Comparable>::Contains(const Comparable &x) const
{
    return Contains(x, root);
}

/**
 * 测试树是否为空
 *
 *
 * @return
 */

template<typename Comparable>
bool BinarySearchTree<Comparable>::IsEmpty() const
{
    if (root == NULL)
    {
        return true;
    }

    return false;
}

/**
 * 以三种方式遍历树
 *
 * @param type 遍历树的方式
 */

template<typename Comparable>
void BinarySearchTree<Comparable>::TraverseTree(int type)
{
    if (type == PREORDERTRAVERSE)
    {
        cout << "PreOrderTraverse the tree:" << endl;
        PreOrderTraverse(root);
        cout << endl << "PreOrderTraverse ends." << endl;
    }

    if (type == INORDERTRAVERSE)
    {
        cout << "InOrderTraverse the tree:" << endl;
        InOrderTraverse(root);
        cout << endl << "InOrderTraverse ends." << endl;
    }

    if (type == POSTORDERTRAVERSE)
    {
        cout << "PostOrderTraverse the tree:" << endl;
        PostOrderTraverse(root);
        cout << endl << "InOrderTraverse ends." << endl;
    }
}

/**
 * 清空BST树
 *
 */

template<typename Comparable>
void BinarySearchTree<Comparable>::MakeEmpty()
{
    MakeEmpty(root);
}

/**
 * 向BST中插入一个元素
 *
 * @param x 待插入的元素
 */

template<typename Comparable>
void BinarySearchTree<Comparable>::Insert(const Comparable &x)
{
    Insert(x, root);
}

/**
 * 从BST中删除一个元素
 *
 * @param x 被删除的元素
 */

template<typename Comparable>
void BinarySearchTree<Comparable>::Remove(const Comparable &x)
{
    Remove(x, root);
}

/**
 * 向树根为t的树中插入一个元素
 *
 * @param x 待插入的元素
 * @param t 树根
 */

template<typename Comparable>
void BinarySearchTree<Comparable>::Insert(const Comparable &x, BinaryNode<Comparable> *&t) const
{
    if (t == NULL)
    {
        t = new BinaryNode<Comparable>(x, NULL, NULL, -3);
    }
    else if (x < t->element)
    {
        Insert(x, t->left);
    }
    else if (x > t->element)
    {
        Insert(x, t->right);
    }
    else
        ; //dupicate; you can do something, of course   
}

/**
 * 从树根为t的树中删除元素
 *
 * @param x 被删除的元素
 * @param t 树根
 */

template<typename Comparable>
void BinarySearchTree<Comparable>::Remove(const Comparable &x, BinaryNode<Comparable> *&t) const
{
    if (t == NULL)
    {
        return;
    }
    else if (x < t->element)
    {
        Remove(x, t->left);
    }
    else if (x > t->element)
    {
        Remove(x, t->right);
    }
    else if (t->left != NULL && t->right != NULL)
    {
        t->element = FindMin(t->right)->element;
        Remove(t->element, t->right);
    }
    else
    {
        BinaryNode<Comparable> *oldNode = t;
        t = (t->left != NULL) ? t->left : t->right;
        delete oldNode;
    }
}


template<typename Comparable>
BinaryNode<Comparable>* BinarySearchTree<Comparable>::FindMin(BinaryNode<Comparable> *&t) const
{
    if (t != NULL)
    {
        while(t->left != NULL)
            t = t->left;
    }

    return t;
}

template<typename Comparable>
BinaryNode<Comparable>* BinarySearchTree<Comparable>::FindMax(BinaryNode<Comparable> *&t) const
{
    if (t != NULL)
    {
        while(t->right != NULL)
            t = t->right;
    }

    return t;
}

template<typename Comparable>
bool BinarySearchTree<Comparable>::Contains(const Comparable &x, BinaryNode<Comparable> *&t) const
{
    if (t == NULL)
    {
        return false;
    }
    else if (x < t->element)
    {
        return Contains(x, t->left);
    }
    else if (x > t->element)
    {
        return Contains(x, t->right);
    }
    else
        return true;
}

template<typename Comparable>
void BinarySearchTree<Comparable>::MakeEmpty(BinaryNode<Comparable> *&t)
{
    if (t != NULL)
    {
        MakeEmpty(t->left);
        MakeEmpty(t->right);
        delete t;
    }

    t = NULL;
}

/**
 * 前序遍历
 *
 * @param t
 */

template<typename Comparable>
void BinarySearchTree<Comparable>::PreOrderTraverse(BinaryNode<Comparable> *&t)
{
    if (t != NULL)
    {
        cout << t->element << " ";
        PreOrderTraverse(t->left);
        PreOrderTraverse(t->right);
    }
}

/**
 * 中序遍历
 *
 * @param t
 */

template<typename Comparable>
void BinarySearchTree<Comparable>::InOrderTraverse(BinaryNode<Comparable> *&t)
{
    if (t != NULL)
    {
        InOrderTraverse(t->left);
        cout << t->element << " ";
        InOrderTraverse(t->right);
    }
}

/**
 * 后序遍历
 *
 * @param t
 */


template<typename Comparable>
void BinarySearchTree<Comparable>::PostOrderTraverse(BinaryNode<Comparable> *&t)
{
    if (t != NULL)
    {
        PostOrderTraverse(t->left);
        PostOrderTraverse(t->right);
        cout << t->element << " ";
    }
}

/**
 * @class AVLTree
 * @brief 由于AVLTree本身是一种改进的BST树,所以绝大多数特性继承自BST树。其中的Insert()和Remove方法和BST树中不同,因此在BST类中将此方法声明为virtual function
 */

template<typename Comparable>
class AVLTree : public BinarySearchTree<Comparable>
{
public:
    AVLTree();
    ~AVLTree();
    int GetHeight();
    void Insert(const Comparable &x);
    void Remove(const Comparable &x);
protected:
    int GetHeight(BinaryNode<Comparable> *&t);
    void Insert(const Comparable &x, BinaryNode<Comparable> *&t);
    void Remove(const Comparable &x, BinaryNode<Comparable> *&t);
    void SingleRotateLeftChild(BinaryNode<Comparable> *&k2);
    void SingleRotateRightChild(BinaryNode<Comparable> *&k2);
    void DoubleRotateLeftChild(BinaryNode<Comparable> *&k3);
    void DoubleRotateRightChild(BinaryNode<Comparable> *&k3);
    void Balance(BinaryNode<Comparable> *&t);
};

/**
 * 构造函数,调用BST基类的构造函数
 *
 *
 * @return
 */

template<typename Comparable>
AVLTree<Comparable>::AVLTree() : BinarySearchTree<Comparable>::BinarySearchTree()
{
    //  BinaryNode<Comparable>* root = BinarySearchTree<Comparable>::GetRoot();
//    root = NULL;
}

/**
 * 析构函数,调用基类的BST::MakeEmpty()
 *
 *
 * @return
 */

template<typename Comparable>
AVLTree<Comparable>::~AVLTree()
{
    BinarySearchTree<Comparable>::MakeEmpty();
}

/**
 * 得到整棵AVL树的高度
 *
 *
 * @return
 */

template<typename Comparable>
int AVLTree<Comparable>::GetHeight()
{
    BinaryNode<Comparable>*& root = BinarySearchTree<Comparable>::GetRoot();
    return GetHeight(root);
}

/**
 * 向AVL中插入元素x
 *
 * @param x 待插入的元素
 */

template<typename Comparable>
void AVLTree<Comparable>::Insert(const Comparable &x)
{
    BinaryNode<Comparable>*& root = BinarySearchTree<Comparable>::GetRoot();
    Insert(x, root);
}

/**
 * 从AVL中删除元素x
 *
 * @param x 被删除的元素
 */


template<typename Comparable>
void AVLTree<Comparable>::Remove(const Comparable &x)
{
    BinaryNode<Comparable>*& root = BinarySearchTree<Comparable>::GetRoot();
    Remove(x, root);
}

/**
 * 得到结点t的高度
 *
 * @param t
 *
 * @return
 */

template<typename Comparable>
int AVLTree<Comparable>::GetHeight(BinaryNode<Comparable> *&t)
{
    return t == NULL ? -1 : t->height;
}


template<typename Comparable>
void AVLTree<Comparable>::Insert(const Comparable &x, BinaryNode<Comparable> *&t)
{
    if (t == NULL)
    {
        t = new BinaryNode<Comparable>(x, NULL, NULL);
    }

    else if (x < t->element)
    {
        Insert(x, t->left);
        Balance(t);
        // if (GetHeight(t->left) - GetHeight(t->right) == 2)
        // {
        //     if (x < t->left->element)
        //     {
        //         SingleRotateLeftChild(t);
        //     }
        //     else
        //         DoubleRotateLeftChild(t);
        // }
    }
    else if (x > t->element)
    {
        Insert(x, t->right);
        Balance(t);
        // if (GetHeight(t->right) - GetHeight(t->left) == 2)
        // {
        //     if (t->right->element < x)
        //     {
        //         SingleRotateRightChild(t);
        //     }
        //     else
        //         DoubleRotateRightChild(t);
        // }
    }
    else
        ;
       
    t->height = max(GetHeight(t->left), GetHeight(t->right)) + 1;
}

/**
 * 有个小bug,弄了一天也没弄出来,可能问题在Balance()和指针的引用上
 *
 * @param x
 * @param t
 */

template<typename Comparable>
void AVLTree<Comparable>::Remove(const Comparable &x, BinaryNode<Comparable> *&t)
{
    static stack<BinaryNode<Comparable>*> tStack;/// 定义一个静态堆栈,存储访问结点的路径
    int tSize = tStack.size();/// 得到栈的大小
   
    if (t == NULL)
    {
        return;
    }
    else if (x < t->element)
    {
        tStack.push(t);
        cout << "traverse through " << t->element << endl;
        Remove(x, t->left);
    }
    else if (x > t->element)
    {
        tStack.push(t);
        cout << "traverse through " << t->element << endl;
        Remove(x, t->right);
    }
    else if (t->left != NULL && t->right != NULL)
    {
        tStack.push(t);
        cout << "traverse through " << t->element << endl;
       
        BinaryNode<Comparable>*& oldT = t->right;
       
        while (oldT->left != NULL)
        {
            tStack.push(oldT);
            cout << "traverse through " << oldT->element << endl;
            oldT = oldT->left;
        }

        t->element = oldT->element;
        Remove(t->element, t->right);
    }
    else
    {
        BinaryNode<Comparable>*& oldNode = t;
        t = (t->left != NULL) ? t->left : t->right;
        delete oldNode;
    }

    BinaryNode<Comparable>* tempStack;

    tSize = tStack.size(); /// 更新堆栈大小

   
    for (int i = 0; i < tSize; i++)
    {
        tempStack = tStack.top();/// 回溯访问结点
        Balance(tempStack);/// 对每个结点做Balance处理
        tStack.pop();/// 已经做过Balance处理的结点出栈
    }/// 此处可以进一步优化
    return ;   
}


template<typename Comparable>
void AVLTree<Comparable>::SingleRotateLeftChild(BinaryNode<Comparable> *&k2)
{
    BinaryNode<Comparable> *k1 = k2->left;
    k2->left = k1->right;
    k1->right = k2;
    k2->height = max(GetHeight(k2->left), GetHeight(k2->right)) + 1;
    k1->height = max(GetHeight(k1->left), k2->height) + 1;
    k2 = k1;
}

template<typename Comparable>
void AVLTree<Comparable>::SingleRotateRightChild(BinaryNode<Comparable> *&k1)
{
    BinaryNode<Comparable> *k2 = k1->right;
    k1->right = k2->left;
    k2->left = k1;
    k1->height = max(GetHeight(k1->left), GetHeight(k1->right)) + 1;
    k2->height = max(k1->height, GetHeight(k2->right)) + 1;
    k1 = k2;
}

template<typename Comparable>
void AVLTree<Comparable>::DoubleRotateLeftChild(BinaryNode<Comparable> *&k3)
{
    SingleRotateRightChild(k3->left);
    SingleRotateLeftChild(k3);
}

template<typename Comparable>
void AVLTree<Comparable>::DoubleRotateRightChild(BinaryNode<Comparable> *&k1)
{
    SingleRotateLeftChild(k1->right);
    SingleRotateRightChild(k1);
}

/**
 * 计算t的平衡因子,分为四种不同情况分别调用不同函数处理
 *
 * @param t 树根
 */

template<typename Comparable>
void AVLTree<Comparable>::Balance(BinaryNode<Comparable> *&t)
{
    if (GetHeight(t->left) - GetHeight(t->right) == 2)
    {
        if (GetHeight(t->left->left) > GetHeight(t->left->right))
        {
            SingleRotateLeftChild(t);
        }
        else if (GetHeight(t->left->left) < GetHeight(t->left->right))
        {
            DoubleRotateLeftChild(t);
        }
        else
            ;       
    }

    if (GetHeight(t->left) - GetHeight(t->right) == -2)
    {
        if (GetHeight(t->right->right) > GetHeight(t->right->left))
        {
            SingleRotateRightChild(t);
        }
        else if (GetHeight(t->right->right) < GetHeight(t->right->left))
        {
            DoubleRotateRightChild(t);
        }
        else
            ;
    }
}

#endif /* _BINARYSEARCHTREE_H_ */
 

main.cpp:

#include <iostream>
#include "BinarySearchTree.h"

using namespace std;

int main(int argc, char *argv[])
{
    int a[10] = {5, 9, 10, 1, 3, 6, 4, 7, 8, 2};

    AVLTree<int> avl;
    avl.BuildBinaryTree(a, 10);
    avl.Insert(11);
    avl.TraverseTree(0);

    avl.Remove(9);
    avl.TraverseTree(0);

    avl.Remove(10);
    avl.TraverseTree(0);
   
    return 0;
}
M said:
Sun, 20 Dec 2009 03:45:41 +0800

Hold on, that is the only way we could arrive where we want to be.
If feel tired, just have a rest, then, go on.


Login *


loading captcha image...
(type the code from the image)
or Ctrl+Enter
Host by is-Programmer.com | Power by Chito 1.3.3 beta | © 2007 LinuxGem | Design by Matthew "Agent Spork" McGee