平衡二叉搜索树（BST） [英] Balancing a Binary Search Tree (BST)
问题描述
我试图创建一个balance_bst（bstNode根）函数，但是我努力的实现。
I'm trying to make a balance_bst(bstNode root) function, but i'm struggling with the implementation.
我实现的功能作为一个模板函数，因为我的bstNode类是一个模板类。
I'm implementing the function as a template function, since my bstNode class is a template class.
这里是（我的一些代码）：
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);
}
我一直在搞乱实际的balance_bst函数，明显的解决方案，但我似乎无法包装我的头围绕这一...
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...
分拣机基本上是使用无序处理算法将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.
然后，为了创建平衡树，我将节点插入向量的中心在树的根处，然后应该能够递归地插入左和右子节点，然后它们将在矢量的左半部分的中间和矢量的右半部分的中间。
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.
注意：我知道这是使用整数除法，即7/2 = 3，这将是大小为7的数组的中间元素的索引。甚至上面实现的算法将找到向量中间两个元素中较大者的索引。
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.
无论如何，欢迎任何建议或观察，鼓励！提前致谢。
Anyway, any suggestions or observations are welcomed and encouraged! Thanks in advance.
编辑：我要求的是如何实现一个函数来平衡二叉搜索树？
（平衡的BST是具有可以给出节点数量的最小深度的BST。）
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.)
推荐答案
平衡二叉搜索树也被称为AVL树
。
A balanced binary search tree is also known as an AVL tree .
这个维基百科链接
有很好的解释平衡问题的解释。
This wikipedia link has a good explanation on solving the balancing problem.
我发现最简单的方法来平衡树是插入。这里是一个具有辅助函数（对于各种旋转情况）和一个AVLNode类的递归插入。
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.
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;
};
希望这有助于！
这篇关于平衡二叉搜索树（BST）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
