資料結構及演算法

Please design an $O(\log n)$ algorithm to search for the $k$-th element in an AVL tree of $n$ elements, while the time complexity of insertion operation remains $O(\log n)$.

(1) (5%) How to modify the data structure of an AVL tree to support this search operation?

(2) (10%) Give the $O(\log n)$ algorithm to search for the k-element.

(3) (5%) How to modify the insertion operation to accommodate for the modification of the data structure.

(Please illustrate your answer by using the AVL-tree provided in Figure 2.)

Figure 2 (AVL tree): root $54$; left child $23$, right child $79$; $23$'s children are $11$ (left) and $45$ (right); $79$'s children are $66$ (left) and $88$ (right); $45$'s left child is $36$.