如何在删除叶子后重新平衡 AVL 树

Question

这是我认为应该如何完成的（在阅读了D.S.Malik的"使用C++的数据结构"第252页之后）。我们从父级开始遍历指向已删除叶子的路径。对于此路径P的每个节点，我们执行下面介绍的操作。支持删除缩短了P的较短子树，Q是P较高的子树的根。让我们bf()表示balance_factor。

1. 如果|bf(P)|>1并bf(Q) = 0，则旋转P

2. 如果 |bf(P)|>1 和 bf(Q) 与 bf(P) 具有相同的符号，则旋转P

3. 如果|bf(P)|>1和bf(Q)与bf(P)有相反的符号，则先旋转Q，然后再旋转P（即使经过Q的旋转bf(P) = 0）

4. 如果|bf(P)|<2，则不对P执行任何操作，并继续P的父级

这是对的吗？

Answer 1

算法看起来不错。我已经在下面的C++程序的帮助下多次测试了它。函数Tree::remove()删除节点，函数Tree::rebalance_del()删除后重新平衡树。在此程序中，任何节点的删除都简化为删除一个子节点/叶节点（通过将节点的内容复制到其直接的前身）。该程序使用graphviz进行树可视化，并在Linux中工作。

#include<iostream>
#include<cstdlib>
#include<deque>
#include<vector>
#include<iterator>
#include<fstream>
#include<algorithm>
#include<set>
using namespace std;
template <typename elemType> 
class Tree;
template <typename elemType> 
class Node{
    friend class Tree<elemType>;
public:
    Node(elemType val): _val(val), _lchild(0), _rchild(0){ }
    elemType val() const { return _val; }
    elemType &val(){ return _val; }
    Node *lchild() const { return _lchild;}
    Node *&lchild() { return _lchild;}
    Node *rchild() const { return _rchild;}
    Node *&rchild() { return _rchild;}
    void insert(Node *temp);
    void graph(string filename);
    Node *find(elemType val);
    Node *find_parent(elemType val);
private:
    elemType _val;
    Node *_lchild;      
    Node *_rchild;
};
template <typename elemType>
class Tree{
public:
    Tree(): _root(0){}
    Tree(elemType *start, elemType *end);
    void insert(elemType val);
    int height(Node<elemType> *node);
    int balance_factor(Node<elemType> *node);
    bool rotate(Node<elemType> *parent, Node<elemType> *child);
    bool rotate_root();
    Node<elemType> *root(){ return _root;}
    void graph(string filename);
    Node<elemType> * find(elemType val);
    Node<elemType> * find_parent(elemType val);
    Node<elemType> * find_predsor(Node<elemType> *node);
    void remove(elemType val);
    void rebalance_del(Node<elemType> *node);
    void rotate_right(Node<elemType> *parent, Node<elemType> *node);
    void rotate_left(Node<elemType> *parent, Node<elemType> *node);
private:
    Node<elemType> *_root;  
};
template <typename elemType>
void Node<elemType>::insert(Node *temp)
{
        if (_val > temp->val() )
        {
            if (_lchild)
                _lchild->insert(temp);
            else
            {
                _lchild = temp;
            }
        }
        else
        {
            if (_rchild)
                _rchild->insert(temp);
            else
            {
                _rchild = temp;
            }
        }
}
template <typename elemType>
void Node<elemType>::graph(string filename)
{
        ofstream out_file(filename.c_str(),ios_base::app);
        if (_lchild)
        {
            out_file << _val << "->" << _lchild->val() << ";" << endl;
            _lchild->graph(filename);
        }
        if (_rchild)
        {
            out_file << _val << "->" << _rchild->val() << ";" << endl;
            _rchild->graph(filename);
        }
}
template <typename elemType>
Node<elemType> *Node<elemType>::find(elemType val)
{
        if (_val == val)
                return this;
        else if (_val > val)
        {
                if (_lchild)
                    return _lchild->find(val);
        }
        else
        {
                if (_rchild)
                    return _rchild->find(val);
        }
        return 0;           
}
template <typename elemType>
Node<elemType> *Node<elemType>::find_parent(elemType val)
{
        if ( (_lchild && _lchild->val() == val) || (_rchild && _rchild->val() == val) )
                return this;
        else if (_val > val)
        {
                if (_lchild)
                    return _lchild->find_parent(val);
        }
        else
        {
                if (_rchild)
                    return _rchild->find_parent(val);
        }
        return 0;       
}   
template <typename elemType>
Tree<elemType>::Tree(elemType *start, elemType *end): _root(0)
{
        while(start != end)
        {
            insert(*start);
            ++start;        
        }
} 
template <typename elemType>
void Tree<elemType>::insert(elemType val)
{
        Node<elemType> *temp = new Node<elemType>(val);
        if (!_root)
        {
            _root = temp;
            return;
        }
        else
            _root->insert(temp);    
        Node<elemType> *child = find_parent(val); 
        while (child != _root)
        {       
            Node<elemType> *parent = find_parent(child->val());
            rotate(parent, child);
            child = parent; 
        }
        rotate_root();
}
template <typename elemType>
int Tree<elemType>::height(Node<elemType> *node)
{
        if (!node)
                return 0;
        return max( height(node->lchild()), height(node->rchild()) ) + 1;       
}
template <typename elemType>
int Tree<elemType>::balance_factor(Node<elemType> *node)
{
        if (!node)
                return 0;
        return height( node->rchild() ) - height( node->lchild() );     
}
template <typename elemType>
bool Tree<elemType>::rotate(Node<elemType> *parent, Node<elemType> *child)
{
        if (!parent || !child)
            return false;
        bool to_right;
        int bf = balance_factor(child);
        if (bf < -1 )
            to_right = true;
        else if (bf > 1 )
            to_right = false;
        else
            return false;       
        if(to_right)
        {
                Node<elemType> *gchild = child->lchild();
                if ( balance_factor (gchild) > 0 )
                        rotate_left(child,gchild);
                rotate_right(parent,child);
        }
        else
        {
                Node<elemType> *gchild = child->rchild();
                if ( balance_factor (gchild) < 0 )
                        rotate_right(child,gchild);
                rotate_left(parent,child);
        }
}
template <typename elemType>
bool Tree<elemType>::rotate_root()
{
        if (!_root)
            return false;
        bool to_right;
        int bf = balance_factor(_root);
        if (bf < -1 )
            to_right = true;
        else if ( bf > 1 )
            to_right = false;
        else
            return false;       
        if(to_right)
                rotate_right(0,_root);
        else
                rotate_left(0,_root);
        return true;
}
template <typename elemType>
void Tree<elemType>::graph(string filename)
{
        ofstream out_file(filename.c_str(),ios_base::out);
        out_file << "digraph G{n graph [ordering="out"];" << endl;
        out_file.close();
        if (!_root)
            return;
        _root->graph(filename);
        out_file.open(filename.c_str(),ios_base::app);
        out_file << "}";                
}

