高子樹是什麼樹

高子樹是最古老的平衡二叉樹，又叫AVL樹。

AVL樹性質：

1、左右子樹高度差不超過1.

複雜度：

插入O(logn)，最多做兩次旋轉，若干次維護樹高。

刪除O(logn)，最壞情況做logn次平衡。

旋轉操作

插入：

與BST一樣，小於當前節點往左子樹，大於往有子樹。回溯時平衡樹高。

刪除：

遞歸查找到目標值的節點

1、如果目標節點是單鏈節點（只有一個兒子），或沒有兒子的節點，則就地刪除，用空指針或兒子替代它。

2、如果目標節點有兩個兒子，則遞歸查找它的前驅，用前驅替代它，然後刪除前驅節點。

樹高修正：

當插入或刪除節點時，可能引發高度差超過1，則進行修正。

大前提：左右子樹高度差大於1。

最終目的是使樹達到平衡

那麼只有從高子樹旋轉向低子樹才能做得到。

高子樹總是向父親方向旋轉的

對於高子樹，還有保證父同側的兒子節點的樹高不大於另一個兒子樹高， 如果不滿足則需要旋轉。