AVL树(一)之 图文解析 和 C语言的实现

 

概要

本章介绍AVL树。和前面介绍"二叉查找树"的流程一样,本章先对AVL树的理论知识进行简单介绍,然后给出C语言的实现。本篇实现的二叉查找树是C语言版的,后面章节再分别给出C++和Java版本的实现。
建议:若您对"二叉查找树"不熟悉,建议先学完"二叉查找树"再来学习AVL树。

目录

1. AVL树的介绍
2. AVL树的C实现
3. AVL树的C实现(完整源码)

4. AVL树的C测试程序

转载请注明出处:http://www.cnblogs.com/skywang12345/p/3576969.html


更多内容数据结构与算法系列 目录 

 

AVL树的介绍

AVL树是根据它的发明者G.M. Adelson-Velsky和E.M. Landis命名的。
它是最先发明的自平衡二叉查找树,也被称为高度平衡树。相比于"二叉查找树",它的特点是:AVL树中任何节点的两个子树的高度最大差别为1。 (关于树的高度等基本概念,请参考"二叉查找树(一)之 图文解析 和 C语言的实现 ")

AVL树(一)之 图文解析 和 C语言的实现

上面的两张图片,左边的是AVL树,它的任何节点的两个子树的高度差别都<=1;而右边的不是AVL树,因为7的两颗子树的高度相差为2(以2为根节点的树的高度是3,而以8为根节点的树的高度是1)。

AVL树的查找、插入和删除在平均和最坏情况下都是O(logn)。
如果在AVL树中插入或删除节点后,使得高度之差大于1。此时,AVL树的平衡状态就被破坏,它就不再是一棵二叉树;为了让它重新维持在一个平衡状态,就需要对其进行旋转处理。学AVL树,重点的地方也就是它的旋转算法;在后文的介绍中,再来对它进行详细介绍。

 

AVL树的C实现

1. 节点

1.1 定义

AVL树(一)之 图文解析 和 C语言的实现
typedef int Type;

typedef struct AVLTreeNode{
    Type key;                    // 关键字(键值)
    int height;
    struct AVLTreeNode *left;    // 左孩子
    struct AVLTreeNode *right;    // 右孩子
}Node, *AVLTree;
AVL树(一)之 图文解析 和 C语言的实现

AVL树的节点包括的几个组成对象:
(01) key -- 是关键字,是用来对AVL树的节点进行排序的。
(02) left -- 是左孩子。
(03) right -- 是右孩子。
(04) height -- 是高度。

 

1.2 节点的创建

AVL树(一)之 图文解析 和 C语言的实现
/*
 * 创建AVL树结点。
 *
 * 参数说明:
 *     key 是键值。
 *     left 是左孩子。
 *     right 是右孩子。
 */
static Node* avltree_create_node(Type key, Node *left, Node* right)
{
    Node* p;

    if ((p = (Node *)malloc(sizeof(Node))) == NULL)
        return NULL;
    p->key = key;
    p->height = 0;
    p->left = left;
    p->right = right;

    return p;
}
AVL树(一)之 图文解析 和 C语言的实现

 

1.3 树的高度

AVL树(一)之 图文解析 和 C语言的实现
#define HEIGHT(p)    ( (p==NULL) ? 0 : (((Node *)(p))->height) )

/*
 * 获取AVL树的高度
 */
int avltree_height(AVLTree tree)
{
    return HEIGHT(tree);
}
AVL树(一)之 图文解析 和 C语言的实现

关于高度,有的文章中将"空二叉树的高度定义为-1",而本文采用*上的定义:树的高度为最大层次。即空的二叉树的高度是0,非空树的高度等于它的最大层次(根的层次为1,根的子节点为第2层,依次类推)。

 

1.4 比较大小

#define MAX(a, b)    ( (a) > (b) ? (a) : (b) )

 

2. 旋转
前面说过,如果在AVL树中进行插入或删除节点后,可能导致AVL树失去平衡。这种失去平衡的可以概括为4种姿态:LL(左左),LR(左右),RR(右右)和RL(右左)。下面给出它们的示意图:

AVL树(一)之 图文解析 和 C语言的实现

上图中的4棵树都是"失去平衡的AVL树",从左往右的情况依次是:LL、LR、RL、RR。除了上面的情况之外,还有其它的失去平衡的AVL树,如下图:

