[問題] 二元搜尋數找第k小元素,O(logn)時間完成

[supercygnus (......)]

開發平台(Platform): (Ex: VC++, GCC, Linux, ...) 

DEV C++
額外使用到的函數庫(Library Used): (Ex: OpenGL, ...) 


問題(Question)：

二元搜尋樹找第k小元素,O(logn)時間完成
大概知道是要用AVL樹
而且是要在節點加一些變數來記錄資訊(例如有幾個子節點,或是有幾個左/右子節點)

但是還是不知道要怎麼用程式實作出來
有人可以提示一下嗎~?
抑或是有其他方法

用中序追蹤出來可以辦得到,但是時間是O(n)


餵入的資料(Input)：


預期的正確結果(Expected Output)：


錯誤結果(Wrong Output)：


程式碼(Code)：(請善用置底文網頁, 記得排版) 

目前節點的結構是

struct TreeNode{
      TreeNode *left;
      TreeNode *right;
      int data;
      int bf;
      int leftnode;
      int rightnode;

       };


補充說明(Supplement)：




--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 111.246.201.24
→ devilphoenix:Have a look at CLRS "Augmented Data Structures"