AVL树的删除操作

虽然AVL树的删除操作比较麻烦。
但是明白了插入过程，删除过程也就不难理解。
递归删除的实现，也是沿着树递归向下寻找，直到找到该元素。
如果只有一个儿子或没有儿子那么直接删除他，返回
他的儿子(或空节点)，和插入操作一样，因为是带返回的插入，在回溯的过程会将他们连接起来。所以我们只要返回
其儿子(或空)就行了。
如果是两个儿子，那么就有点麻烦了。因为正真要删除的是其右子树中的最小关键字。
对有两个儿子的删除操作，还要对其右子树使用一个递归历程。递归的寻找左儿子，当左儿子的儿子为空是，即找到
右子树中的最小关键字。于是删除他返回其儿子节点(空节点)。
无论是如何删除的，删除后的回溯过程都需要修复可能的高度规则破坏。即判断左右子树高度差是不是小于1
不如不是，那么就要进行修复操作。通过比较左右子树的高度差，根据比较结果再在比较 左子树/右子树 的左右子树高度
差，从而判断对应那种旋转修复操作。

我们先来看删除的修复模块如下：

static NODE delete_fixup(NODE node){        //删除修复过程
    if(node_height(node->left) > node_height(node->right)){                    //如果左儿子高度大于右儿子高度
        if(node_height(node->left->left) >= node_height(node->left->right))//并且左儿子的左子树高度大于左儿子的右子树高度
            node=single_right_rotate(node,node->left);                        //那么使用 对应单旋转
        else
            node=double_right_rotate(node,node->left,node->left->right);    //否则使用 双旋转
    }else{                                                                    //如果右儿子高度大于左儿子，操作是对应的
        if(node_height(node->right->right) >= node_height(node->right->left))
            node=single_left_rotate(node,node->right);
        else
            node=double_left_rotate(node,node->right,node->right->left);
    }
    return node;
}

看过前面插入分析的，应该发现删除操作的修复操作几乎和插入是一样的。不同的是这里没有用关键字来判断
应该使用上面旋转而是直接用高度比较来看应该用什么旋转。并且旋转操作和插入的旋转操作是一样的，十分简洁，并且压根就没用到父指针。
这也是递归删除的"优雅"之处，虽然频繁的递归会影响效率，但是带来的简洁性却容易让我们理解删除的正真原理。
非递归的实现不得不为旋转操作引入父指针，那么旋转操作要做的工作量是复杂且可观的。甚至还需要考虑删除的是根节点，从而需要改变根指针
指向的问题。

明白了修复过程，下面就是删除操作

先看当沿着树递归遍历到找到关键字时的 具体删除操作

NODE _delete(NODE root){
        if(root->left==NULL ){            //只有右儿子(或都为空)
            root = delete_have_right_child(root);
        }else if(root->left != NULL && root->right == NULL){    //只有左儿子
            root = delete_have_left_child(root);
        }else if(root->left != NULL && root->right != NULL){        //两个儿子，那么删除的实际上是右子树中的最小元素，别忘了要交换关键字
            root->right=delete_have_two_child(root->right,root);    //所以传入了当前节点root指针，好在删除的时候和其交换关键字
        }

        if(root != NULL){
            root->height = MAX(node_height(root->left),node_height(root->right))+1;        //更新高度如果删除节点是有两个儿子节点，那么删除
                                                                                        //的是其后代，所以需要更新高度
            if(height_difference(node_height(root->left),node_height(root->right)) >=2){ //查看高度规则是否被破坏了
                root=delete_fixup(root);
                root->height = MAX(node_height(root->left),node_height(root->right))+1;//旋转后更新高度

            }
        }
        return root;
}

正如代码所示，根据左右儿子的情况来调用相应的删除操作。删除操作完成后，因为可能会导致 真是高度已经变了，所以需要更新高度。
同时还需判断高度规则是否被破坏了。如果被破坏了，也需要调用修复操作来修复高度规则
对 只有一个儿子节点的删除很简单，因为删除操作都是带返回的，所以我们所要做的仅仅只是返回其儿子节点(可能为空)

