題組內容

三、給定一棵二元搜尋樹(binary search tree) ，且該樹同時也是一棵 AVL 樹。 樹的節點在 C 語言中宣告如下：

並定義以下函式： 

找出以 root 為根的整棵樹中，所有鍵值大於 val 的節點裡，第 k 小的 節點，k 從 1 開始算。若第 k 小的節點不存在，則回傳 NULL。

(二)下圖為一棵包含 5 個節點且滿足 AVL 平衡特性的二元搜尋樹，圖中 顯示每個節點的鍵值。若將鍵值為 70 的新節點插入此樹，為保持 AVL 樹的平衡，會觸發旋轉。請畫出旋轉後的樹狀結構圖。除新插入的節 點 70 外，若原有節點的 size 欄位值在旋轉後發生改變，請在旋轉後 的圖中，於該節點旁標示其新的 size 欄位值。(5 分)