平衡的AVL树（C ++） [英] balancing an AVL tree (C++)
问题描述
我在最困难的时候试图找出如何平衡的AVL树为我的课。我知道了这个插入：
I'm having the hardest time trying to figure out how to balance an AVL tree for my class. I've got it inserting with this:
Node* Tree::insert(int d)
{
cout << "base insert\t" << d << endl;
if (head == NULL)
return (head = new Node(d));
else
return insert(head, d);
}
Node* Tree::insert(Node*& current, int d)
{
cout << "insert\t" << d << endl;
if (current == NULL)
current = new Node(d);
else if (d < current->data) {
insert(current->lchild, d);
if (height(current->lchild) - height(current->rchild)) {
if (d < current->lchild->getData())
rotateLeftOnce(current);
else
rotateLeftTwice(current);
}
}
else if (d > current->getData()) {
insert(current->rchild, d);
if (height(current->rchild) - height(current->lchild)) {
if (d > current->rchild->getData())
rotateRightOnce(current);
else
rotateRightTwice(current);
}
}
return current;
}
我的计划是有来电平衡（）检查，看看树需要平衡，然后根据需要平衡。麻烦的是，我甚至无法弄清楚如何遍历树，找到正确的平衡点。我知道如何递归遍历树，但我似乎无法在算法转化为寻找最低的不平衡结点。我也遇到了麻烦写一个迭代算法。任何帮助将是AP preciated。 ：）
My plan was to have the calls to balance() check to see if the tree needs balancing and then balance as needed. The trouble is, I can't even figure out how to traverse the tree to find the correct unbalanced node. I know how to traverse the tree recursively, but I can't seem to translate that algorithm into finding the lowest unbalanced node. I'm also having trouble writing an iterative algorithm. Any help would be appreciated. :)
推荐答案
您可以测量一个分支的高度在给定的点来计算不平衡
You can measure the height of a branch at a given point to calculate the unbalance
（记得高度（水平）的差异> = 2表示你的树是不均衡的）的
int Tree::Height(TreeNode *node){
int left, right;
if(node==NULL)
return 0;
left = Height(node->left);
right = Height(node->right);
if(left > right)
return left+1;
else
return right+1;
}
根据不均匀，那么你就可以旋转作为必要
void Tree::rotateLeftOnce(TreeNode*& node){
TreeNode *otherNode;
otherNode = node->left;
node->left = otherNode->right;
otherNode->right = node;
node = otherNode;
}
void Tree::rotateLeftTwice(TreeNode*& node){
rotateRightOnce(node->left);
rotateLeftOnce(node);
}
void Tree::rotateRightOnce(TreeNode*& node){
TreeNode *otherNode;
otherNode = node->right;
node->right = otherNode->left;
otherNode->left = node;
node = otherNode;
}
void Tree::rotateRightTwice(TreeNode*& node){
rotateLeftOnce(node->right);
rotateRightOnce(node);
}
现在，我们知道如何旋转，可以说你想要插入在树中的值。首先我们要检查是否有树是空或不
Now that we know how to rotate, lets say you want to insert a value in the tree... First we check whether the tree is empty or not
TreeNode* Tree::insert(int d){
if(isEmpty()){
return (root = new TreeNode(d)); //Is empty when root = null
}
else
return insert(root, d); //step-into the tree and place "d"
}
在树不为空，我们使用递归遍历树，并获得哪些地方
When the tree is not empty we use recursion to traverse the tree and get to where is needed
TreeNode* Tree::insert(TreeNode*& node, int d_IN){
if(node == NULL) // (1) If we are at the end of the tree place the value
node = new TreeNode(d_IN);
else if(d_IN < node->d_stored){ //(2) otherwise go left if smaller
insert(node->left, d_IN);
if(Height(node->left) - Height(node->right) == 2){
if(d_IN < node->left->d_stored)
rotateLeftOnce(node);
else
rotateLeftTwice(node);
}
}
else if(d_IN > node->d_stored){ // (3) otherwise go right if bigger
insert(node->right, d_IN);
if(Height(node->right) - Height(node->left) == 2){
if(d_IN > node->right->d_stored)
rotateRightOnce(node);
else
rotateRightTwice(node);
}
}
return node;
}
您应经常检查平衡的（并做旋转如有必要）修改树，没有一点等待，直到当树是一个烂摊子，以平衡它结束的时候的。这只是复杂的事情......
You should always check for balance (and do rotations if necessary) when modifying the tree, no point waiting until the end when the tree is a mess to balance it. That just complicates things...
更新
有一个错误在您的实现，在code下面你不检查正确的树是否是不平衡的。你需要检查的高度是否等于2（因此失衡）。其结果是，code波纹管......
There is a mistake in your implementation, in the code below you are not checking correctly whether the tree is unbalanced. You need to check whether the height is equals to 2 (therefore unbalance). As a result the code bellow...
if (height(current->lchild) - height(current->rchild)) { ...
if (height(current->rchild) - height(current->lchild)) {...
应成为...
Should become...
if (height(current->lchild) - height(current->rchild) == 2) { ...
if (height(current->rchild) - height(current->lchild) == 2) {...
有些资源
- AVL Tree ~ Imprementation in C++
- AVL Tree ~ Applet
这篇关于平衡的AVL树（C ++）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