static NODE delete_have_right_child(NODE node){        //对于只有一个儿子的节点的删除，只要释放其节点，返回子节点就行了。
    NODE child = node->right;
    free(node);
    return child;
}
static NODE delete_have_left_child(NODE node){
    NODE child    = node->left;
    free(node);
    return child;
}

但是对于有两个儿子的节点的删除，因为真正删除的是其右子树中的最小元素，所以可能稍微复杂点。并且这里也是用递归来实现
需要注意的是，因为这里也牵涉到，沿着树往下寻找要删除的节点(最小元素),所以在删除后的回溯过程，用样需要更新高度和修复可能被破坏的高度规则，找到最小元素后那么删除该节点就和删除一般节点(只有一个儿子或没有)一样了，即直接返回该节点的儿子节点就行了(右儿子)。

static NODE delete_have_two_child(NODE node,NODE true_node){            //对于删除有两个儿子的节点，我们传入的node 为要删除节点的
    if(node->left != NULL){                                                //右儿子，然后对node 递归的搜索左儿子,直到左儿子为空
        node->left = delete_have_two_child(node->left,true_node);        //那么该元素就是真正要删除的节点，true_node为想删除的，传进来是为了交换关键字

        if(height_difference(node_height(node->left),node_height(node->right)) >=2){            //对于有双儿子的删除节点
            node= delete_fixup(node);                                                            //删除后的回溯过程也需要旋转操作
        }                                                                                        //来修正可能出现的高度规则破坏
        node->height = MAX(node_height(node->left),node_height(node->right))+1;    //经历了可能的旋转后需要更新高度
        return node;
    }
    true_node->key = node->key;
    NODE temp = node->right;
    free(node);
    return temp;                //别忘了返回节点
}

明白了具体的删除过程，那么下面就是删除过程的框架了，

static NODE _delete_key(TYPE key,NODE root){
     if((root != NULL )&&(root->key == key)){        //当前节点关键字即是要删除的关键字，找到关键字元素了
        root=_delete(root);
        return root;
    }else if(root != NULL) {    //当前节点关键字不是要删除的关键字，继续向子树中寻找
            if(key <root->key){        //向左子树中寻找
                root->left = _delete_key(key,root->left);
            }else{                    //向右子树中寻找
                root->right = _delete_key(key,root->right);
            }
            if(height_difference(node_height(root->left),node_height(root->right)) >=2){
                root=delete_fixup(root);
            }
            root->height = MAX(node_height(root->left),node_height(root->right))+1;    //旋转后跟新高度
            return root;
    }
    printf(":can't find key:%d",key); //递归寻找到树的最低层，没有找到要删除的
    return NULL;
}

代码正如文章开头所述的流程，判断当前关键字是否是要删除的，不是那么就递归的往左子树或右子树中寻找。在找到并删除后需要修复可能被破坏的
高度规则，以及更更新高度。注意，最终还要返回当前节点。同插入一样，删除也正是通过带返回的特性从而使在删除回溯过程中树能顺利连接
起来。


这里删除操作也就分析完了。后面是整个插入和删除的测试代码。
实现了树的打印代码。会打印每个节点的高度，以及左右子树的高度。如果左右子树高度差大于 2 ，会给出错误提示。
没有则说明符合高度规则。
最后三行会出现 AVl 树的一般理论最大高度 1.44log(N+2)-1.328  （log以 2 为底）
以及 插入操作后的 AVL树高度
和 删除操作执行后的树高度
测试代码中进行了 20万次的插入然后打印，和20次的删除然后打印。
从输出结果可以看出，树的正确性。

main.c

#include"avl_tree.h"
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<math.h>

#define COUNT 200000

