二叉樹與二叉搜尋樹的區別

排序是將資料按邏輯順序排列的過程，以便能夠以最有效的方式進行分析。搜尋是在資料庫中查詢特定記錄的操作。如果資料以預定的方式正確組織，則搜尋過程將變得簡單且節省時間。本文的主題是樹，它是非線性資料結構最重要的例子之一。

使用樹來表示資料的主要目的是說明被表示結構的各個元件之間的層次關係。例如，目錄和家譜。

從更技術的角度來看，樹可以定義為一個稱為“T”的有限集合，它包含一個或多個節點。在這個集合中，一個節點被指定為樹的“根”，其餘節點被劃分為 $"n\geq{0}"$ 個不相交的集合，稱為 $"T_{1},T_{2},T_{3},....T_{n}"$ 這些子樹被稱為根節點的“子節點”。

什麼是二叉樹？

這是一種非線性資料結構，其中每個元素最多可以有兩個、一個或零個節點。此樹中的每個節點都可以充當父節點或子節點。位於樹頂部的節點稱為根節點。每個父節點最多可以有兩個子節點（子節點）。在這種情況下，我們通常分別將其稱為左子節點/子節點和右子節點/子節點。

構成二叉樹的每個節點都由三個欄位組成：

這就是多個節點組合形成二叉樹的方式。

以下術語在與二叉樹相關的上下文中經常使用：

這些是與二叉樹相關的一些基本術語。現在您已經對二叉樹有了基本的瞭解，是時候繼續學習二叉樹的下一階段，即二叉搜尋樹。

二叉搜尋樹是一種基於節點的、非線性的資料結構型別，它派生自二叉樹。它也縮寫為 BST。資料檢索、分類和分析都可以藉助它的幫助來完成。由於它的節點以特定的順序排列，因此該結構的另一個名稱是有序二叉樹。

BST 將具有以下特徵：

下表重點介紹了二叉樹和二叉搜尋樹之間的主要區別：

比較依據	二叉樹	二叉搜尋樹
定義	二叉樹是一種非線性資料結構，其中每個節點最多可以有兩個子節點。	BST 是一種二叉樹，其節點具有也是二叉搜尋樹的右子樹和左子樹。
型別	完全二叉樹滿二叉樹擴充套件二叉樹	AVL 樹伸展樹 Tango 樹 T 樹
操作	由於二叉樹是無序的，因此插入、刪除和查詢它們的過程需要花費更多時間。	由於其有序特性，在 BST 中插入、刪除和搜尋元素的速度比在二叉樹中更快。
結構	在二叉樹中，節點的排列方式沒有順序。	在 BST 中，左子樹包含小於節點元素的元素，而右子樹包含大於節點元素的元素。
資料表示	資料表示以分層結構的形式執行。	資料表示以有序格式完成。
重複值	二叉樹允許重複值。	二叉搜尋樹不允許重複值。
速度	由於它是無序的，因此在二叉樹中刪除、插入和搜尋操作的速度比在二叉搜尋樹中慢。	由於它具有有序屬性，因此二叉搜尋樹執行元素刪除、插入和搜尋的速度更快。
複雜度	通常，時間複雜度為“O(n)”。	通常，時間複雜度為“O(log n)”。
應用	它用於快速有效地查詢資料和獲取資訊。	它擅長刪除元素、插入新元素和搜尋專案。
用法	它作為開發各種二叉樹結構的基礎，例如滿二叉樹、BST 和完美二叉樹等。	它用於實施平衡二叉搜尋樹，例如 AVL 樹、紅黑樹和其他類似結構。

這兩種模型都模擬了一個具有節點集合的層次樹結構，每個節點代表一個值；但是，它們在實踐方式和使用方式上存在很大差異。

二叉樹遵循每個父節點最多隻能有兩個子節點的規則，而二叉搜尋樹只是二叉樹的一種變體，它遵循相對順序來確定樹中節點的結構方式。

Pradeep Kumar

更新於：2022年7月22日

14K+ 次瀏覽

完成課程獲得認證