Вопрос по c++ – Балансировка дерева двоичного поиска (BST)

5

Я пытаюсь сделать функцию balance_bst (корень bstNode), но я борюсь с реализацией.

Я реализую функцию как функцию шаблона, так как мой класс bstNode является классом шаблона.

Вот (некоторые из) мой код:

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); 
}

Я возился с реальной функцией balance_bst и думаю, что рекурсия - очевидное решение, но я не могу обернуться вокруг этого ...

sorter в основном вставляет элементы BST в вектор, используя алгоритм обработки по порядку. Так что до тех пор, как «корень» является указателем на корень дерева двоичного поиска (т. е. все значения ключей левого поддерева узлов меньше значения ключей узлов, а все значения ключей правого поддерева узлов больше узлов), затем узлы, вставленные в вектор будет отсортирован по возрастанию.

Затем, чтобы создать сбалансированное дерево, я вставляю узел в центре вектора в корне дерева, а затем должен быть в состоянии рекурсивно вставить левый и правый дочерние узлы, которые затем были бы в середине левой половины вектора и середина правой половины вектора.

Примечание: я понимаю, что это использует целочисленное деление и, скажем, 7/2 = 3, который будет индексом среднего элемента массива размера 7. А для массивов четного размера алгоритм, реализованный выше, найдет индекс большего из двух элементов в середине вектора.

В любом случае, любые предложения или замечания приветствуются и поощряются! Заранее спасибо.

Изменить: то, что я спрашиваю, как я могу реализовать функцию, чтобы сбалансировать двоичное дерево поиска? (Сбалансированный BST - это тот, который имеет минимальную глубину, которую он может дать, учитывая количество узлов.)

В чем вопрос? Juraj Blaho
Извините, вопрос в том, как мне сбалансировать бинарное дерево поиска? MRT89

Ваш Ответ

1   ответ
7

Эта ссылка на Википедию имеет хорошее объяснение по решению проблемы балансировки.

Я нашел самый простой способ сбалансировать дерево во время вставки. Вот рекурсивная вставка с вспомогательными функциями (для различных случаев поворота) и классом 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;
        }

Вспомогательные функции

        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
{
  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;
};

Надеюсь это поможет!

Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded

Похожие вопросы