如果我有了n不同的整數作爲其按鍵順序統計二元平衡的樹，我想寫功能find(x)返回的最小整數，是不是在樹上，並且大於x。在O(log(n))時間。失蹤人數
例如，如果樹中的密鑰是6,7,8,10,11,13,14，則find(6)=9,find(8)=9,find(10)=12,find(13)=15。
我想尋找在O(log(n))的max和x（標記）在O(log(n))索引那麼如果i_x=n-(m-x)那麼我可以簡單地返回max+1。
通過指數我指的是6,7,8,10,11,13,14 6指數爲0，10指數是3，例如...
但我有與其他案件的麻煩......
根據wikipedia，訂單統計樹支持日誌這兩個操作（n）時間：
首先獲取x的等級，並選擇x的優先級，直到你找到一個地方插入你缺少的元素。但是這是n * log（n）的最壞情況。
所以，相反，一旦你有x的排名，你做一種二進制搜索。基本思想是在樹中是否有數字x和y之間的空格。有一個空間，如果rank(x) - rank(y) != x - y。
一般情況是：當搜索區間[lo，hi]中的數字（lo和hi是樹中的排名，mid是中等排名）時，如果lo和mid之間存在空格，則搜索內部[lo，mid]，否則在[mid，hi]內搜索。 您將最終找到您尋求的號碼。
但是，此解決方案不會在log（n）時間運行，而是在log^2（n）中運行。這是我能想到的最好的解決方案。
編輯：
嗯，這是一個很難回答的問題，我改變主意了幾次。以下是我想出了：
我假設左節點擁有較低的價格和合適的節點擁有卓越的價值
的find(x)直覺：從根開始和下井樹幾乎像一個標準的二叉樹。如果我們想要去的分支不包含find(x)的解決方案，然後將其剪下。
我們去完成基本情況第一：
x在左子樹中的情況比較棘手，因爲它可能包含直到y-1的x，x + 1，x + 2，x + 3等，其中y是存儲在當前節點。在這種情況下，我們要在右子樹中搜索y + 1。但是，如果從x到y的所有數字都不在左子樹中（即存在間隙），那麼我們將在其中找到一個值，因此我們查看x的左子樹。
問題是：如何查找從x到y的序列是否存在於子樹中？
Python中的算法是這樣的：
def find(node, x):
if node == null:
return x
if node.data < x:
return find(node.right, x)
if node.data == x:
return find(node.right, x+1)
if is_full(...):
return find(node.right, node.data+1)
return find(node.left, x)
要獲得的最小值嚴格大於x這是不是在樹中，第一個電話是find(root, x+1)。如果您希望最大值大於或等於不在樹中的x，則第一個調用爲find(root, x)。 is_full方法檢查左側子樹是否包含從x到node.data-1的所有數字。
現在，以此爲出發點，我相信你可以自己找到一個合適的解決方案，使用的事實是每個子樹中包含的節點數存儲在子樹的根。
我遇到過類似的問題。
沒有限制發現超過一些x，只需找到BST中缺少的元素。
下面是我的答案，在O(lg(n))時間完成這個操作是完全可能的，假設樹幾乎是平衡的。您可能想要考慮證明隨機構建的BST的預期高度爲lg(n)給定n元素。我使用了一個更簡單的符號，O(h)其中h =樹的高度，所以現在兩件事情是分開的。
假設和/或要求：
(left_subtree + right_subtree + 1)的計數。
請原諒我的多個符號爲不等於（=/=和!= ）
另請注意，如果要在機器上編寫工作代碼，代碼可能會以更好的方式構造。
此外，我認爲，在這個時候，這是正確的。我嘗試了儘可能多的角落案例，並且總體來說很有效。即使有反例，我也不認爲修改代碼以適應特定情況將會很困難;但請評論反例，我很感興趣。
像平常一樣尋找x。然後從x執行Depth first style搜索，以便每個整數都是前一個的增量。如果它沒有，那麼你找到你的整數。 – Striker
@Striker但是對於具有'find（1）'的'1,2,3,4,5,6,7,9'，它將是'O（n）'，不是嗎？ – dan785317
對於最壞的情況是，它將是O（n）。 – Striker