AVL树(一)之 图文解析 和 C语言的实现
上面的两张图都是为了便于理解,而列举的关于"失去平衡的AVL树"的例子。总的来说,AVL树失去平衡时的情况一定是LL、LR、RL、RR这4种之一,它们都由各自的定义:

(1) LL:LeftLeft,也称为"左左"。插入或删除一个节点后,根节点的左子树的左子树还有非空子节点,导致"根的左子树的高度"比"根的右子树的高度"大2,导致AVL树失去了平衡。
     例如,在上面LL情况中,由于"根节点(8)的左子树(4)的左子树(2)还有非空子节点",而"根节点(8)的右子树(12)没有子节点";导致"根节点(8)的左子树(4)高度"比"根节点(8)的右子树(12)"高2。

(2) LR:LeftRight,也称为"左右"。插入或删除一个节点后,根节点的左子树的右子树还有非空子节点,导致"根的左子树的高度"比"根的右子树的高度"大2,导致AVL树失去了平衡。
     例如,在上面LR情况中,由于"根节点(8)的左子树(4)的左子树(6)还有非空子节点",而"根节点(8)的右子树(12)没有子节点";导致"根节点(8)的左子树(4)高度"比"根节点(8)的右子树(12)"高2。

(3) RL:RightLeft,称为"右左"。插入或删除一个节点后,根节点的右子树的左子树还有非空子节点,导致"根的右子树的高度"比"根的左子树的高度"大2,导致AVL树失去了平衡。
     例如,在上面RL情况中,由于"根节点(8)的右子树(12)的左子树(10)还有非空子节点",而"根节点(8)的左子树(4)没有子节点";导致"根节点(8)的右子树(12)高度"比"根节点(8)的左子树(4)"高2。

(4) RR:RightRight,称为"右右"。插入或删除一个节点后,根节点的右子树的右子树还有非空子节点,导致"根的右子树的高度"比"根的左子树的高度"大2,导致AVL树失去了平衡。
     例如,在上面RR情况中,由于"根节点(8)的右子树(12)的右子树(14)还有非空子节点",而"根节点(8)的左子树(4)没有子节点";导致"根节点(8)的右子树(12)高度"比"根节点(8)的左子树(4)"高2。

前面说过,如果在AVL树中进行插入或删除节点后,可能导致AVL树失去平衡。AVL失去平衡之后,可以通过旋转使其恢复平衡,下面分别介绍"LL(左左),LR(左右),RR(右右)和RL(右左)"这4种情况对应的旋转方法。

 

2.1 LL的旋转

LL失去平衡的情况,可以通过一次旋转让AVL树恢复平衡。如下图:

AVL树(一)之 图文解析 和 C语言的实现

图中左边是旋转之前的树,右边是旋转之后的树。从中可以发现,旋转之后的树又变成了AVL树,而且该旋转只需要一次即可完成。
对于LL旋转,你可以这样理解为:LL旋转是围绕"失去平衡的AVL根节点"进行的,也就是节点k2;而且由于是LL情况,即左左情况,就用手抓着"左孩子,即k1"使劲摇。将k1变成根节点,k2变成k1的右子树,"k1的右子树"变成"k2的左子树"。

LL的旋转代码

AVL树(一)之 图文解析 和 C语言的实现
/*
 * LL:左左对应的情况(左单旋转)。
 *
 * 返回值:旋转后的根节点
 */
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;
}
AVL树(一)之 图文解析 和 C语言的实现

 

2.2 RR的旋转

理解了LL之后,RR就相当容易理解了。RR是与LL对称的情况!RR恢复平衡的旋转方法如下:

AVL树(一)之 图文解析 和 C语言的实现

图中左边是旋转之前的树,右边是旋转之后的树。RR旋转也只需要一次即可完成。

 

RR的旋转代码

AVL树(一)之 图文解析 和 C语言的实现
/*
 * RR:右右对应的情况(右单旋转)。
 *
 * 返回值:旋转后的根节点
 */
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;
}
AVL树(一)之 图文解析 和 C语言的实现

 

2.3 LR的旋转

LR失去平衡的情况,需要经过两次旋转才能让AVL树恢复平衡。如下图:

