BST，尋找下一個最高點

在BST，根據暴露BST，尋找下一個最高點

編程訪談「給出一個節點，你甚至可以找到在澳下一個最高點（日誌（n））的時間」第65頁

BST中的節點將右子節點作爲下一個最高節點，那麼爲什麼O（log（n））？請更正

首先回答這個問題，然後否定它

來源

2014-01-08 codey modey

如果沒有合適的孩子會怎麼樣？ – Dukeling

根據你的下一個最高節點的含義是什麼？ –

可能是下一個更大/更大的節點。 – Dukeling

「在BST節點有右孩子爲下一個最高節點」（這裏假設「一級」是指下一個最大的值） - 不，這不是「T。那可以是沒有左節點的情況，但並不總是如此（參見下面的第1點）。

下一個最大的值（用這個詞，而不是「最高」，因爲後者可能與樹的高度相混淆）值來自於兩個地方：

首先，如果當前節點具有右子，然後移動到那個正確的孩子，只要你能看到一個左邊的孩子，移動到它。

換句話說（s和d源和目的地）：

S 
/\ 
x x <- This is the node your simple explanation chose, 
    /\ but it's the wrong one in this case. 
    x x 
/\ 
D x 
    \ 
    x

否則（當前節點沒有右孩子），你需要動起來，不斷父（所以節點需要一個右，左和父指針），直到你從移動的節點是一個左邊的孩子。如果你到達根目錄並且仍然有還沒有從左邊的孩子上移，那麼你的原始節點已經是樹中最高的了。圖形，這將是：

x \ D /\ x x \ x /\ x S / x

這種功能的僞代碼將是：

def getNextNode (node): if node.right != NULL: node = node.right while node.left != NULL: node = node.left return node while node.parent != NULL: if node.parent.left == node: return node.parent node = node.parent return NULL

由於努力是成正比的樹的高度，平衡樹（如紅黑，2-3-4和AVL）的時間複雜度爲O（log N），因爲高度與項目數有logN關係。本書在此討論平衡樹，因爲它包含了關於它們的片段：

此查找是一種快速操作，因爲您在每次迭代時都會從搜索中消除一半的節點。

查找是二叉搜索樹中的O（log（n））操作。

如果您可以保證在每次迭代中剩餘要搜索的節點數量將減半或減半，則查找僅爲O（log（n））。

所以，雖然它在這最後的報價，一個BST可能不均衡承認，在O（日誌N）的屬性是隻對那些變異體是。

對於非平衡樹，複雜性（最壞情況）會爲O（n），你可以用墮落樹木一樣結束了：

S D \ / x x \ \ x x \ \ x x \ \ x x / \ D S

來源

2014-01-08 08:58:59 paxdiablo

的副本以及它如何登錄（n）？ –

@ user2901020在平衡樹中，「深度」是O（log N）。在尋找下一個節點時，最多可以深入'深度'，然後最多深入'深度'時間 - 當相加時，導致O（log N）。 – JakubT

來實現它，你如何找到給定節點的父節點，沒有返回指針的權利？簡而言之，你能否給出一個想法，對於我來說，它是如何實現的，首先計算源節點的深度，然後計算它的父節點，然後檢查源節點是正確的還是左節點..我是越來越困惑，你能給我一個正確的方向嗎？ –

這是我在Java中實現僞。希望能幫助到你。節點的

結構

public Class Node{ 

int value {get, set}; 
Node leftChild {get,set}; 
Node rightChild{get, set}; 
Node parent{get,set}; 
}

功能找到下一個最高點

public Node findNextBiggest(Node n){ 
    Node temp=n; 
    if(n.getRightChild()==null) 
    { 
     while(n.getParent()!=null && temp.getValue()>n.getParent().getValue()) 
     { 
      n=n.getParent(): 
     } 
     return n.getParent(); 
    } 
    else 
    { 
     n=n.getRightChild(); 
     while (n.getLeftChild()!=null && n.getLeftChild().getValue()>temp.getValue()) 
     { 
      n=n.getLeftChild(); 
     } 
    return n; 
    } 
}

來源

2014-04-11 16:20:20 Bipin

我認爲，我們可以發現，只需找到該節點的序後繼下一個最高點。

步驟 -

首先，轉到節點的右子。
然後儘可能左移。當您到達葉節點時，打印該葉節點，因爲該節點與給定節點相比是下一個最高節點。

來源

2017-06-06 14:56:15

BST，尋找下一個最高點

回答

相關問題