AVL樹是一種緊湊的二叉查找樹。它的每個結點，都有左右子樹高度相等，或者只相差1這樣的特性。文章https://blog.csdn.net/aaasssdddd96/article/details/106291144給出了一個例子。

為了便于討論，這里對AVL樹的結點平衡情況定義2個名稱，如果兩邊左右子樹高度相等，稱之為真平衡，如果兩邊高度相差1，稱之為準平衡。真平衡和準平衡的這個意義只限于在本文的討論。準平衡有2種情況，所以實際是3種情況。

當AVL樹中插入一個新結點時，它的父結點如果是真平衡，那么狀態轉化為準平衡，樹的高度增加了1，因為高度增加，這個父結點需要接著向更高一層的父結點報告這個變化。

如果父結點是準平衡，那么也有2種情況。如果增加的高度是在較矮的一側，那么父結點狀態轉為真平衡，操作完成；如果增加的高度是在較高的一側，那么結點的平衡因子超限，這種情況在上面第一種情況的最后一個變化發生，需要進行平衡調整。調整之后，恢復為真平衡，局部高度不增，操作完成。

這些問題不難。真正讓初學者感到煩惱的是平衡調整。調整分4種情況，分別稱為“LL-旋轉”，“LR-旋轉”，“RL-旋轉”，“RR-旋轉”。后2種和前兩種鏡像對應。編寫這部分代碼的時候，最好寫完前2種，休息20分鐘，再去復制前面的代碼，逐條改成它的鏡像。休息片刻是為了避免頭暈，轉來轉去轉的頭一暈，修改鏡像時隨便漏掉一條，就會帶來極為費時難調的bug。這樣編程并沒有什么不對，這是需要掌握的基本功，而且實際開發過程也會常常碰到需要蠻力硬搞來攻克的難題。

但在這里是否有比硬搞好一點的辦法?

如果在構造AVL樹時，預分配3個儲備結點會怎么樣。左、中、右，預先結成一個三角形。但不在AVL樹中，而是備用：

struct avl_help {struct node *root;struct triangle {struct node *left;struct node *mid;struct node *right;} help;
};struct avl_help avl;

初始化為：

avl.root=NULL;
avl.help.left = (struct node*)malloc(sizeof(struct node));
avl.help.mid = (struct node*)malloc(sizeof(struct node));
avl.help.right = (struct node*)malloc(sizeof(struct node));avl.help.mid->left=avl.help.left;
avl.help.mid->right=avl.help.right;
avl.help.left->parent=avl.help.mid;
avl.help.right->parent=avl.help.mid;

現在大家都想到了：在AVL樹需要發生平衡調整的時候，把已經調好的3個儲備結點拿出來，整體替換掉樹中需要調整的3個結點，再把替換下來的原來的3個結點做成初始化中的左、中、右三角結構，存回到help中儲備，留給下次用。這樣調整就完成了。而替換下來的3個結點只要把頭結點連到中間結點的左指針，或右指針，具體看那個指針空閑，就重新構成了三角結構。

以“LR型-旋轉”為例，調整操作大致是這樣子。假設ap0,ap1,ap2三個指針已經分別指向LR型的待調整的上中下3個結點：

help= &avl.help;
help->left->left=ap1->left;
help->left->right=ap2->left;
help->left->tag=(ap2->tag==1?0:-1);help->right->left=ap2->right;
help->right->right=ap0->right;
help->right->tag=(ap2->tag==-1?1:0);help->mid->tag=0;
if(help->left->left)
help->left->left->parent=help->left;
if(help->left->right)
help->left->right->parent=help->left;
if(help->right->left)
help->right->left->parent=help->right;
if(help->right->right)
help->right->right->parent=help->right;
help->mid->parent=ap0->parent;if(help->mid->parent==NULL)
avl->root= help->mid;
else if(help->mid->parent->left==ap0)
help->mid->parent->left=help->mid;
else help->mid->parent->right=help->mid;

而存回替換下來的ap0,ap1,ap2三個結點的代碼就是：

ap1->left=ap0;
ap0->parent=ap1;
help->left= ap0;
help->mid=ap1;
help->right=ap2;

其它幾種情況可以類推，大同小異，這里就不重復了。