AVL树(一)之 图文解析 和 C语言的实现
第一次旋转是围绕"k1"进行的"RR旋转",第二次是围绕"k3"进行的"LL旋转"。

 

LR的旋转代码

AVL树(一)之 图文解析 和 C语言的实现
/*
 * LR:左右对应的情况(左双旋转)。
 *
 * 返回值:旋转后的根节点
 */
static Node* left_right_rotation(AVLTree k3)
{
    k3->left = right_right_rotation(k3->left);

    return left_left_rotation(k3);
}
AVL树(一)之 图文解析 和 C语言的实现

 

2.4 RL的旋转
RL是与LR的对称情况!RL恢复平衡的旋转方法如下:

AVL树(一)之 图文解析 和 C语言的实现

第一次旋转是围绕"k3"进行的"LL旋转",第二次是围绕"k1"进行的"RR旋转"。


RL的旋转代码

AVL树(一)之 图文解析 和 C语言的实现
/*
 * RL:右左对应的情况(右双旋转)。
 *
 * 返回值:旋转后的根节点
 */
static Node* right_left_rotation(AVLTree k1)
{
    k1->right = left_left_rotation(k1->right);

    return right_right_rotation(k1);
}
AVL树(一)之 图文解析 和 C语言的实现


3. 插入
插入节点的代码

AVL树(一)之 图文解析 和 C语言的实现
/* 
 * 将结点插入到AVL树中,并返回根节点
 *
 * 参数说明:
 *     tree AVL树的根结点
 *     key 插入的结点的键值
 * 返回值:
 *     根节点
 */
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);
        // 插入节点后,若AVL树失去平衡,则进行相应的调节。
        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;
}
AVL树(一)之 图文解析 和 C语言的实现

 

4. 删除
删除节点的代码

AVL树(一)之 图文解析 和 C语言的实现
/* 
 * 删除结点(z),返回根节点
 *
 * 参数说明:
 *     ptree AVL树的根结点
 *     z 待删除的结点
 * 返回值:
 *     根节点
 */
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);
        // 删除节点后,若AVL树失去平衡,则进行相应的调节。
        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的左子树比右子树高;
                // 则(01)找出tree的左子树中的最大节点
                //   (02)将该最大节点的值赋值给tree。
                //   (03)删除该最大节点。
                // 这类似于用"tree的左子树中最大节点"做"tree"的替身;
                // 采用这种方式的好处是:删除"tree的左子树中最大节点"之后,AVL树仍然是平衡的。
                Node *max = avltree_maximum(tree->left);
                tree->key = max->key;
                tree->left = delete_node(tree->left, max);
            }
            else
            {
                // 如果tree的左子树不比右子树高(即它们相等,或右子树比左子树高1)
                // 则(01)找出tree的右子树中的最小节点
                //   (02)将该最小节点的值赋值给tree。
                //   (03)删除该最小节点。
                // 这类似于用"tree的右子树中最小节点"做"tree"的替身;
                // 采用这种方式的好处是:删除"tree的右子树中最小节点"之后,AVL树仍然是平衡的。
                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;
}

/* 
 * 删除结点(key是节点值),返回根节点
 *
 * 参数说明:
 *     tree AVL树的根结点
 *     key 待删除的结点的键值
 * 返回值:
 *     根节点
 */
Node* avltree_delete(AVLTree tree, Type key)
{
    Node *z; 

    if ((z = avltree_search(tree, key)) != NULL)
        tree = delete_node(tree, z);
    return tree;
}
AVL树(一)之 图文解析 和 C语言的实现

 

注意关于AVL树的"前序遍历"、"中序遍历"、"后序遍历"、"最大值"、"最小值"、"查找"、"打印"、"销毁"等接口与"二叉查找树"基本一样,这些操作在"二叉查找树"中已经介绍过了,这里就不再单独介绍了。当然,后文给出的AVL树的完整源码中,有给出这些API的实现代码。这些接口很简单,Please RTFSC(Read The Fucking Source Code)!

 

AVL树的C实现(完整源码)

AVL树的头文件(avltree.h)

