L'équilibrage d'un Arbre de Recherche Binaire (BST)

Je suis en train de faire un balance_bst(bstNode racine) de la fonction, mais j'ai du mal avec la mise en œuvre.

Je suis la mise en œuvre de la fonction comme une fonction de modèle, depuis mon bstNode classe est une classe template.

Ici est (une partie de) mon 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); 
}

Je me suis amusé avec le réel balance_bst fonction, et pense que la récursivité est la solution la plus évidente, mais je n'arrive pas à envelopper ma tête autour de celui-ci...

trieur fondamentalement insère les éléments d'une BST dans un vecteur à l'aide d'un afinde algorithme de traitement. Donc tant que "root" est un pointeur sur la racine d'un arbre de recherche binaire(c'est à dire toutes les valeurs de clé de nœuds du sous-arbre gauche sont moins de la valeur de la clé de noeuds et de toutes les principales valeurs des nœuds du sous-arbre droit sont plus grands que les nœuds), puis les nœuds inséré dans le vecteur sera trieur dans un croissant.

Ensuite, pour créer l'équilibre de l'arbre, j'insère le nœud au centre du vecteur à la racine de l'arbre, et ensuite devrait être en mesure d'insérer de manière récursive gauche et à droite les noeuds enfants qui seraient ensuite au milieu de la moitié gauche du vecteur et de la milieu de la moitié droite du vecteur.

Remarque: je comprends que c'est à l'aide de division entière et que dire, 7/2 = 3, ce qui serait l'indice de la moyenne des éléments d'un tableau de taille 7. Et de même pour la taille des tableaux, l'algorithme mis en œuvre ci-dessus permettra de trouver l'indice de la plus grande des deux éléments dans le milieu du vecteur.

De toute façon, des suggestions ou des observations sont les bienvenus et encouragés! Merci à l'avance.

Edit: Ce que je demande est de savoir comment dois-je mettre en œuvre une fonction d'équilibre d'un arbre de recherche binaire?
(L'équilibre de la STB est celui qui a de la profondeur minimale il peut, compte tenu du nombre de nœuds.)

Quelle est la question?
Désolé,La question est: comment puis-je balance un arbre de recherche binaire?

OriginalL'auteur MRT89 | 2012-05-03