回『進階班』
a322: 平衡二元樹(偽?)
標籤 : BST
通過比率 : 17人/19人 ( 89% ) [非即時]
評分方式：
Tolerant

最近更新 : 2020-11-20 20:23

內容

李氏子盤想對一些資料進行查詢

這些資料有些特殊，就是遞增的比率比較多

這個特性導致一般的二元搜尋樹的右側會比左邊多更多節點

造成搜尋上的效率低落

又電又電的李盤馬上就想到了AVL tree, RB tree, Treap, Spray tree, Ordered Vector tree之類的

但他太電了刻不出平衡二元樹

於是他在參考葦名流奧義之後想到

如果把分向左右節點的條件做一些調整就可以改善一些

以下是該樹的定義

  1. 若任意節點的左子樹不空，則左子樹上所有節點的值均小於它的根節點兩倍的值
  2. 若任意節點的右子樹不空，則右子樹上所有節點的值均大於或等於它的根節點兩倍的值
  3. 任意節點的左、右子樹也分別符合以上規則

現在請你幫他測試這種二元樹是不是如他所想的效率不錯

 

輸入說明

多個測資點，每個測資點單筆測資

第一行有一正整數 $n$ 代表資料數量

第二行有 $n$ 個不重複整數 $a_i$ ，為資料

第三行有 $m$ 個整數 $q_i$ 以EOF結束，為欲查詢的值

$1 \leq n \leq 10^5$

$1 \leq m \leq 10^2$

$ -10^9 \leq a_i, q_i \leq 10^9$

輸出說明

對於每個查詢 $q_i$

輸出從根節點至該節點途經每個節點的值

以空格隔開，每個查詢換行

範例輸入 
5
1 2 3 4 5
5 1 2 3 4
範例輸出 
1 2 4 5
1
1 2
1 2 3
1 2 4
測資資訊：
記憶體限制： 64 MB
公開 測資點#0 (20%): 1.0s , <1M
公開 測資點#1 (20%): 1.0s , <1M
公開 測資點#2 (20%): 1.0s , <1M
公開 測資點#3 (20%): 10.0s , <1M
公開 測資點#4 (20%): 10.0s , <1M
提示 ：

如有多個相同鍵值的節點，只需印出至最先遇到的節點

標籤:
BST
出處:
108學年度進階班下學期期初複習考考題 [管理者：
fdhs107_KonChin... (konchin)
]

本題狀況 本題討論 排行

編號 身分 題目 主題 人氣 發表日期
沒有發現任何「解題報告」