AVL添加和删除结点-526互联

删除

虽然，二叉排序树的插入都在叶子节点，但是删除却可以分为三种不同的情况；

（1）删除的节点刚好是叶子结点——直接删除

1 if ((*T)->lchild == NULL && (*T)->rchild == NULL)
2         {
3             //为叶子结点，直接删除
4             TreeNode* temp = *T;
5             *T = NULL;
6             free(temp);
7             return;//直接返回上一次循环去判断
8         }

(2)删除的节点只有左孩子或者只有右孩子，直接让其唯一的那个孩子去替代父母的位置

 1 else if ((*T)->lchild == NULL && (*T)->rchild) 
 2         {
 3             //删除结点没有左子树，将右子树上移就可以
 4             TreeNode* temp = *T;
 5             *T = (*T)->rchild;
 6             free(temp);
 7             return;
 8         }
 9         else if ((*T)->rchild == NULL && (*T)->lchild)
10         {
11             //删除结点没有右子树，将左子树上移就可以
12             TreeNode* temp = *T;
13             *T = (*T)->lchild;
14             free(temp);
15             return;
16         }

（3）删除的节点既有左孩子又有右孩子，两种删除方法

①左子树“上位”，右子树合并到左子树，因为右子树上节点肯定都比左子树上的大，所以把右子树的根接到左子树的最右下（对应下面的方法2）