template <typename elemType>
Node<elemType> * Tree<elemType>::find(elemType val)
{
        if (!_root)
            return 0;
        return _root->find(val);                
}
template <typename elemType>
Node<elemType> * Tree<elemType>::find_parent(elemType val)
{
        if (!_root)
            return 0;
        return _root->find_parent(val);             
}
template <typename elemType>
Node<elemType> *Tree<elemType>::find_predsor(Node<elemType> *node)
{
        if (!node || !node->lchild())
            return 0;
        Node<elemType> *temp = node->lchild();
        while(temp && temp->rchild())
                temp = temp->rchild();
        return temp;    
}
template <typename elemType>
void Tree<elemType>::remove(elemType val)
{
        if (!_root)
            return;
        Node<elemType> *to_remove;
        if ( ! (to_remove = find(val)) )
        {
                cout << val << " is not present" << endl;
                return;
        }
        Node<elemType> *node = find_parent(val); 
        Node<elemType> *predsor = find_predsor(to_remove);
        if ( to_remove->lchild() && to_remove->rchild() )
        {
                node = find_parent(predsor->val());
                elemType temp = to_remove->val();
                to_remove->val() = predsor->val();
                predsor->val() = temp;
                to_remove = predsor;
        }
        if ( node->rchild() == to_remove )
                if (to_remove->lchild())
                        node->rchild() = to_remove->lchild();
                else
                        node->rchild() = 0;
        else
                if (to_remove->lchild())
                        node->lchild() = to_remove->lchild();
                else
                        node->lchild() = 0;
        delete to_remove;
        cout << "Node " << val << " was removed" << endl;
        rebalance_del(node);
}
template <typename elemType>
void Tree<elemType>::rebalance_del(Node<elemType> *node)
{   
        while (node)
        {       
            Node<elemType> *parent = find_parent(node->val());
            int bfp = balance_factor(node);
            if (bfp > 1)
            {
                int bfq = balance_factor(node->rchild());
                if (bfq > -1)
                        rotate_left(parent,node);
                else
                {
                        rotate_right(node,node->rchild());
                        rotate_left(parent,node);
                }
            }
            else if (bfp < -1)
            {
                int bfq = balance_factor(node->lchild());
                if (bfq < 1)
                        rotate_right(parent,node);
                else
                {
                        rotate_left(node,node->lchild());
                        rotate_right(parent,node);
                }
            }
            node = parent; 
        }
}
template <typename elemType>
void Tree<elemType>::rotate_right(Node<elemType> *parent, Node<elemType> *node)
{
        if (!node)
                return; 
        Node<elemType> *temp = 0;
        if( node->_lchild)
        {
                temp = node->_lchild->_rchild;
                node->_lchild->_rchild = node;
        }
        node = node->_lchild;
        if (node && node->_rchild)
        {
                node->_rchild->_lchild =  temp;
        }
        if (parent)
        {
                if (node && parent->_rchild == node->_rchild)
                        parent->_rchild = node;
                else if (node && parent->_lchild == node->_rchild)      
                        parent->_lchild = node;
                else;       
        }
        else
            _root = node;
}
template <typename elemType>
void Tree<elemType>::rotate_left(Node<elemType> *parent, Node<elemType> *node)
{
        if (!node)
                return; 
        Node<elemType> *temp = 0;
        if( node->_rchild)
        {
                temp = node->_rchild->_lchild;
                node->_rchild->_lchild = node;
        }
        node = node->_rchild;
        if (node && node->_lchild)
        {
                node->_lchild->_rchild =  temp;
        }
        if (parent)
        {
                if (node && parent->_lchild == node->_lchild)
                        parent->_lchild = node;
                else if (node && parent->_rchild == node->_lchild)      
                        parent->_rchild = node;
                else;       
        }
        else
            _root = node;
}

int main(int argc,char *argv[])
{
    typedef int elemType;
    set<elemType> elems;
    srand(time(NULL));
    Tree<elemType> tree;
    //tree generation
    ofstream out_file("tree.dat");
    for (int ix = 0; ix < 10000; ++ix)
    {
        elemType val = rand() % 100;
        if (elems.count(val))
            continue;   
        tree.insert( val ); 
        out_file << val << ' ';
        elems.insert(val);
    }
    //print tree to file
    tree.graph("tree_before.dot");
    system("dot -Tpng tree_before.dot > tree_before.png");
    //delete node with to_del key
    int to_del = 33;
    tree.remove(to_del);
    //print rebalanced tree without node to_del
    tree.graph("tree_after.dot");
    system("dot -Tpng tree_after.dot > tree_after.png");
}