AVL树(一)之 图文解析 和 C语言的实现
 1 #ifndef _AVL_TREE_H_
 2 #define _AVL_TREE_H_
 3 
 4 typedef int Type;
 5 
 6 typedef struct AVLTreeNode{
 7     Type key;                    // 关键字(键值)
 8     int height;
 9     struct AVLTreeNode *left;    // 左孩子
10     struct AVLTreeNode *right;    // 右孩子
11 }Node, *AVLTree;
12 
13 // 获取AVL树的高度
14 int avltree_height(AVLTree tree);
15 
16 // 前序遍历"AVL树"
17 void preorder_avltree(AVLTree tree);
18 // 中序遍历"AVL树"
19 void inorder_avltree(AVLTree tree);
20 // 后序遍历"AVL树"
21 void postorder_avltree(AVLTree tree);
22 
23 void print_avltree(AVLTree tree, Type key, int direction);
24 
25 // (递归实现)查找"AVL树x"中键值为key的节点
26 Node* avltree_search(AVLTree x, Type key);
27 // (非递归实现)查找"AVL树x"中键值为key的节点
28 Node* iterative_avltree_search(AVLTree x, Type key);
29 
30 // 查找最小结点:返回tree为根结点的AVL树的最小结点。
31 Node* avltree_minimum(AVLTree tree);
32 // 查找最大结点:返回tree为根结点的AVL树的最大结点。
33 Node* avltree_maximum(AVLTree tree);
34 
35 // 将结点插入到AVL树中,返回根节点
36 Node* avltree_insert(AVLTree tree, Type key);
37 
38 // 删除结点(key是节点值),返回根节点
39 Node* avltree_delete(AVLTree tree, Type key);
40 
41 // 销毁AVL树
42 void destroy_avltree(AVLTree tree);
43 
44 
45 #endif
View Code

AVL树的实现文件(avltree.c)

