如何使二叉树平衡

Question

这里有一个简单的c语言的二叉树，但是好像不平衡，如何让它平衡？

代码：

/**
 * binary_tree impl
 */

#include <stdio.h>
#include <stdlib.h>


typedef struct _tnode _tnode;
typedef struct _bin_tree _bin_tree;
struct _tnode {
    int data;
    _tnode *parent;
    _tnode *left;
    _tnode *right;
};

_tnode *new_node(int data) {
    _tnode *node = (_tnode*)malloc(sizeof(_tnode));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return node;
}

_tnode *add(_tnode *top, int new_data, int (*cmpf)(int, int)) {
    if(top == NULL) {
        top = new_node(new_data);
    } else if(cmpf(top->data, new_data)<=0) {
        if(top->left == NULL) 
            top->left = new_node(new_data);
        else
            add(top->left, new_data, cmpf);
    } else {
        if(top->right == NULL) 
            top->right = new_node(new_data);
        else
            add(top->right, new_data, cmpf);
    }
    return top;
}

int cmp_int(int n1, int n2) {
    return n1 - n2;
}

void print_tree(_tnode *top) {
    if(top->left) print_tree(top->left);
    printf("%d\n",top->data);
    if(top->right) print_tree(top->right);
}

int main(int argc, char * argv[]) {
    int i = 0;
    _tnode *top = NULL;
    int arr[] = {6,1,9,3,5,0,2,7};
    int count = sizeof(arr) / sizeof(arr[0]);
    for(i=0; i<count; i++) {
        top = add(top, arr[i], cmp_int);
        printf("add: %d\n", arr[i]);
    }

    print_tree(top);
    return 0;
}

Answer 1

基本思路如下

对于插入，首先将新节点插入叶子，就像插入 non-balanced 树一样。

然后沿着树向根移动，确保对于每个节点，左右之间的高度差 sub-trees 不超过一。

如果是，则您 "rotate" 节点使得差异为一或更小。例如，考虑以下树，它在您添加 32 之前 是平衡的 但现在不是：

32 节点的深度差为零，因为两个 sub-trees 的深度都为零。

64 节点的深度差为 1，因为左侧 sub-tree 的深度为 1，右侧 sub-tree 的深度为 0。

128 节点的深度差为 two，因为左侧 sub-tree 的深度为二和右边 sub-tree 的深度为零。因此需要通过该节点进行旋转。这可以通过将 128 向下推到右侧 sub-tree 并调出 64:

来完成

   64
  /  \
32    128

你又一次有了余额。

旋转的方向当然要看高度是偏左还是偏右

删除有点棘手，因为您不一定像插入时那样在叶节点上工作。它在那里变得有点复杂，因为它取决于节点是否没有 children（是叶子）、一个 child 或两个 children.

1/ 对于叶子节点，直接删除即可，然后在那个叶子的parent处开始re-balancing。

2/ 对于one-child节点，可以只复制child信息（数据和链接）来替换要删除的节点, 然后删除 child 并开始 re-balancing 现在 child 信息所在的位置。

3/ 对于two-child节点，思路是找到它的直接后继（首先向右child然后不断向左child直到有没有了 children）。您还可以找到它的直接前身（从左到右），效果也一样。

然后你把你要删除的节点中的数据和后继（或前导）中的数据交换，然后re-apply这个规则，直到你要删除的节点是叶节点。然后使用与上述 (1) 完全相同的规则删除该叶节点。

这个交换技巧是完全有效的，因为即使交换使两个相邻的项目暂时乱序，事实上您正在删除其中一个（2 在这种情况下）auto-magically 解决问题：

  2           3           3
 / \   -->   / \   -->   /
1   3       1   2       1
=====       =====       =====
1,2,3       1,3,2       1,3

如何使二叉树平衡

How to make a binary tree balance

c

algorithm

binary-tree

tree-balancing