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

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

平衡因子

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

旋转

左旋(朝左旋转)

左旋

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

1
static Node* right_right_rotation(AVLTree k1)
2
{
3
    AVLTree k2;
4
5
    k2 = k1->right;
6
    k1->right = k2->left;
7
    k2->left = k1;
8
9
    k1->height = MAX( HEIGHT(k1->left), HEIGHT(k1->right)) + 1;
10
    k2->height = MAX( HEIGHT(k2->right), k1->height) + 1;
11
12
    return k2;
13
}

右旋(朝右旋转)

右旋

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

1
static Node* left_left_rotation(AVLTree k2)
2
{
3
    AVLTree k1;
4
5
    k1 = k2->left;
6
    k2->left = k1->right;
7
    k1->right = k2;
8
9
    k2->height = MAX( HEIGHT(k2->left), HEIGHT(k2->right)) + 1;
10
    k1->height = MAX( HEIGHT(k1->left), k2->height) + 1;
11
12
    return k1;
13
}

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

左右旋

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

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

右左旋

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

插入

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

删除

1
static Node* delete_node(AVLTree tree, Node *z)
2
{
3
  /* 根为空或者没有要删除的节点，直接返回NULL */
4
  if (tree==NULL || z==NULL)
5
    return NULL;
6
  
7
  if (z->key < tree->key)  /* 待删除的节点在tree的左子树中 */
8
  {
9
    tree->left = delete_node(tree->left, z);
10
    /* 删除节点后，若AVL树失去平衡，则进行相应的调节 */
11
    if (HEIGHT(tree->right) - HEIGHT(tree->left) == 2)
12
    {
13
      Node *r =  tree->right;
14
15
      if (HEIGHT(r->left) > HEIGHT(r->right))
16
        tree = right_left_rotation(tree);
17
      else
18
        tree = right_right_rotation(tree);
19
    }
20
  }
21
  else if (z->key > tree->key)/* 待删除的节点在tree的右子树中 */
22
  {
23
    tree->right = delete_node(tree->right, z);
24
    
25
		if (HEIGHT(tree->left) - HEIGHT(tree->right) == 2)
26
    {
27
      Node *l =  tree->left;
28
      if (HEIGHT(l->right) > HEIGHT(l->left))
29
        tree = left_right_rotation(tree);
30
      else
31
        tree = left_left_rotation(tree);
32
    }
33
  }
34
  else  /* tree是对应要删除的节点 */
35
  {
36
    /* tree的左右孩子都非空 */
37
    if ((tree->left) && (tree->right))
38
    {
39
      if (HEIGHT(tree->left) > HEIGHT(tree->right))
40
      {
41
        /* 如果tree的左子树比右子树高,则:
42
				 1. 找出tree的左子树中的最大节点(左子树的最大结点只小于该结点)
43
         2. 将该最大节点的值赋值给tree
44
         3. 删除该最大节点
45
         4. 这类似于用tree的左子树中最大节点做tree的替身 */
46
        Node *max = avltree_maximum(tree->left);
47
        tree->key = max->key;
48
        tree->left = delete_node(tree->left, max);
49
      }
50
      else
51
      {
52
        /* 如果tree的左子树不比右子树高(即它们相等，或右子树比左子树高1),则:
53
         1. 找出tree的右子树中的最小节点
54
         2. 将该最小节点的值赋值给tree
55
         3. 删除该最小节点 */
56
        Node *min = avltree_maximum(tree->right);
57
        tree->key = min->key;
58
        tree->right = delete_node(tree->right, min);
59
      }
60
    }
61
    else
62
    {
63
      Node *tmp = tree;
64
      tree = tree->left ? tree->left : tree->right;
65
      free(tmp);
66
    }
67
  }
68
69
  return tree;
70
}
71
72
Node* avltree_delete(AVLTree tree, Type key)
73
{
74
  Node *z;
75
76
  if ((z = avltree_search(tree, key)) != NULL)
77
    tree = delete_node(tree, z);
78
  
79
	return tree;
80
}