目前正在學習考試，並通讀一些筆記時，我有幾個問題。二叉樹問題
我知道二叉搜索樹的高度是Log（n）。這是否意味着深度也是Log（n）？
什麼是具有n個節點的完整二叉樹中節點的最大深度？這與第一個問題有關;如果二叉樹的高度是Log（n），那麼最大深度也是Log（n）？
我知道在二叉搜索樹中搜索節點的時間複雜度是O（Log（n）），據我所知。但是，我讀到最壞情況下的時間複雜度是O（N）。在什麼情況下需要O（N）時間才能找到一個元素？
這是一個優先隊列/堆問題。在我的講義中，它說以下語句：
如果我們使用優先隊列的數組，排隊需要O（1），排隊需要O（n）。在排序的數組中，en-queue需要O（N），並且取消隊列需要O（1）。
我很難理解這一點。誰能解釋一下？
對不起，所有的問題，真的需要一些這些主題的一些清晰。
警告：我是有點生疏，但在這裏不用...
高度和二叉樹的深度是同義 - 更多或更少。高度是沿着從根到葉的任何路徑的最大深度。但是，當你遍歷樹時，你有一個當前深度的概念。根節點的深度爲0，其子節點的深度爲1，其子孫的深度爲2.如果我們在這裏停止，樹的高度爲3，但是我們訪問的最大深度爲2，否則在談論時經常互換樹整體。
在我們談到更多問題之前，需要注意的是二叉樹有各種不同的風格。平衡或不平衡。使用完美平衡的樹，除最大高度以外的所有節點都將使其左/右鏈接非空。例如，在樹中有n個節點，令n = 1024。完美平衡的高度是10（例如1024 == 2^10）的log2（n）。
當你搜索一個完美的平衡樹，搜索爲 O（LOG 2（N）），因爲從根節點開始，你選擇跟隨左或右，並在每次做的時候，你消除1/2個節點。在這種有1024個元素的樹中，深度爲10，你做出10個這樣的左/右判定。
當您添加新節點時，大多數樹算法會即時重新平衡樹（例如AVL或RB（紅黑色））樹。所以，你總是或多或少地得到一棵完美平衡的樹。
但是...
讓我們考慮一個非常糟糕的算法。當你添加一個新節點時，它只會將它附加到最大深度的子節點上的左側鏈接[或新節點變成新的根節點]。這個想法是快速追加，並且「我們稍後會重新平衡」。
如果我們搜索這個「壞」樹，如果我們已經添加了n個節點，樹看起來像使用父鏈接和左鏈接的雙鏈表[記住所有正確的鏈接都是NULL]。這是線性時間搜索或O（n）。
我們故意這樣做了，但它仍然可以在某些樹算法和/或數據組合的情況下發生。也就是說，數據是自然放置在左側鏈接上的，因爲這是基於算法放置函數放置它的正確位置。
優先級隊列就像常規隊列一樣，除了每條數據都有一個與之相關的優先級號。
在一個普通的隊列中，你只需按下/追加到最後。當你離隊時，你從前面移動/彈出。你從來沒有需要在中間插入任何東西。因此，入隊和出隊都是O（1）操作。 O（n）來自這樣一個事實，即如果必須在數組中間插入一個數據，則必須「分開水域」爲要插入的元素留出空間。例如，如果您需要在第一個元素[array [0]]之後插入，則會將新元素放置在array [1]處，但首先必須將array [1]移動到array [2]，數組[2]到數組[3]，...對於n的數組，這是O（n）努力。
從數組中刪除元素時，它是相似的，但是相反。如果你想刪除數組[1]，你抓住它，那麼你必須通過數組[1] =數組[2]，數組[2] =數組[3]，「...」再次，O（n）操作。
在排序數組中，您只需彈出結尾。這是你想要的。因此O（1）。要添加元素，請將其插入正確的位置。如果你的數組是1,2,3,7,9,12,17並且你想添加6，那麼數組[4]就是新的值，你必須移動7,9,12,17作爲以上。
優先級隊列只是附加到數組，因此O（1）。但要找到正確的出列元素，可以掃描數組數組[0]，數組[1]，......記住給定優先級的第一個元素位置，如果您發現優先級更高，那麼您應該記住這一點。當你達到目的時，你知道你需要哪個元素，說它是j。現在你必須從數組中刪除j，並且如上所述的O（n）操作。
它比所有這些稍微複雜，但不是兩個多。
平衡二叉搜索樹的高度爲order log（N）（與深度相同，如果從頁面向下繪製樹）。然而，你所說的沒有說明樹是平衡的。不平衡樹是一個高度爲O（N）的列表，而不是O（logN）。時間複雜性也是如此。 當你對我說「完整的二叉樹」時，意味着你在高度爲M的平衡樹中有完全（2^M）-1的節點。這就是你的意思嗎？大多數時候，樹會有其他數量的節點，所以它不能「滿」。 – cliffordheath