《数据结构与STL》笔记和习题（5）

chapter8：二叉查找树

chapter9：AVL树

这两个就一起看了。因为AVL树是二叉查找树的一个升级版本，所以我就选择直接实现AVL树的基本功能，主要是find、erase、insert。

树节点：

struct Node {
T item;
int height;
Node *parent;
Node *left;
Node *right;

Node(): height(0), parent(NULL), left(NULL), right(NULL) {}
Node(const T& x):
item(x), height(0),parent(NULL), left(NULL), right(NULL) {}
};

AVL树除了要满足二叉查找树的要求外，还要求树上的任意节点N：

|height（N->left) - height(N->right)| <= 1，

即两个子树的高度差不能超过1，其中height（NULL） == -1。

基本思路：

1）find和二叉查找树一样，没有什么好说的。

2）insert

感觉书上讲得有点乱，没仔细看，找了《数据结构》（C语言版）和《数据结构和算法分析》C++来看了一下，

真是相当清楚，四种情况，一目了然，证明也是犀利。

LL: 在左子树的左子树插入并引起不平衡

LR：在左子树的右子树插入。。。

RL：在右子树的左子树插入。。。

RR：在右子树的右子树插入。。。

平衡失衡可以通过左右旋转搞定，并且神奇的是只要搞定插入路径上高度最低的不平衡点，其它个点

不会有影响。（具体大家看书去吧，我只是瞎扯扯）

为了偷懒，我实现的是递归版本，并且树节点中有一个高度字段，其实没有必要递归。

template <class T, class Compare>
void AVLTree<T, Compare>::insertNode(Node *parent, Node * &tree, const T& item) {
    if (tree == NULL) {
        tree = new Node(item);
        tree->parent = parent;
        adjustMinMaxInsert(tree);
        nodeCount++;
        return;
    }
    if (compare(item, tree->item) < 0) {
        insertNode(tree, tree->left, item);
        if (getHeight(tree->left) - getHeight(tree->right) == 2) {
            Node *child = tree->left;
            if (getHeight(child->left) > getHeight(child->right))
                leftRotation(tree); // LL
            else
                rlRotation(tree);   // LR
        }
    } else if (compare(item, tree->item) > 0) {
        insertNode(tree, tree->right, item);
        if (getHeight(tree->left) - getHeight(tree->right) == -2) {
            Node *child = tree->right;
            if (getHeight(child->left) < getHeight(child->right))
                rightRotation(tree); // RR
            else
                lrRotation(tree);    // RL
        }
    } else
        std::cout << "Item: " << item << " exists!" << std::endl;
    tree->height = maxHeight(tree->left, tree->right) + 1; // important
}

这里用指针引用Node * &tree，是个小技巧，不然在连接树的新节点时候要多写些代码，呵呵。

3）erase

基本书上没有给出解答，差不多都留作课后习题了。

我的思路和二叉查找树的erase类似，假设要删除的节点是N，

1. N至多只有一棵子树，删除N，从N的父亲节点开始平衡可能被破坏。

2. N有两棵子树，那么找N的后记节点（必定存在的，因为右子树不为空啊），将后继节点内容copy到当前节点，下面的任务改为删除后继节点。

从删除节点的父亲开始，不断查看是否需要左右旋转来调整平衡，直到根节点，（出现上面四种情况之一，就要需要旋转，这一点插入和删除是一致的）。

当然，要记得查看root指向的节点是否更换，父亲和儿子节点是否相互连接，不然会出奇怪的错误的。

template <class T, class Compare>
bool AVLTree<T, Compare>::erase(const T& item) {
    Iterator itr = find(item);
    if (!(itr != end()))
        return false; // Can't find such item.
    Node *tree = itr.position;
    // If both subtree is not empty, then find the successor.
    while (tree->left != NULL && tree->right != NULL) {
        Node *succ = successor(tree);
        tree->item = succ->item;
        tree = succ;
    }
    Node *parent = tree->parent;
    Node *child = tree->left ? tree->left : tree->right;
    adjustMinMaxErase(tree);

    if (child != NULL)
        child->parent = parent;
    if (parent != header) {
        if (parent->left == tree)
            parent->left = child;
        else
            parent->right = child;
        parent->height = maxHeight(parent->left, parent->right) + 1;
        adjustBalance(parent);
    } else
        root = child; // adjust root
    delete tree;
    nodeCount--;
    return true;
}

调整平衡。

