删除
虽然，二叉排序树的插入都在叶子节点，但是删除却可以分为三种不同的情况；
（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);
}
}
}
}
标签：lchild,左子,结点,temp,getHeight,AVL,添加,rchild,data From： https://www.cnblogs.com/saucerdish/p/17850340.html