有根樹和二叉樹

有根樹

有根樹G是一個連通的無環圖，它有一個特殊的節點稱為樹的根，並且每條邊都直接或間接地起源於根。有序有根樹是有根樹，其中每個內部頂點的子節點是有序的。如果一個有根樹的每個內部頂點最多有m個子節點，則稱之為m叉樹。如果一個有根樹的每個內部頂點恰好有m個子節點，則稱之為完全m叉樹。如果m = 2，則有根樹稱為二叉樹。

二叉搜尋樹

二叉搜尋樹是一種滿足以下性質的二叉樹：

頂點V的左子樹中的X，Value(X) ≤ Value(V)
頂點V的右子樹中的Y，Value(Y) ≥ Value(V)

因此，內部節點V的左子樹的所有頂點的值都小於或等於V，內部節點V的右子樹的所有頂點的值都大於或等於V。從根節點到最深節點的連結數是二叉搜尋樹的高度。

示例

在BST中搜索鍵的演算法

BST_Search(x, k)
if ( x = NIL or k = Value[x] )
   return x;
if ( k < Value[x])
   return BST_Search (left[x], k);
else
   return BST_Search (right[x], k)

二叉搜尋樹的複雜度

	平均情況	最壞情況
空間複雜度	O(n)	O(n)
搜尋複雜度	O(log n)	O(n)
插入複雜度	O(log n)	O(n)
刪除複雜度	O(log n)	O(n)

Mahesh Parahar

更新於：2019年8月26日

4K+ 次瀏覽

開啟你的職業生涯

完成課程獲得認證

開始學習