C++ 平衡二叉搜索树 (BST)

Balancing a Binary Search Tree (BST)

提问by MRT89

I'm trying to make a balance_bst(bstNode root) function, but i'm struggling with the implementation.

我正在尝试创建一个 balance_bst(bstNode root) 函数，但我正在努力实现。

I'm implementing the function as a template function, since my bstNode class is a template class.

我将该函数实现为模板函数，因为我的 bstNode 类是模板类。

Here is (some of) my code:

这是（一些）我的代码：

template<class Item, class  Key>
class bstNode{
public:
    //Constructor
    bstNode(const Item& init_data = Item(), const Key& init_key = Key(), bstNode<Item, Key>* l_child = NULL, bstNode<Item, Key>* r_child = NULL){
        data_field = init_data;
        key_field = init_key;
        l_ptr = l_child;
        r_ptr = r_child;
    }
    //Destructor
    ~bstNode(){
        data_field = 0;
        key_field = 0;
        l_ptr = r_ptr = NULL;
    }
    //Basic Member Functions
    bstNode<Item, Key>*& left( )   {                    return l_ptr;       }           //returns left child pointer by reference
    bstNode<Item, Key>*& right( )  {                    return r_ptr;       }           //returns right child pointer by reference
    bstNode<Item, Key>* left( ) const   {               return l_ptr;       }       //returns left child pointer by reference
    bstNode<Item, Key>* right( ) const  {               return r_ptr;       }       //returns right child pointer by reference
    const Item& data() const{                           return data_field;  }           //returns reference to data_field
    const Key& key()const {                             return key_field;   }
    Item& data() {                                      return data_field;  }           //returns reference to data_field
    Key& key() {                                        return key_field;   }
    void set_data(const Item& new_data){            data_field = new_data;      }       //sets data_field to new_data
    void set_key(const Key& new_key){               key_field = new_key;        }       //sets key_field to new_key
    void set_left(bstNode* new_left){               l_ptr = new_left;           }       //sets left child pointer to new_left
    void set_right(bstNode* new_right){             r_ptr = new_right;          }       //sets right child pointer to new_right

private:
    bstNode<Item, Key>  *l_ptr,     //pointer to left child node 
                        *r_ptr;     //pointer to right child node
    Item    data_field;
    Key     key_field;
};

template<class Item, class Key>
void balance_bst(bstNode<Item, Key>*& root){                //unfinished

    std::vector< bstNode<Item, Key>* > nodes;
    sorter(root, nodes);
    size_t i = nodes.size()/2;                      //size() divided by 2 will yield
                                                    //index of middle element of vector for 
                                                    //odd-isized arrays and the greater of the 
                                                    //middle two elements for an even-sized array

    while(i>=0){
        root->set_key(nodes[i]->key());                             
        root->set_data(nodes[i]->data());
         //.....MORE CODE HERE: recursive call??

    }


}

template<class Item, class Key>
void sorter(bstNode<Item, Key>*& root, std::vector<bstNode<Item, Key>* >& tree_nodes){
    if(root == NULL)
        return;
    sorter(root->left(), tree_nodes);
    tree_nodes.push_back(root);
    sorter(root->right(), tree_nodes); 
}

I've been messing with the actual balance_bst function, and think that recursion is the obvious solution but i can't seem to wrap my head around this one...

我一直在搞乱实际的 balance_bst 函数，并认为递归是显而易见的解决方案，但我似乎无法理解这个......

sorter basically inserts the elements of a BST into a vector using an inorder processing algorithm. So as long as "root" is a pointer to the root of a binary search tree(ie all key values of a nodes left subtree are less than the key value of the nodes and all key values of the nodes right subtree are greater than the nodes) then the nodes inserted into the vector will be sorter in an ascending manner.

排序器基本上使用中序处理算法将 BST 的元素插入向量中。所以只要“root”是指向二叉搜索树根的指针（即一个节点左子树的所有键值都小于节点的键值并且节点右子树的所有键值都大于节点）然后插入到向量中的节点将以升序方式排序。

Then, to create a balanced tree, i insert the node at the center of the vector at the root of the tree, and then should be able to recursively insert the left and right children nodes which would then be at the middle of the left half of the vector and the middle of the right half of the vector.

然后，为了创建一个平衡树，我在树的根部向量的中心插入节点，然后应该能够递归地插入左右子节点，然后它们将位于左半部分的中间的向量和向量的右半部分的中间。

Note: i understand that this is using integer division and that say, 7/2 = 3, which would be the index of the middle element of an array of size 7. And for even-sized arrays, the algorithm implemented above will find the index of the greater of the two elements in the middle of the vector.

注意：我知道这是使用整数除法，也就是说，7/2 = 3，这将是大小为 7 的数组的中间元素的索引。对于偶数大小的数组，上面实现的算法将找到向量中间两个元素中较大元素的索引。

Anyway, any suggestions or observations are welcomed and encouraged! Thanks in advance.

无论如何，欢迎和鼓励任何建议或意见！提前致谢。

Edit: What I am asking is how do I implement a function to balance a binary search tree? (A balanced BST is one that has the minimum depth it can given the number of nodes.)

编辑：我要问的是如何实现一个函数来平衡二叉搜索树？（平衡的 BST 是在给定节点数量的情况下具有最小深度的 BST。）

回答by Jared Sealey