AVL树(一)之 图文解析 和 C语言的实现
  1 /**
  2  * AVL树(C语言): C语言实现的AVL树。
  3  *
  4  * @author skywang
  5  * @date 2013/11/07
  6  */
  7 
  8 #include <stdio.h>
  9 #include <stdlib.h>
 10 #include "avltree.h"
 11 
 12 #define HEIGHT(p)    ( (p==NULL) ? -1 : (((Node *)(p))->height) )
 13 #define MAX(a, b)    ( (a) > (b) ? (a) : (b) )
 14 
 15 /*
 16  * 获取AVL树的高度
 17  */
 18 int avltree_height(AVLTree tree)
 19 {
 20     return HEIGHT(tree);
 21 }
 22 
 23 /*
 24  * 前序遍历"AVL树"
 25  */
 26 void preorder_avltree(AVLTree tree)
 27 {
 28     if(tree != NULL)
 29     {
 30         printf("%d ", tree->key);
 31         preorder_avltree(tree->left);
 32         preorder_avltree(tree->right);
 33     }
 34 }
 35 
 36 
 37 /*

 38  * 中序遍历"AVL树"
 39  */
 40 void inorder_avltree(AVLTree tree)
 41 {
 42     if(tree != NULL)
 43     {
 44         inorder_avltree(tree->left);
 45         printf("%d ", tree->key);
 46         inorder_avltree(tree->right);
 47     }
 48 }
 49 
 50 /*
 51  * 后序遍历"AVL树"
 52  */
 53 void postorder_avltree(AVLTree tree)
 54 {
 55     if(tree != NULL)
 56     {
 57         postorder_avltree(tree->left);
 58         postorder_avltree(tree->right);
 59         printf("%d ", tree->key);
 60     }
 61 }
 62 
 63 /*
 64  * (递归实现)查找"AVL树x"中键值为key的节点
 65  */
 66 Node* avltree_search(AVLTree x, Type key)
 67 {
 68     if (x==NULL || x->key==key)
 69         return x;
 70 
 71     if (key < x->key)
 72         return avltree_search(x->left, key);
 73     else
 74         return avltree_search(x->right, key);
 75 }
 76 
 77 /*
 78  * (非递归实现)查找"AVL树x"中键值为key的节点
 79  */
 80 Node* iterative_avltree_search(AVLTree x, Type key)
 81 {
 82     while ((x!=NULL) && (x->key!=key))
 83     {
 84         if (key < x->key)
 85             x = x->left;
 86         else
 87             x = x->right;
 88     }
 89 
 90     return x;
 91 }
 92 
 93 /* 
 94  * 查找最小结点:返回tree为根结点的AVL树的最小结点。
 95  */
 96 Node* avltree_minimum(AVLTree tree)
 97 {
 98     if (tree == NULL)
 99         return NULL;
100 
101     while(tree->left != NULL)
102         tree = tree->left;
103     return tree;
104 }
105  
106 /* 
107  * 查找最大结点:返回tree为根结点的AVL树的最大结点。
108  */
109 Node* avltree_maximum(AVLTree tree)
110 {
111     if (tree == NULL)
112         return NULL;
113 
114     while(tree->right != NULL)
115         tree = tree->right;
116     return tree;
117 }
118 
119 /*
120  * LL:左左对应的情况(左单旋转)。
121  *
122  * 返回值:旋转后的根节点
123  */
124 static Node* left_left_rotation(AVLTree k2)
125 {
126     AVLTree k1;
127 
128     k1 = k2->left;
129     k2->left = k1->right;
130     k1->right = k2;
131 
132     k2->height = MAX( HEIGHT(k2->left), HEIGHT(k2->right)) + 1;
133     k1->height = MAX( HEIGHT(k1->left), k2->height) + 1;
134 
135     return k1;
136 }
137 
138 /*
139  * RR:右右对应的情况(右单旋转)。
140  *
141  * 返回值:旋转后的根节点
142  */
143 static Node* right_right_rotation(AVLTree k1)
144 {
145     AVLTree k2;
146 
147     k2 = k1->right;
148     k1->right = k2->left;
149     k2->left = k1;
150 
151     k1->height = MAX( HEIGHT(k1->left), HEIGHT(k1->right)) + 1;
152     k2->height = MAX( HEIGHT(k2->right), k1->height) + 1;
153 
154     return k2;
155 }
156 
157 /*
158  * LR:左右对应的情况(左双旋转)。
159  *
160  * 返回值:旋转后的根节点
161  */
162 static Node* left_right_rotation(AVLTree k3)
163 {
164     k3->left = right_right_rotation(k3->left);
165 
166     return left_left_rotation(k3);
167 }
168 
169 /*
170  * RL:右左对应的情况(右双旋转)。
171  *
172  * 返回值:旋转后的根节点
173  */
174 static Node* right_left_rotation(AVLTree k1)
175 {
176     k1->right = left_left_rotation(k1->right);
177 
178     return right_right_rotation(k1);
179 }
180 
181 /*
182  * 创建AVL树结点。
183  *
184  * 参数说明:
185  *     key 是键值。
186  *     left 是左孩子。
187  *     right 是右孩子。
188  */
189 static Node* avltree_create_node(Type key, Node *left, Node* right)
190 {
191     Node* p;
192 
193     if ((p = (Node *)malloc(sizeof(Node))) == NULL)
194         return NULL;
195     p->key = key;
196     p->height = 0;
197     p->left = left;
198     p->right = right;
199 
200     return p;
201 }
202 
203 /* 
204  * 将结点插入到AVL树中,并返回根节点
205  *
206  * 参数说明:
207  *     tree AVL树的根结点
208  *     key 插入的结点的键值
209  * 返回值:
210  *     根节点
211  */
212 Node* avltree_insert(AVLTree tree, Type key)
213 {
214     if (tree == NULL) 
215     {
216         // 新建节点
217         tree = avltree_create_node(key, NULL, NULL);
218         if (tree==NULL)
219         {
220             printf("ERROR: create avltree node failed!\n");
221             return NULL;
222         }
223     }
224     else if (key < tree->key) // 应该将key插入到"tree的左子树"的情况
225     {
226         tree->left = avltree_insert(tree->left, key);
227         // 插入节点后,若AVL树失去平衡,则进行相应的调节。
228         if (HEIGHT(tree->left) - HEIGHT(tree->right) == 2)
229         {
230             if (key < tree->left->key)
231                 tree = left_left_rotation(tree);
232             else
233                 tree = left_right_rotation(tree);
234         }
235     }
236     else if (key > tree->key) // 应该将key插入到"tree的右子树"的情况
237     {
238         tree->right = avltree_insert(tree->right, key);
239         // 插入节点后,若AVL树失去平衡,则进行相应的调节。
240         if (HEIGHT(tree->right) - HEIGHT(tree->left) == 2)
241         {
242             if (key > tree->right->key)
243                 tree = right_right_rotation(tree);
244             else
245                 tree = right_left_rotation(tree);
246         }
247     }
248     else //key == tree->key)
249     {
250         printf("添加失败:不允许添加相同的节点!\n");
251     }
252 
253     tree->height = MAX( HEIGHT(tree->left), HEIGHT(tree->right)) + 1;
254 
255     return tree;
256 }
257 
258 /* 
259  * 删除结点(z),返回根节点
260  *
261  * 参数说明:
262  *     ptree AVL树的根结点
263  *     z 待删除的结点
264  * 返回值:
265  *     根节点
266  */
267 static Node* delete_node(AVLTree tree, Node *z)
268 {
269     // 根为空 或者 没有要删除的节点,直接返回NULL。
270     if (tree==NULL || z==NULL)
271         return NULL;
272 
273     if (z->key < tree->key)        // 待删除的节点在"tree的左子树"中
274     {
275         tree->left = delete_node(tree->left, z);
276         // 删除节点后,若AVL树失去平衡,则进行相应的调节。
277         if (HEIGHT(tree->right) - HEIGHT(tree->left) == 2)
278         {
279             Node *r =  tree->right;
280             if (HEIGHT(r->left) > HEIGHT(r->right))
281                 tree = right_left_rotation(tree);
282             else
283                 tree = right_right_rotation(tree);
284         }
285     }
286     else if (z->key > tree->key)// 待删除的节点在"tree的右子树"中
287     {
288         tree->right = delete_node(tree->right, z);
289         // 删除节点后,若AVL树失去平衡,则进行相应的调节。
290         if (HEIGHT(tree->left) - HEIGHT(tree->right) == 2)
291         {
292             Node *l =  tree->left;
293             if (HEIGHT(l->right) > HEIGHT(l->left))
294                 tree = left_right_rotation(tree);
295             else
296                 tree = left_left_rotation(tree);
297         }
298     }
299     else    // tree是对应要删除的节点。
300     {
301         // tree的左右孩子都非空
302         if ((tree->left) && (tree->right))
303         {
304             if (HEIGHT(tree->left) > HEIGHT(tree->right))
305             {
306                 // 如果tree的左子树比右子树高;
307                 // 则(01)找出tree的左子树中的最大节点
308                 //   (02)将该最大节点的值赋值给tree。
309                 //   (03)删除该最大节点。
310                 // 这类似于用"tree的左子树中最大节点"做"tree"的替身;
311                 // 采用这种方式的好处是:删除"tree的左子树中最大节点"之后,AVL树仍然是平衡的。
312                 Node *max = avltree_maximum(tree->left);
313                 tree->key = max->key;
314                 tree->left = delete_node(tree->left, max);
315             }
316             else
317             {
318                 // 如果tree的左子树不比右子树高(即它们相等,或右子树比左子树高1)
319                 // 则(01)找出tree的右子树中的最小节点
320                 //   (02)将该最小节点的值赋值给tree。
321                 //   (03)删除该最小节点。
322                 // 这类似于用"tree的右子树中最小节点"做"tree"的替身;
323                 // 采用这种方式的好处是:删除"tree的右子树中最小节点"之后,AVL树仍然是平衡的。
324                 Node *min = avltree_maximum(tree->right);
325                 tree->key = min->key;
326                 tree->right = delete_node(tree->right, min);
327             }
328         }
329         else
330         {
331             Node *tmp = tree;
332             tree = tree->left ? tree->left : tree->right;
333             free(tmp);
334         }
335     }
336 
337     return tree;
338 }
339 
340 /* 
341  * 删除结点(key是节点值),返回根节点
342  *
343  * 参数说明:
344  *     tree AVL树的根结点
345  *     key 待删除的结点的键值
346  * 返回值:
347  *     根节点
348  */
349 Node* avltree_delete(AVLTree tree, Type key)
350 {
351     Node *z; 
352 
353     if ((z = avltree_search(tree, key)) != NULL)
354         tree = delete_node(tree, z);
355     return tree;
356 }
357 
358 /* 
359  * 销毁AVL树
360  */
361 void destroy_avltree(AVLTree tree)
362 {
363     if (tree==NULL)
364         return ;
365 
366     if (tree->left != NULL)
367         destroy_avltree(tree->left);
368     if (tree->right != NULL)
369         destroy_avltree(tree->right);
370 
371     free(tree);
372 }
373 
374 /*
375  * 打印"AVL树"
376  *
377  * tree       -- AVL树的节点
378  * key        -- 节点的键值 
379  * direction  --  0,表示该节点是根节点;
380  *               -1,表示该节点是它的父结点的左孩子;
381  *                1,表示该节点是它的父结点的右孩子。
382  */
383 void print_avltree(AVLTree tree, Type key, int direction)
384 {
385     if(tree != NULL)
386     {
387         if(direction==0)    // tree是根节点
388             printf("%2d is root\n", tree->key, key);
389         else                // tree是分支节点
390             printf("%2d is %2d‘s %6s child\n", tree->key, key, direction==1?"right" : "left");
391 
392         print_avltree(tree->left, tree->key, -1);
393         print_avltree(tree->right,tree->key,  1);
394     }
395 }
View Code

