我正在尝试优化我的AVL树。如果没有自平衡，一百万个节点的树创建是超级快的。但是一旦我添加了旋转，它就变得非常慢。我怀疑这是由计算高度或平衡引起的，但是我无法找到正确的修复方法。
我应该做些什么来提高再平衡的效率？
typedef struct node{
int value;
struct node *left, *right, *parent;
}NODE;
int insert(int val,NODE **root,NODE *par){
NODE *temp;
NODE *new;
if(*root == NULL){
new = (NODE *)malloc(sizeof(NODE));
new->value = val;
new->left = NULL;
new->right = NULL;
new->parent = par;
*root = new;
rotate(*root);
return 1;
}
temp = *root;
if(val == temp->value){
//printf("Node already exist\n"); //X
return 0;
}
if(val < temp->value){
insert(val,&temp->left,temp);
}
if(val > temp->value){
insert(val,&temp->right,temp);
}
}
void rotate(NODE* root){
NODE* p;
p = root;
while(p != NULL){
rotation(p);
p = p->parent;
}
}
void rotation(NODE *root){
NODE* temp;
int balance = get_balace(root);
if(balance > 1){
if(get_balace(root->left) >= 1){
right_rotate(root);
}else if(get_balace(root->left) <= -1){
left_rotate(root->left);
right_rotate(root);
}
}else if(balance < -1){
if(get_balace(root->right) <= -1){
left_rotate(root);
}else if(get_balace(root->right) >= 1){
right_rotate(root->right);
left_rotate(root);
}
}
}
int get_height(NODE *root){
int left_h, right_h;
if(root == NULL){
return 0;
}
left_h = get_height(root->left);
right_h = get_height(root->right);
return 1 + max(left_h,right_h);
}
int get_balace(NODE *root){
return get_height(root->left) - get_height(root->right);
}旋转函数仅仅是具有逻辑的基本旋转。
我试着改变balance和height函数，通过分别计算left_h和right_h而不是像return 1 + max(get_height(root->left),get_height(root->right));那样计算，我设法使height稍微快一些
还能做些什么来加快速度呢？
1条答案
按热度按时间qyyhg6bp1#
在AVL树中计算子树的高度（在插入节点之后）是没有效率的。更重要的是，不需要知道子树的高度来实现正确运行的AVL树。与每个节点一起存储平衡因子（bf）就足够了。每种类型的旋转都可以导出平衡因子的变化，以保持信息的一致性。
Wikipedia上关于AVL tree的文章详细介绍了旋转和保持平衡因子最新的算法，注意旋转函数有前提条件，只有在需要重新平衡树时调用它们时才能给予可靠的结果。
下面是一个实现：