A balanced binary search tree is also known as an AVL tree .

平衡二叉搜索树也称为 AVL 树。

This wikipedia linkhas a good explanation on solving the balancing problem.

这个维基百科链接对解决平衡问题有很好的解释。

I found the easiest way to balance the tree is during insertion. Here is a recursive insert with helper functions (for the various rotate cases) and an AVLNode class.

我发现平衡树的最简单方法是在插入期间。这是一个带有辅助函数（用于各种旋转情况）和一个 AVLNode 类的递归插入。

        bool avl_insert(AVLNode*& subRoot, const int &newData, bool &taller)
        {
            bool result = true;
            if(!subRoot){
                subRoot = new AVLNode(newData);
                taller = true;
            }
            else if(newData == subRoot->getData()){
                result = false;
                taller = false;
            }
            else if(newData < subRoot->getData()){
                result = avl_insert(subRoot->getLeft(), newData, taller);
                if(taller)
                    switch(subRoot->getBalance()){
                    case -1:
                        left_balance(subRoot);
                        taller = false;
                        break;
                    case 0:
                        subRoot->setBalance(-1);
                        break;
                    case 1:
                        subRoot->setBalance(0);
                        taller = false;
                        break;
                    }
            }
            else{
                result = avl_insert(subRoot->getRight(), newData, taller);
                if(taller)
                    switch(subRoot->getBalance()){
                    case -1:
                        subRoot->setBalance(0);
                        taller = false;
                        break;
                    case 0:
                        subRoot->setBalance(1);
                        break;
                    case 1:
                        right_balance(subRoot);
                        taller = false;
                        break;
                    }
            }
            return result;
        }

Helper Functions

辅助函数

        void right_balance(AVLNode *&subRoot)
        {
            AVLNode *&right_tree = subRoot->getRight();
            switch(right_tree->getBalance()){
            case 1:
                subRoot->setBalance(0);
                right_tree->setBalance(0);
                rotate_left(subRoot); break;
            case 0:
                cout<<"WARNING: program error in right_balance"<<endl; break;
            case -1:
                AVLNode *subTree = right_tree->getLeft();
                switch(subTree->getBalance()){
                    case 0:
                        subRoot->setBalance(0);
                        right_tree->setBalance(0);break;
                    case -1:
                        subRoot->setBalance(0);
                        right_tree->setBalance(1); break;
                    case 1:
                        subRoot->setBalance(-1);
                        right_tree->setBalance(0);break;
                }
                subTree->setBalance(0);
                rotate_right(right_tree);
                rotate_left(subRoot); break;
            }
        }
        void left_balance(AVLNode *&subRoot)
        {
            AVLNode *&left_tree = subRoot->getLeft();
            switch(left_tree->getBalance()){
            case -1:
                subRoot->setBalance(0);
                left_tree->setBalance(0);
                rotate_right(subRoot); break;
            case 0:
                cout<<"WARNING: program error in left_balance"<<endl; break;
            case 1:
                AVLNode *subTree = left_tree->getRight();
                switch(subTree->getBalance()){
                    case 0:
                        subRoot->setBalance(0);
                        left_tree->setBalance(0);break;
                    case -1:
                        subRoot->setBalance(0);
                        left_tree->setBalance(1); break;
                    case 1:
                        subRoot->setBalance(-1);
                        left_tree->setBalance(0);break;
                }
                subTree->setBalance(0);
                rotate_left(left_tree);
                rotate_right(subRoot); break;
            }
        }

    void rotate_left(AVLNode *&subRoot)
    {
        if(subRoot == NULL || subRoot->getRight() == NULL)
            cout<<"WARNING: program error detected in rotate_left"<<endl;
        else{
            AVLNode *right_tree = subRoot->getRight();
            subRoot->setRight(right_tree->getLeft());
            right_tree->setLeft(subRoot);
            subRoot = right_tree;
        }
    }
    void rotate_right(AVLNode *&subRoot)
    {
        if(subRoot == NULL || subRoot->getLeft() == NULL)
            cout<<"WARNING: program error detected in rotate_left"<<endl;
        else{
            AVLNode *left_tree = subRoot->getLeft();
            subRoot->setLeft(left_tree->getRight());
            left_tree->setRight(subRoot);
            subRoot = left_tree;
        }
    }

AVLNode class

AVLNode 类

class AVLNode
{
  public:
        AVLNode()
        {
            previous = NULL;
            next = NULL;
        }
        AVLNode(int newData){
            data = newData;
            previous = NULL;
            balance=0;
            next = NULL;
        }
        ~AVLNode(){}
        void setBalance(int b){balance = b;}
        int getBalance(){return balance;}
        void setRight(AVLNode* newNext){next = newNext;}
        void setLeft(AVLNode* newPrevious){previous = newPrevious;}
        AVLNode* getRight() const{return next;}
        AVLNode* getLeft() const{return previous;}
        AVLNode*& getRight(){return next;}
        AVLNode*& getLeft(){return previous;}
        int getData() const{return data;}
        int& getData(){return data;}
        void setData(int newData){data = newData;}
        void setHeight(int newHeight){ height = newHeight;}
        int getHeight(){return height;}
  private:
        AVLNode* next;
        AVLNode* previous;
        int balance;
        int height;
        int data;
};

Hope this helps!

希望这可以帮助！