AVL树的测试程序(avltree_test.c) 

AVL树(一)之 图文解析 和 C语言的实现
 1 /**
 2  * C 语言: AVL树
 3  *
 4  * @author skywang
 5  * @date 2013/11/07
 6  */
 7 #include <stdio.h>
 8 #include "avltree.h"
 9 
10 static int arr[]= {3,2,1,4,5,6,7,16,15,14,13,12,11,10,8,9};
11 #define TBL_SIZE(a) ( (sizeof(a)) / (sizeof(a[0])) )
12 
13 void main()
14 {
15     int i,ilen;
16     AVLTree root=NULL;
17 
18     printf("== 高度: %d\n", avltree_height(root));
19     printf("== 依次添加: ");
20     ilen = TBL_SIZE(arr);
21     for(i=0; i<ilen; i++)
22     {
23         printf("%d ", arr[i]);
24         root = avltree_insert(root, arr[i]);
25     }
26 
27     printf("\n== 前序遍历: ");
28     preorder_avltree(root);
29 
30     printf("\n== 中序遍历: ");
31     inorder_avltree(root);
32 
33     printf("\n== 后序遍历: ");
34     postorder_avltree(root);
35     printf("\n");
36 
37     printf("== 高度: %d\n", avltree_height(root));
38     printf("== 最小值: %d\n", avltree_minimum(root)->key);
39     printf("== 最大值: %d\n", avltree_maximum(root)->key);
40     printf("== 树的详细信息: \n");
41     print_avltree(root, root->key, 0);
42 
43 
44     i = 8;
45     printf("\n== 删除根节点: %d", i);
46     root = avltree_delete(root, i);
47 
48     printf("\n== 高度: %d", avltree_height(root));
49     printf("\n== 中序遍历: ");
50     inorder_avltree(root);
51     printf("\n== 树的详细信息: \n");
52     print_avltree(root, root->key, 0);
53 
54     // 销毁二叉树
55     destroy_avltree(root);
56 }
View Code

 