int main(void){
    srand((unsigned int)time(0));

    int i;

    int height1,height2;
    AVL_TREE tree;
    init_avl_tree(tree);
    for(i=0;i<COUNT;i++){
        insert_key_recursion(rand()%(COUNT*2),tree);
    }

    height1=print(tree);


    printf("\n\n*************delete******************\n\n");

    for(i=0;i<(COUNT);i++){
        delete_key(rand()%(COUNT*2),tree);
    }


    height2=print(tree);
    printf("log2(%d)=%f\n",COUNT,(log(COUNT+2)/log(2))*1.44-1.328);
    printf("after inster, height:%d\n",height1);
    printf("after delete, height:%d\n",height2);
    return 0;
}

avl_tree.h

#ifndef AVL_TREE_H_
#define AVL_TREE_H_

typedef int TYPE;

struct avl_tree;
typedef struct avl_tree *AVL_TREE;

struct tree_node;
typedef struct tree_node *NODE;

//初始化函数一般应该是没有返回值的，所以这里用宏来实现
#define init_avl_tree(TREE)    \
        (TREE =_init_avl_tree())

AVL_TREE _init_avl_tree(void);


void  insert_key_recursion(TYPE key,AVL_TREE tree);
void delete_key(TYPE key,AVL_TREE tree);

//测试 avl 树的高度
//理论高度 1.44log(N+2)-1.328  （log为 以2为底）
//打印操作返回的是树的高度
int print(AVL_TREE tree);
#endif

 avl_tree.c

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

struct avl_tree{
    NODE root;
};

struct tree_node{
    TYPE key;
    NODE left;
    NODE right;
    int height;
};

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

/*
    获得一个欲插入树中的关键字的节点
    key : 节点中的关键字
*/
static NODE  malloc_node(TYPE key);

static int is_empty(AVL_TREE tree);
static int height_difference(int left,int right);    //求高度差
static int    node_height(NODE node);            //求一个节点的高度 NULL高度认为是 -1
static NODE insert(TYPE key,NODE root);        //递归插入的正真实现


//单旋转,插入右子树的右子树后的旋转修复
static NODE single_left_rotate(NODE grandfather,NODE right_father);
 //单旋转,插入左子树的左节点后的旋转修复
static NODE single_right_rotate(NODE grandfather,NODE left_father);
//双旋转，插入到右子树的左子树后的旋转修复
static NODE double_left_rotate(NODE grandfather,NODE right_father,NODE left_child);
//双旋转，插入到左子树的右子树后的旋转修复
static NODE double_right_rotate(NODE grandfather,NODE left_father,NODE rifght_child);

static NODE find_key(TYPE key,AVL_TREE tree);
//对于删除节点没有儿子的情况，case2 case3的删除都可以适用
//删除操作均返回被删除节点的父节点。因为父节点是第一个高度规则被破坏的节点。从父节点开始
//向上遍历来修复路径上可能被破坏的高度规则
static NODE delete_have_two_child(NODE node);        //删除节点有两个儿子节点，则删除右子树中的最小节点
static NODE delete_have_left_child(NODE node);        //删除节点有一个右儿子
static NODE delete_have_right_child(NODE node);        //删除节点有一个左儿子
static NODE delete_fixup(NODE node);                        //删除操作后的修复操作，从被删除节点的父节点开始向上遍历到根修复


AVL_TREE _init_avl_tree(void){
    AVL_TREE tree;
    tree = (AVL_TREE)malloc(sizeof(struct avl_tree));
    if(tree == NULL){
        printf("malloc error: in init_avl_tree\n");
        exit(1);
    }
    tree->root = NULL;

    return tree;
}

