插入 AVL 树

Question

我目前正在尝试用 c 构建一个 AVL 树，其中每个节点都包含一个名称和一个值。树应该按值排序。目前，输入：

6 Franklin
4 David
1 Anna 
2 Bob
3 Cora
5 Ella
7 Griffin

树最终看起来像

         David
     /           \
   Anna        Franklin
      \        /    \
      Bob    Ella  Griffin
        \ 
       Cora

什么时候应该看起来像

          David
      /          \
    Bob       Franklin
  /    \      /      \
Anna  Cora  Ella  Griffin

这似乎是它打破的阈值大小，输入由较少的节点组成。相关代码：

#define MAX(X, Y) ((X) < (Y) ? (Y) : (X))

int height(struct Tree_Node *n) {

    if (n->right && n->left) return MAX(n->right->height, n->left->height) + 1;
    if (n->left && !n->right) return n->left->height + 1;
    if (n->right && !n->left) return n->right->height + 1;

    return 0;
}

int balance(struct Tree_Node *n) {

    if (n->left && n->right) return n->left->height - n->right->height;
    if (n->left && !n->right) return n->left->height;
    if (!n->left && n->right) return n->right->height;
    return 0;
}

struct Tree_Node *rotate_left(struct Tree_Node *n){

    struct Tree_Node *p;
    struct Tree_Node *tp;
    p = n;
    tp = p->left;

    p->left = tp->right;
    tp->right = p;

    return tp; 
}


struct Tree_Node *rotate_right(struct Tree_Node *n){

    struct Tree_Node *p;
    struct Tree_Node *tp;
    p = n;
    tp = p->right;

    p->right = tp->left;
    tp->left = p;

    return tp; 
}

struct Tree_Node *rotate_right_left(struct Tree_Node *n) {

    struct Tree_Node *p;
    struct Tree_Node *tp;
    struct Tree_Node *tp2;
    p = n;
    tp = p->right;
    tp2 =p->right->left;

    p -> right = tp2->left;
    tp ->left = tp2->right;
    tp2 ->left = p;
    tp2->right = tp; 
     
    return tp2; 
}

struct Tree_Node *rotate_left_right(struct Tree_Node *n) {

    struct Tree_Node *p;
    struct Tree_Node *tp;
    struct Tree_Node *tp2;
    p = n;
    tp = p->left;
    tp2 =p->left->right;

    p -> left = tp2->right;
    tp ->right = tp2->left;
    tp2 ->right = p;
    tp2->left = tp; 
     
    return tp2; 
}

struct Tree_Node *insert_leaf(struct Tree_Node *root, struct Tree_Node *new) {

    if (!root) {
        root = new;
        root->left = NULL;
        root->right = NULL;
        root->height = 0;
        return root;
    }
    else {
        if (new->value < root->value) root->left = insert_leaf(root->left, new);
        else root->right = insert_leaf(root->right, new);
    }
    root->height = height(root);
    
    if (balance(root) > 1 && new->value < root->left->value) root = rotate_left(root);
    else if (balance(root) < -1 && new->value > root->right->value) root = rotate_right(root);
    else if (balance(root) < -1 && new->value < root->right->value) root = rotate_right_left(root);
    else if (balance(root) > 1 && new->value > root->left->value) root = rotate_left_right(root);

    return root;
}

Answer 1

存在以下问题：

一个叶子节点的高度是1，不是0。所以height函数中最后的return应该是：
```
return 1;
```
然后在 insert_leaf 函数中，从 if 块中删除这两行：
```
root->height = 0;
return root;
```
这样执行将继续调用 height 以将此值正确设置为 1。
旋转函数将改变作为返回节点后代的节点的高度，因此您必须更新它们的高度。在单个旋转函数中，因此添加这一行：
```
p->height = height(p);
```
并在双旋转函数中添加：
```
p->height = height(p);
tp->height = height(tp);
```
您使用 n->left->height - n->right->height 将右重树的平衡定义为负数，然后在 n->left 时将其设为正数是 NULL 而 n->right 不是。在那种情况下应该是 negative。所以像这样添加否定运算符：
```
if (!n->left && n->right) return -n->right->height;
```

通过这些更改，将为您的测试用例构建预期的树。

插入 AVL 树

Insertion into AVL tree

c

tree

binary-tree

avl-tree