AVL树的C测试程序

AVL树的测试程序运行结果如下:

AVL树(一)之 图文解析 和 C语言的实现
== 依次添加: 3 2 1 4 5 6 7 16 15 14 13 12 11 10 8 9 
== 前序遍历: 7 4 2 1 3 6 5 13 11 9 8 10 12 15 14 16 
== 中序遍历: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 
== 后序遍历: 1 3 2 5 6 4 8 10 9 12 11 14 16 15 13 7 
== 高度: 5
== 最小值: 1
== 最大值: 16
== 树的详细信息: 
 7 is root
 4 is  7s   left child
 2 is  4s   left child
 1 is  2s   left child
 3 is  2s  right child
 6 is  4s  right child
 5 is  6s   left child
13 is  7s  right child
11 is 13s   left child
 9 is 11s   left child
 8 is  9s   left child
10 is  9s  right child
12 is 11s  right child
15 is 13s  right child
14 is 15s   left child
16 is 15s  right child

== 删除根节点: 8
== 高度: 5
== 中序遍历: 1 2 3 4 5 6 7 9 10 11 12 13 14 15 16 
== 树的详细信息: 
 7 is root
 4 is  7s   left child
 2 is  4s   left child
 1 is  2s   left child
 3 is  2s  right child
 6 is  4s  right child
 5 is  6s   left child