②左子树最右下角作为最接近被删节点的节点之一，可以直接替代子树的父母(左子树最大直上位）

 1 else if ((*T)->lchild&& (*T)->rchild) 
 2         {
 3             //左右子树都存在
 4             if (getHeight((*T)->lchild) > getHeight((*T)->rchild))
 5             {
 6                 //.找到左子树中的最大值，将值赋给给节点，然后将左子树最大值这个节点删除
 7                 TreeNode* temp = Getmax((*T)->lchild);
 8                 int maxnode = temp->data;
 9                 (*T)->data = maxnode;
10                 deletenode(&(*T)->lchild, maxnode);
11             }
12             else
13             {
14                 //寻找后继节点post。
15                 TreeNode* post = (*T)->rchild;
16                 while (post->lchild)
17                     post = post->lchild;
18                 //用post替换*T。
19                 (*T)->data = post->data;
20 
21                 //删除节点post。
22                 //虽然能够确定post所属最小子树的根结点为&post，
23                 //但是不采用AVLDelete(&post,post->data)删除post，目的是方便递归更改节点的高度。
24                 deletenode(&((*T)->rchild), post->data);
25             }
26             return;
27         }

删除节点为叶节点。这种情况最简单，直接将其置空，释放，然后返回给父节点即可。
删除节点有左子树没有右子树。先保存该节点的地址(方便释放)，将该节点直接等于左子树地址，相当于该节点存的就是左子树的地址，将原来节点地址覆盖了。然后释放。
删除节点有右子树没有左子树。与2处理相同，只是将左子树换为右子树。
既有左子树又有右子树
可以有两种解决办法：
1.找到左子树中的最大值，将值赋给给节点，然后将左子树最大值这个节点删除(删除可以用递归实现)
2.找到左子树中的最小值，将值赋给给节点，然后将右子树最小值这个节点删除
当然这样会有个弊端：当一直删除时，会导致树高度失衡，导致一边高，一边低，解决这样的办法可以删除左右子树最大最小节点交替实行。或者记录一高度，主要删除，左子树或者右子树高的那一边。

平衡化（看每个图片右下角）

因为二叉排序树有变成单只树（线性表）的风险，为了保证二叉排序树的效率与log2n同数量级,所以要将二叉排序树调成平衡二叉树。
平衡二叉树：根结点的左子树深度-右子树深度的绝对值不超过1。
不平衡共有以下四种情况
平衡化关键是：找到最小的非平衡二叉树的根其平衡因子绝对值一定是2，则其之前的平衡因子绝对值一定为1，分清除不平衡的类型
（1）最小的非平衡二叉树的根（A）的左子树(AL)的左子树上加了节点导致其不平衡简称（LL型）
做法：AL上去，A下来作为AL的右孩子，AL原本的右孩子作为A的左孩子

1 void llRotation(TreeNode* node, TreeNode** root)
2 {
3     TreeNode* temp = node->lchild;
4     node->lchild = temp->rchild;
5     temp->rchild = node;
6     node->height = max(getHeight(node->lchild), getHeight(node->rchild)) + 1;
7     temp->height = max(getHeight(temp->lchild), getHeight(temp->rchild)) + 1;
8     *root = temp;
9 }

（2）RR型
做法：AR上去，A下来作为AR的左孩子，AR原本的左孩子作为A的右孩子

1 void rrRotation(TreeNode* node, TreeNode** root)
2 {
3     TreeNode* temp = node->rchild;
4     node->rchild = temp->lchild;
5     temp->lchild = node;
6     node->height = max(getHeight(node->lchild), getHeight(node->rchild)) + 1;
7     temp->height = max(getHeight(temp->lchild), getHeight(temp->rchild)) + 1;
8     *root = temp;
9 }

（3）LR型
①ALR（A的左孩子的右孩子）上去；②AL作为ALR的左孩子，ALR左孩子放到AL的右孩子；③A作为ALR的右孩子，ALR的右孩子放到A的左孩子。

1 //LR调整
2                 rrRotation((*T)->lchild, &(*T)->lchild);
3                 llRotation(*T, T);

（4）RL型
①ARL（A的右孩子的右孩子）上去；②AR作为ALR的右孩子，ARL右孩子放到AR的右孩子；③A作为ARL的左孩子，ARL的左孩子放到A的右孩子。

1 //RL调整
2                 llRotation((*T)->rchild, &(*T)->rchild);
3                 rrRotation(*T, T);

插入(判断什么型的判断条件注意）

 1 void avlInsert(TreeNode** T, int data)
 2 {
 3     if (*T == NULL)
 4     {
 5         *T = (TreeNode*)malloc(sizeof(TreeNode));
 6         (*T)->data = data;
 7         (*T)->height = 0;
 8         (*T)->lchild = NULL;
 9         (*T)->rchild = NULL;
10     }
11     else if (data < (*T)->data)
12     {
13         avlInsert(&(*T)->lchild, data);
14 
15         int lHeight = getHeight((*T)->lchild);
16         int rHeight = getHeight((*T)->rchild);
17 
18         //计算高度差=平衡因子，左右子树不平衡就调整
19         if (lHeight - rHeight == 2)
20         {
21             if (data < (*T)->lchild->data)
22                 //LL调整
23                 llRotation(*T, T);
24             else
25             {
26                 //LR调整
27                 rrRotation((*T)->lchild, &(*T)->lchild);
28                 llRotation(*T, T);
29             }
30         }
31     }
32     else if (data > (*T)->data)
33     {
34         avlInsert(&(*T)->rchild, data);
35 
36         int lHeight = getHeight((*T)->lchild);
37         int rHeight = getHeight((*T)->rchild);
38 
39         //计算高度差=平衡因子，左右子树不平衡就调整
40         if (lHeight - rHeight == -2)
41         {
42             if (data > (*T)->rchild->data)
43                 //RR调整
44                 rrRotation(*T, T);
45             else
46             {
47                 //RL调整
48                 llRotation((*T)->rchild, &(*T)->rchild);
49                 rrRotation(*T, T);
50             }
51         }
52     }
53     //更新树结点的高度
54     (*T)->height = max(getHeight((*T)->lchild), getHeight((*T)->rchild)) + 1;
55 }

删除（重点看如何平衡化的，判断什么型最关键）

void deletenode(TreeNode** T, int key)
{
    if ((*T) == NULL)
    {
        cout << "不存在" << key << endl;
        return;
    }
    else if ((*T)->data == key)
    {
       //文章前面有
    }
    else if ((*T)->data > key)
    {
        deletenode(&(*T)->lchild, key);

        //更新树结点的高度
        (*T)->height = max(getHeight((*T)->lchild), getHeight((*T)->rchild)) + 1;

        int lHeight = getHeight((*T)->lchild);
        int rHeight = getHeight((*T)->rchild);

        //计算高度差=平衡因子，左右子树不平衡就调整
        if (lHeight - rHeight == -2)
        {
            if (getHeight((*T)->rchild->lchild) - getHeight((*T)->rchild->rchild) == -1)
                //RR调整
                rrRotation(*T, T);
            else
            {
                //RL调整
                llRotation((*T)->rchild, &(*T)->rchild);
                rrRotation(*T, T);
            }
        }
    }
    else if ((*T)->data < key)
    {
        deletenode(&(*T)->rchild, key);

        //更新树结点的高度
        (*T)->height = max(getHeight((*T)->lchild), getHeight((*T)->rchild)) + 1;

        int lHeight = getHeight((*T)->lchild);
        int rHeight = getHeight((*T)->rchild);

        //计算高度差=平衡因子，左右子树不平衡就调整
        if (lHeight - rHeight == 2)
        {
            if (getHeight((*T)->lchild->lchild) - getHeight((*T)->lchild->rchild) == 1)
                //LL调整
                llRotation(*T, T);
            else
            {
                //LR调整
                rrRotation((*T)->lchild, &(*T)->lchild);
                llRotation(*T, T);
            }
        }
    }
    
}