AVL樹仍然是一棵二叉查找樹囱淋。
平衡是指對(duì)AVL樹的任意結(jié)點(diǎn)來說，其左子樹和右子樹的高度之差的絕對(duì)值不超過1。
平衡因子是指左子樹和右子樹的高度之差。
因此需要在樹的結(jié)構(gòu)中加入一個(gè)變量height
左旋的三個(gè)步驟：
①讓B的左子樹成為A的右子樹
②讓A成為B的左子樹
③將根結(jié)點(diǎn)設(shè)定為結(jié)點(diǎn)B
右旋則把左旋代碼里的lchild改為rchild筐付，rchild改為lchild就行了
LL、LR阻肿、RR瓦戚、RL：
在這個(gè)基礎(chǔ)上，由于需要從插入的結(jié)點(diǎn)開始從下往上判斷結(jié)點(diǎn)是否平衡丛塌，因此需要在每個(gè)insert函數(shù)之后更新當(dāng)前子樹的高度较解，并在這之后根據(jù)樹型是LL型、LR型赴邻、RR型印衔、RL型之一來進(jìn)行平衡的操作：