13 is  7s  right child
11 is 13s   left child
 9 is 11s   left child
10 is  9s  right child
12 is 11s  right child
15 is 13s  right child
14 is 15s   left child
16 is 15s  right child
AVL树(一)之 图文解析 和 C语言的实现

 

下面,我们对测试程序的流程进行分析!

1. 新建AVL树
   新建AVL树的根节点root。

 

2. 依次添加"3,2,1,4,5,6,7,16,15,14,13,12,11,10,8,9" 到AVL树中,过程如下。
2.01 添加3,2
添加3,2都不会破坏AVL树的平衡性。

AVL树(一)之 图文解析 和 C语言的实现

 

2.02 添加1
添加1之后,AVL树失去平衡(LL),此时需要对AVL树进行旋转(LL旋转)。旋转过程如下:

AVL树(一)之 图文解析 和 C语言的实现

 

2.03 添加4
添加4不会破坏AVL树的平衡性。

AVL树(一)之 图文解析 和 C语言的实现

 

2.04 添加5
添加5之后,AVL树失去平衡(RR),此时需要对AVL树进行旋转(RR旋转)。旋转过程如下:

AVL树(一)之 图文解析 和 C语言的实现

 

2.05 添加6
添加6之后,AVL树失去平衡(RR),此时需要对AVL树进行旋转(RR旋转)。旋转过程如下:

AVL树(一)之 图文解析 和 C语言的实现

 

2.06 添加7
添加7之后,AVL树失去平衡(RR),此时需要对AVL树进行旋转(RR旋转)。旋转过程如下:

AVL树(一)之 图文解析 和 C语言的实现

 

2.07 添加16
添加16不会破坏AVL树的平衡性。

AVL树(一)之 图文解析 和 C语言的实现

 

2.08 添加15
添加15之后,AVL树失去平衡(RR),此时需要对AVL树进行旋转(RR旋转)。旋转过程如下:

AVL树(一)之 图文解析 和 C语言的实现

 

2.09 添加14
添加14之后,AVL树失去平衡(RL),此时需要对AVL树进行旋转(RL旋转)。旋转过程如下:

AVL树(一)之 图文解析 和 C语言的实现

 

2.10 添加13
添加13之后,AVL树失去平衡(RR),此时需要对AVL树进行旋转(RR旋转)。旋转过程如下:

AVL树(一)之 图文解析 和 C语言的实现

 

2.11 添加12
添加12之后,AVL树失去平衡(LL),此时需要对AVL树进行旋转(LL旋转)。旋转过程如下:

AVL树(一)之 图文解析 和 C语言的实现

 

2.12 添加11
添加11之后,AVL树失去平衡(LL),此时需要对AVL树进行旋转(LL旋转)。旋转过程如下:

AVL树(一)之 图文解析 和 C语言的实现

 

2.13 添加10
添加10之后,AVL树失去平衡(LL),此时需要对AVL树进行旋转(LL旋转)。旋转过程如下:

AVL树(一)之 图文解析 和 C语言的实现

 

2.14 添加8
添加8不会破坏AVL树的平衡性。

AVL树(一)之 图文解析 和 C语言的实现

 

2.15 添加9
但是添加9之后,AVL树失去平衡(LR),此时需要对AVL树进行旋转(LR旋转)。旋转过程如下:

AVL树(一)之 图文解析 和 C语言的实现


3. 打印树的信息
输出下面树的信息:

AVL树(一)之 图文解析 和 C语言的实现

前序遍历: 7 4 2 1 3 6 5 13 11 9 8 10 12 15 14 16
中序遍历: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
后序遍历: 1 3 2 5 6 4 8 10 9 12 11 14 16 15 13 7
高度: 5
最小值: 1
最大值: 16

 

4. 删除节点8

删除操作并不会造成AVL树的不平衡。

AVL树(一)之 图文解析 和 C语言的实现

删除节点8之后,在打印该AVL树的信息。
高度: 5
中序遍历: 1 2 3 4 5 6 7 9 10 11 12 13 14 15 16

AVL树(一)之 图文解析 和 C语言的实现,布布扣,bubuko.com

AVL树(一)之 图文解析 和 C语言的实现

上一篇:Java开发中未整理的资料


下一篇:C++之继承与多态