static NODE insert(TYPE key,NODE root){            //递归插入的思想核心的沿着树下降直到找到关键字应该插入的位置(此时应该是遍历到NULL节点停止了)
    if(root == NULL){                            //然后将 新节点 赋值，最后按递归顺序在原路返回到根节点处。因为插入是带返回的插入，所以返回
        NODE node = malloc_node(key);            //的过程也就将树连接好了。（同时伴随着高度的修复操作）
        return node;
    }else{
        if(key < root->key){                        //应该插入到左子树中
            root->left = insert(key,root->left);
            if(node_height(root->left)-node_height(root->right) >= 2){    //插入导致高度被破坏
                if(key < root->left->key)                                //判断是插入哪里导致高度规则被破坏
                    root = single_right_rotate(root,root->left);        //如果插入到左子树中的左边则执行一次对应的单旋转
                else                                                    //否则执行对应的 双旋转
                    root = double_right_rotate(root,root->left,root->left->right);
            }
        }else{                                            //插入的右子树的操作是对应的
            root->right =insert(key,root->right);
            if(node_height(root->right)-node_height(root->left) >= 2){
                if(key >= root->right->key)
                    root = single_left_rotate(root,root->right);
                else
                    root = double_left_rotate(root,root->right,root->right->left);
            }
        }
    }

    //经过旋转后 root可能已经不是原来的 root 节点了，所以需要重新计算高度
    root->height = MAX(node_height(root->left),node_height(root->right)) +1;

    return root;    //需要返回当前节点，正事插入的返回操作使得树的递归在返回过程中将树连接起来
}


void insert_key_recursion(TYPE key,AVL_TREE tree){
    tree->root = insert(key,tree->root);
    printf("\n\n");
}


static is_empty(AVL_TREE tree){
    return tree->root == NULL;
}

static int node_height(NODE node){
    if(node == NULL){
        return (-1);
    }else{
        return node->height;
    }
}

static int height_difference(int left,int right){
    int hd = left - right;
    if(hd <0)
        return (hd*(-1));
    else
        return hd;
}
static NODE  malloc_node(TYPE key){
    NODE node;
    node = (NODE)malloc(sizeof(tree_node));
    if(node == NULL){
        printf("malloc error: in malloc_node\n");
        exit(1);
    }
    node->key    = key;
    node->left    = NULL;
    node->right    = NULL;
    node->height = 0;
    return node;
}


static NODE single_left_rotate(NODE father,NODE right_child){    //左旋(单旋转)

    father->right = right_child->left;
    right_child->left     = father;
    //更新高度
    father->height = MAX(node_height(father->left),node_height(father->right))+1;
    right_child->height = MAX(node_height(right_child->left),node_height(right_child->right))+1;
    return right_child;    //返回新的父节点
}
static NODE single_right_rotate(NODE father,NODE left_child){ //右旋(右旋转)
    father->left = left_child->right;
    left_child->right = father;

    father->height = MAX(node_height(father->left),node_height(father->right))+1;
    left_child->height = MAX(node_height(left_child->left),node_height(left_child->right))+1;
    return left_child; //返回新的父节点
}
static NODE double_left_rotate(NODE grandfather,NODE right_father,NODE left_child){    //双旋转(高度被破坏的节点，相对和其左旋转的儿子的位置 在左边)
    grandfather->right = single_right_rotate(right_father,left_child);    //先进行一次右旋，将"破坏高度因素"旋转至外侧
    return single_left_rotate(grandfather,grandfather->right);            //在进行一次左旋就完成了.（这时就如同修复插入到右儿子的右子树中的情况一样）
}

static NODE double_right_rotate(NODE grandfather,NODE left_father,NODE right_child){ //双旋转(高度被破坏的节点，相对和其左旋转的儿子的位置 在右边)
    grandfather->left = single_left_rotate(left_father,right_child); //先进行一次左旋，将"破坏高度因素"旋转至外侧
    return single_right_rotate(grandfather,grandfather->left);            //再进行一次右旋就完成了.（这时就如同修复插入到左儿子的左子树中的情况一样）
}

