平衡二叉树(balance binary tree)是二叉排序树的进化体，由G.M.Adelson-Velsky和E.M. Landis提出的，所以又叫AVL树。

平衡二叉树是指它除了具备二叉排序树的基本特征之外，还具有一个重要的特定：它的左子树与右子树的深度之差(平衡因子)的绝对值不超过1，且都是平衡二叉树。

平衡因子

平衡因子(Balance Factor,BF):二叉树结点的左子树深度减去右子树深度的值。平衡二叉树的平衡因子的绝对值不超过1。平
衡因子绝对值大于1的结点为根节点的子树就是最小不平衡子树。调整节点之间的链接关的基本方法就是旋转。

旋转

左旋(朝左旋转)

左旋

左旋规则：在产生的最小不平衡子树根结点右孩子的右孩子处插入结点，即最小不平衡子树的根结点及其右孩子的平衡因子都为负，则以根结点的右孩子为支点进行左旋转，根结点变为支点的左孩子。

1
2
3
4
5
6
7
8
9
10
11
12
13
static Node* right_right_rotation(AVLTree k1)
{
    AVLTree k2;

    k2 = k1->right;
    k1->right = k2->left;
    k2->left = k1;

    k1->height = MAX( HEIGHT(k1->left), HEIGHT(k1->right)) + 1;
    k2->height = MAX( HEIGHT(k2->right), k1->height) + 1;

    return k2;
}

右旋(朝右旋转)

右旋

右旋规则：在产生的最小不平衡子树的根结点及其左孩子平衡因子都为正，即在最小不平衡子树根结点的左孩子的左孩子出插入结点，则以根结点的左孩子为支点进行右旋。

1
2
3
4
5
6
7
8
9
10
11
12
13
static Node* left_left_rotation(AVLTree k2)
{
    AVLTree k1;

    k1 = k2->left;
    k2->left = k1->right;
    k1->right = k2;

    k2->height = MAX( HEIGHT(k2->left), HEIGHT(k2->right)) + 1;
    k1->height = MAX( HEIGHT(k1->left), k2->height) + 1;

    return k1;
}

左右旋(先向左旋在向右旋)

左右旋

1
2
3
4
5
6
static Node* left_right_rotation(AVLTree k3)
{
    k3->left = right_right_rotation(k3->left);

    return left_left_rotation(k3);
}

右左旋(先向右旋在向左旋)

右左旋

1
2
3
4
5
6
static Node* right_left_rotation(AVLTree k1)
{
    k1->right = left_left_rotation(k1->right);

    return right_right_rotation(k1);
}

插入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
Node* avltree_insert(AVLTree tree, Type key)
{
  if (tree == NULL) 
  {
    tree = avltree_create_node(key, NULL, NULL);
    if (tree==NULL)
    {
      printf("ERROR: create avltree node failed!\n");
      return NULL;
    }
  }
  else if (key < tree->key) /* 将key插入到tree的左子树 */
  {
    tree->left = avltree_insert(tree->left, key);
    /* 插入节点后，若AVL树失去平衡，则进行相应的调节 */
    if (HEIGHT(tree->left) - HEIGHT(tree->right) == 2)
    {
      if (key < tree->left->key)
        tree = left_left_rotation(tree);
      else
        tree = left_right_rotation(tree);
    }
  }
  else if (key > tree->key) /* 将key插入到tree的右子树 */
  {
    tree->right = avltree_insert(tree->right, key);
    
		if (HEIGHT(tree->right) - HEIGHT(tree->left) == 2)
    {
      if (key > tree->right->key)
        tree = right_right_rotation(tree);
      else
        tree = right_left_rotation(tree);
    }
  }
  else /* key == tree->key */
  {
    printf("添加失败：不允许添加相同的节点！\n");
  }

  tree->height = MAX( HEIGHT(tree->left), HEIGHT(tree->right)) + 1;
 
  return tree;
}

删除

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
static Node* delete_node(AVLTree tree, Node *z)
{
  /* 根为空或者没有要删除的节点，直接返回NULL */
  if (tree==NULL || z==NULL)
    return NULL;
  
  if (z->key < tree->key)  /* 待删除的节点在tree的左子树中 */
  {
    tree->left = delete_node(tree->left, z);
    /* 删除节点后，若AVL树失去平衡，则进行相应的调节 */
    if (HEIGHT(tree->right) - HEIGHT(tree->left) == 2)
    {
      Node *r =  tree->right;

      if (HEIGHT(r->left) > HEIGHT(r->right))
        tree = right_left_rotation(tree);
      else
        tree = right_right_rotation(tree);
    }
  }
  else if (z->key > tree->key)/* 待删除的节点在tree的右子树中 */
  {
    tree->right = delete_node(tree->right, z);
    
		if (HEIGHT(tree->left) - HEIGHT(tree->right) == 2)
    {
      Node *l =  tree->left;
      if (HEIGHT(l->right) > HEIGHT(l->left))
        tree = left_right_rotation(tree);
      else
        tree = left_left_rotation(tree);
    }
  }
  else  /* tree是对应要删除的节点 */
  {
    /* tree的左右孩子都非空 */
    if ((tree->left) && (tree->right))
    {
      if (HEIGHT(tree->left) > HEIGHT(tree->right))
      {
        /* 如果tree的左子树比右子树高,则:
				 1. 找出tree的左子树中的最大节点(左子树的最大结点只小于该结点)
         2. 将该最大节点的值赋值给tree
         3. 删除该最大节点
         4. 这类似于用tree的左子树中最大节点做tree的替身 */
        Node *max = avltree_maximum(tree->left);
        tree->key = max->key;
        tree->left = delete_node(tree->left, max);
      }
      else
      {
        /* 如果tree的左子树不比右子树高(即它们相等，或右子树比左子树高1),则:
         1. 找出tree的右子树中的最小节点
         2. 将该最小节点的值赋值给tree
         3. 删除该最小节点 */
        Node *min = avltree_maximum(tree->right);
        tree->key = min->key;
        tree->right = delete_node(tree->right, min);
      }
    }
    else
    {
      Node *tmp = tree;
      tree = tree->left ? tree->left : tree->right;
      free(tmp);
    }
  }

  return tree;
}

Node* avltree_delete(AVLTree tree, Type key)
{
  Node *z;

  if ((z = avltree_search(tree, key)) != NULL)
    tree = delete_node(tree, z);
  
	return tree;
}