template <class T, class Compare>
void AVLTree<T, Compare>::adjustBalance(Node * tree) {
    while (tree != NULL && tree != header) {
        tree->height = maxHeight(tree->left, tree->right) + 1;
        char flag = 'M';
        if (tree->parent != header)
            flag = tree->parent->left == tree ? 'L' : 'R';

        if (getHeight(tree->left) - getHeight(tree->right) == 2) {
            Node *child = tree->left;
            if (getHeight(child->left) >= getHeight(child->right))
                leftRotation(tree); // LL
            else
                rlRotation(tree);   // LR

        } else if (getHeight(tree->left) - getHeight(tree->right) == -2) {
            Node *child = tree->right;
            if (getHeight(child->left) <= getHeight(child->right))
                rightRotation(tree); // RR
            else
                lrRotation(tree);    // RR
        }

        if (flag == 'L')   // Concatenate parent and child.
            tree->parent->left = tree;
        else if (flag == 'R')
            tree->parent->right = tree;
        else {
            if (getHeight(root) < getHeight(tree))
                root = tree; // adjust root
        }
        tree = tree->parent;
    }
}

4）Iterator

迭代器功能，我又偷懒了，只实现了++itr, *itr, itr1 != itr2

在AVLTree里面加了个header字段，header->left指向第一个节点，header->right指向最后一个节点（其实这个没有必要，因为我没有实现--itr），header->parent = NULL。根节点root->parent = header，这都是为了方便，不然++itr就找不到header了，因为header是作为最后一个节点之后的节点的，即end()的返回值。

遇到的问题：

1）按书上的做法，我也用了function object，其实这就是标准的策略模式。

一开始，两个地方的模板声明都用了,结果出现shadows template parm ‘class T’的错误。

这个必须把其中一个T换成别的名字。

2）犯了一些傻错误

AVLTree>avlTree;  //error: >>不能相连，相连就是个运算符

friend class AVLTree; // class 不能落下

void AVLTree:: ... // 不能忘记写

附上源码： avlTree.zip   

完整的类定义：

template <class T, class Compare>
class AVLTree {
private:
    struct Node {
        T item;
        int height;
        Node *parent;
        Node *left;
        Node *right;

        Node(): height(0), parent(NULL), left(NULL), right(NULL) {}
        Node(const T& x):
            item(x), height(0),parent(NULL), left(NULL), right(NULL) {}
    };

    /* header: point to the node following the last one;
     * header->left: point to the fisrt node (which has
     *    the smallest item);
     * header->right: point to the last node (which has
     *    the largest item);
     */
    Node *header, *root;
    size_t nodeCount;
    Compare compare;  // object function

    inline int getHeight(const Node *tree) const;

    /* maxHeight:
     * Return the larger height between the left and right
     * subtree.
     */
    inline int maxHeight(const Node *left, const Node *right) const;

    /* Four different kinds of tree rotations, in order
     * to restore balance.
     */
    void leftRotation(Node * &tree);
    void rightRotation(Node * &tree);
    void lrRotation(Node * &tree);
    void rlRotation(Node * &tree);

    /* Get the successor(predecessor) of *ptr, following
     * the predefined order, s.t. compare.
     */
    Node* successor(Node *ptr) const;
    Node* predecessor(Node *ptr) const;

    /* Adjust header->left and header->right after inserting
     * or erasing nodes.
     */
    void adjustMinMaxInsert(Node *ptr);
    void adjustMinMaxErase(Node *ptr);

    /* Adjust tree balance after erasing nodes.*/
    void adjustBalance(Node * tree);

    /* An auxiliary function of insert with recursive manner.*/
    void insertNode(Node *parent, Node * &tree, const T& item);

public:
    class Iterator {
    private:
        friend class AVLTree;
        Node *position;

        Iterator(Node *pos): position(pos) {}
    public:
        Iterator() {};
        Iterator& operator++();
        inline T& operator*() const;
        inline bool operator!=(const Iterator& another) const;
    };

    AVLTree();
    ~AVLTree();

    /* For convenient check, print out the whole tree in
     * layer order.
     */
    void printTree() const;

    /* If insert new node successfully, return the iterator
     * pointing to the new node, otherwise return end().
     */
    Iterator insert(const T& item);

    /* Erasing nodes successfull, return true, otherwise
     * return false.
     */
    bool erase(const T& item);

    /* Return the iterator if find the corresponding item,
     * otherwise return end().
     */
    Iterator find(const T& item) const;

    inline Iterator begin() const;
    inline Iterator end() const;
    inline int treeHeight() { return getHeight(root); }
};