在二叉搜索樹中搜索數字。如果它不存在，找到最大的數字比它小

Question

假設你有一個平衡的二叉搜索樹（說AVL樹）與n個數字。

您需要一個查找給定數字x的算法，但如果找不到它， 將返回小於x的最大數字。

爲了這個問題，不插入x然後刪除它，解決方案應該是O（log（n））。

由於

Answer 1

這個問題是關於查找（虛擬地）插入的節點的中序前身。我將首先解釋Inorder Predecessor是什麼，然後解釋我們如何在BST中找到Inorder Predecessor。

在我們談論Inorder Predecessor之前，我們必須先熟悉二叉搜索樹的Inorder遍歷。 中序遍歷算法訪問二叉搜索樹中的所有節點按照特定的順序如下遞歸算法概述：

Inorder(Node S) 
    Inorder(left child of S) 
    print S 
    Inorder(right child of S) 

在平原的話，我們遞歸打印左側的樹，然後中心節點，然後是右子樹。

該算法非常簡單但優雅，因爲按照此順序打印按鍵時，由於BST結構中的按鍵排序，我們將獲得特殊的按鍵序列。那個特殊的序列是什麼？讓我們跟蹤BST的算法並檢查它。

讓我們考慮如下所示的BST：

在這裏，讓我們來跟蹤我們的算法，我們首先啓動算法在根目錄（與值20點），然後根據算法說，我們遞歸調用對於左子樹（即以節點8爲根的子樹）的相同函數，並且我們再次調用8的左子樹，即節點4.此時，4沒有左子樹，因此我們打印了密鑰4。由於4沒有右子樹，所以我們完成了以節點4爲根的子樹，並且我們回溯到節點8.現在我們打印節點8.然後，我們稱節點8右子樹的遞歸函數爲ALGO一步一步，你會意識到，打印的順序是：4，8，10，12，14，20，22

這個序列是什麼？這只是按鍵的排序順序。

這是怎麼回事？那麼，這只是BST節點結構的方式：BST具有一個特殊屬性，即對於每個節點S，節點S左側的所有密鑰都小於S，並且S右側的所有節點都大於S.

換句話說，Inorder遍歷只是按排序順序打印出二叉搜索樹的鍵。

好的，現在我們已經理解了打印BST的Inorder遍歷的遞歸算法，我們將重點放在尋找節點的任務上，該節點將是比我們的目標節點更小的最大節點。這個節點是什麼？它只是在我們的虛擬插入節點之前打印的節點，它位於BST的Inorder遍歷中。這被稱爲Inorder Predecessor。

讓我們回頭看看我們的BST，並瞭解Inorder Predecessor是什麼。

這裏是什麼12的中序前身？我們做什麼？我們知道節點的Inorder Predecessor是在Inorder遍歷中打印此節點之前打印的節點。這可以是哪個節點？爲了回答這個問題，我們必須可視化我們的節點12將被打印的確切時間點。顯然，通過Inorder遍歷算法在特定節點之前打印的東西，應該是某個節點的打印步驟已經完成。在這種情況下，對於節點12，我們看到在步驟12的打印步驟之前立即進行遞歸打印12的左側子節點的調用。 12歲的孩子是什麼？它是10.顯然，10是Inorder遍歷中12之前打印的節點。因此，10是12的Inorder Predecessor。

通常，很容易看出如果一個節點有一個左子樹，那麼節點的Inorder Precedessor就是它左子樹中的最大節點。

但是如果節點沒有左子樹呢？說，節點10的Inorder Predecessor是什麼？我們如何找到這個？

好吧，這有點棘手，因爲10沒有左子樹。讓我們想想，哪個節點可以在節點10之前打印？我們正在尋找一個已經打印好的節點。首先，我們是如何到達遍歷算法序列中的節點10的？我們來自節點12左邊，Inorder Predecessor可以是12嗎？不，因爲根據算法，節點12將僅在10之後被打印，因爲通過對節點12的左子樹的遞歸調用來打印10。好的，什麼叫12？ 8將遞歸調用調用爲12，作爲其遞歸調用其右子樹的一部分。好的，可以成爲Inorder Predecessor嗎？首先我們已經打印了8張？是的，我們已經打印了8個，因爲我們現在已經在8個右側的子樹中。 8實際上是在Inorder遍歷中的節點10之前打印的節點。爲什麼？我們剛剛做了什麼？我們所做的只是回顧我們如何在節點10處結束，回溯步驟並查看已經打印的第一個節點。顯然，這是Inorder Predecessor。因此8是Inorder Predecessor爲10.

一般來說，很容易看出如果一個節點沒有左子樹，你所需要做的就是從你的節點上去樹根，並且這樣做，找到它的父節點的正確子節點，然後父節點就是Inorder Predecessor。因此，找到一個節點的Inorder Predecessor所需要做的就是追溯遍歷中如何到達節點的遞歸調用。

總結： 如果節點有一個左子樹，則Inorder Predecessor是節點左子樹中的最大密鑰。 Else 直到找到一個節點，它是它的父節點的正確子節點，那麼父節點將是Inorder Predecessor。

現在，我們瞭解Inorder Predecessor是什麼以及如何在BST中找出它，讓我們回到我們的任務。由於我們的節點並不存在，所以我們將它插入（實際上是atleast），這意味着它將是插入的葉子，這意味着它不會有左子樹，這意味着它的前驅實際上只是向上那個樹。所以，在一次遍歷中，你應該能夠完成這個任務，而不需要實際插入。