static NODE delete_have_right_child(NODE node){        //对于只有一个儿子的节点的删除，只要释放其节点，返回子节点就行了。
    NODE child = node->right;
    free(node);
    return child;
}
static NODE delete_have_left_child(NODE node){
    NODE child    = node->left;
    free(node);
    return child;
}
static NODE delete_fixup(NODE node){        //删除修复过程
    if(node_height(node->left) > node_height(node->right)){                    //如果左儿子高度大于右儿子高度
        if(node_height(node->left->left) >= node_height(node->left->right))//并且左儿子的左子树高度大于左儿子的右子树高度
            node=single_right_rotate(node,node->left);                        //那么使用 对应单旋转
        else
            node=double_right_rotate(node,node->left,node->left->right);    //否则使用 双旋转
    }else{
        if(node_height(node->right->right) >= node_height(node->right->left))
            node=single_left_rotate(node,node->right);
        else
            node=double_left_rotate(node,node->right,node->right->left);
    }
    return node;
}
static NODE delete_have_two_child(NODE node,NODE true_node){            //对于删除有两个儿子的节点，我们传入的node 为要删除节点的
    if(node->left != NULL){                                                //右儿子，然后对node 递归的搜索左儿子,直到左儿子为空
        node->left = delete_have_two_child(node->left,true_node);        //那么该元素就是真正要删除的节点

        if(height_difference(node_height(node->left),node_height(node->right)) >=2){            //对于有双儿子的删除节点
            node= delete_fixup(node);                                                            //删除后的回溯过程也需要旋转操作
        }                                                                                        //来修正可能出现的高度规则破坏
        node->height = MAX(node_height(node->left),node_height(node->right))+1;
        return node;
    }
    true_node->key = node->key;
    NODE temp = node->right;
    free(node);
    return temp;
}

NODE _delete(NODE root){
        if(root->left==NULL ){            //只有右儿子(或都为空)
            root = delete_have_right_child(root);
        }else if(root->left != NULL && root->right == NULL){    //只有左儿子
            root = delete_have_left_child(root);
        }else if(root->left != NULL && root->right != NULL){        //两个儿子，那么删除的实际上是右子树中的最小元素，别忘了要交换关键字
            root->right=delete_have_two_child(root->right,root);    //所以传入了当前节点root指针，好在删除的时候和其交换关键字
        }

        if(root != NULL){
            root->height = MAX(node_height(root->left),node_height(root->right))+1;        //更新高度如果删除节点是有两个儿子节点，那么删除
                                                                                        //的是其后代，所以需要更新高度
            if(height_difference(node_height(root->left),node_height(root->right)) >=2){ //查看高度规则是否被破坏了
                root=delete_fixup(root);
                root->height = MAX(node_height(root->left),node_height(root->right))+1;//旋转后更新高度

            }
        }
        return root;
}

//删除操作真正的执行程序
static NODE _delete_key(TYPE key,NODE root){
     if((root != NULL )&&(root->key == key)){        //当前节点关键字即是要删除的关键字，找到关键字元素了
        root=_delete(root);
        return root;
    }else if(root != NULL) {    //当前节点关键字不是要删除的关键字，继续向子树中寻找
            if(key <root->key){        //向左子树中寻找
                root->left = _delete_key(key,root->left);
            }else{                    //向右子树中寻找
                root->right = _delete_key(key,root->right);
            }
            if(height_difference(node_height(root->left),node_height(root->right)) >=2){
                root=delete_fixup(root);
            }
            root->height = MAX(node_height(root->left),node_height(root->right))+1;    //旋转后跟新高度
            return root;
    }
    printf(":can't find key:%d",key); //递归寻找到树的最低层，没有找到要删除的
    return NULL;
}

void delete_key(TYPE key,AVL_TREE tree){
    printf("\n delete %d ",key);
    if(is_empty(tree)){
        printf("the tree is empty\n");
        exit(1);
    }
    tree->root=_delete_key(key,tree->root);
}

int max_height;
static void _print(NODE root){        //print打印树程序的正真驱动程序
    if( NULL){
        if(height_difference(node_height(root->left),node_height(root->right)) >=2){
            printf("\n\nheight difference greater than 2\n\n");
            exit(1);
        }
        max_height = MAX(max_height,root->height);
        _print(root->left);
        printf("\nkey:%d  height: %d  (left height: %d   right height: %d  )  %s",
                root->key,node_height(root),node_height(root->left),node_height(root->right),
                height_difference(node_height(root->left),node_height(root->right))>=2?"error:height difference greater than 2" : "");
        _print(root->right);
    }
}
int print(AVL_TREE tree){
    max_height =0;
    NODE root = tree->root;
    _print(root);
    printf("\n");
    return max_height;
}