數據結構樹複雜

Question

我有這個tree

我相信，這是一個最大堆的，我不知道，如果它是一個完整的樹，因爲在過程中注意到它說一當每個非離開節點有兩個孩子時，二叉樹是一棵滿樹。

Answer 1

Max-heap。你有一個例子，是的，你的樹是最大的堆。

此外，對於它是一棵完整的樹，每個級別都必須填充節點，例如在this示例中。你的樹是一棵完整的樹，但不是一棵完整的樹。希望這可以幫助。

要成爲binary search tree，它必須遵守一些規則。 例如，您有根，左和右兒童。

2 
1 3 

左樹（由這裏1個單個節點。製造）必須具有較低的值比所述根，和右樹（在此由1個單個節點。製造）必須具有比所述根更大的所有值。所以不，你的樹不是二叉搜索樹。

關於第二個問題（您應該發佈1個問題/帖子）...最壞的情況是O（n）如果樹不是二叉搜索樹。如果它是一個二叉查找樹，在最壞的情況下，如果您有一棵平衡樹，就會得到O（log n）！

如果你有一棵二叉樹，最壞的情況是O（n），因爲這個有效的binary search tree。

A balanced binary search tree針對不同類型的操作進行了優化。在一般樹中，取決於它的構建方式，最壞的情況是O（n）！ 「

Answer 2

」二進制堆是使用二叉樹創建的堆數據結構。「 - Wikipedia

二叉樹表示每個節點有2個子引用。

如果二叉樹中的每個節點沒有兩個子節點，那麼它不是一個完整的樹。

O(logn)用於搜索，因爲在每個節點處，您將數據集分爲兩半（因爲最多隻有兩個孩子），向左或向右搜索，直到找到葉子或正在搜索的數據。