二元搜尋樹是什麼

二元搜尋樹又稱為二元尋找樹或二元排序樹，一棵二元搜尋樹是以二元樹來組織的，可以使用一個鍊錶資料結構來表示，其中每一個結點就是一個物件；一般地，除了key和衛星資料之外，每個結點還包含屬性lchild、rchild和parent。

二元查找樹（Binary Search Tree），（又：二元搜尋樹，二元排序樹）它或是一棵空樹，或者是具有下列性質的二元樹： 若它的左子樹不空，則左子樹上所有結點的值均小於它的根結點的值； 若它的右子樹不空，則右子樹上所有結點的值都大於它的根結點的值； 它的左、右子樹也分別為二元排序樹。二元搜尋樹作為一種經典的資料結構，它既有鍊錶的快速插入與刪除操作的特點，又有數組快速查找的優勢；所以應用十分廣泛，例如在文件系統和數據庫系統一般會採用這種資料結構進行高效率的排序與檢索操作。

原理

二元搜尋樹（BST）又稱二元找出樹或二元排序樹。一棵二元搜尋樹是以二元樹來組織的，可以使用一個鍊錶資料結構來表示，其中每一個結點就是一個物件。一般地，除了key和衛星資料之外，每個結點還包含屬性lchild、rchild和parent，分別指向結點的左孩子、右孩子和雙親（父結點）。如果某個孩子結點或父結點不存在，則對應屬性的值為空（NIL）。根結點是樹中唯一父指針為NIL的結點，而葉子結點的孩子結點指針也為NIL。

結構

二元搜尋樹是能夠有效率地進行以下操作的資料結構。

1.插入一個數值

2.查詢是否包含某個數值

#3.刪除某個數值 

以上是二元搜尋樹是什麼的詳細內容。更多資訊請關注PHP中文網其他相關文章！