最近一段時間，一時興起，重新刷了leetcode，順便重新溫習二叉搜索樹相關(guān)的知識，對它的理解更上一層樓。二叉搜索樹是非常優(yōu)雅的數(shù)據(jù)結(jié)構(gòu)，有非常出色的時間復雜度，而且應用也非常廣泛！

每種數(shù)據(jù)結(jié)構(gòu)都有它獨特的特性。跟數(shù)組和鏈表相比， 二叉搜索樹的優(yōu)勢在哪里？?那么二叉搜索樹的用途是什么？?最后一個比較深刻的問題： 二叉搜索樹的本質(zhì)是什么？?

要回答這個問題， 我們先看看數(shù)組、鏈表、二叉搜索樹有哪些特性，以及它們的比較。

下面， 考慮一個場景：?

一組已順序排序的整數(shù)序列， 分別用 數(shù)組， 鏈表， 二叉搜索樹 存儲， get, insert, delete 操作的時間復雜度分別是多少。

現(xiàn)在定義如下函數(shù)：

get（int value);

insert(int value);// 插入一個值，整數(shù)序列仍然是順序排序?

delete(int value);// 刪除一個值，整數(shù)序列仍然是順序排序?

不同的存儲結(jié)構(gòu)，時間復雜度分別如下：

數(shù)組：時間復雜度O(log2n), insert時間復雜度O(n),delete時間復雜度O(n)

鏈表：get時間復雜度O(n), insert時間復雜度O(n),delete時間復雜度O(n)?

二叉搜索樹：get時間復雜度O(log2n), insert時間復雜度O(log2n),delete時間復雜度O(log2n)（這里有一個前提：該二叉搜索樹是平衡的）

對于順序序列的數(shù)據(jù)操作，?二叉搜索樹簡直吊打數(shù)組和鏈表。?

但是仔細分析，其實二叉搜索樹是數(shù)組和鏈表的集大成者， 吸收其精華！

數(shù)組最大的特性是連續(xù)存儲， 基于這個特性， 可以利用二分查找， 使get復雜度為O(log2n)。 而二叉搜索樹的get操作從本質(zhì)上來說也是二分查找， 從這一點來說和數(shù)組的二分查找有異曲同工之妙！

而二叉搜索樹利用了鏈表的特性（已知一個節(jié)點，insert和delete的時間復雜度為O(1)）， 使得insert和delete時間復雜度都為O(log2n)。

所以， 二叉搜索樹的本質(zhì)是： 集成了數(shù)組和鏈表的優(yōu)勢， 是一種藝術(shù)的平衡！

正是因為二叉搜索樹有太優(yōu)秀的時間復雜度， 具有廣泛的應用。 如：基于二叉樹的紅黑樹和AVL樹，在操作系統(tǒng)， 數(shù)據(jù)庫等領(lǐng)域有廣泛的應用。

如有錯誤，煩請批評指正，不勝感激！轉(zhuǎn)載請明確標注轉(zhuǎn)載并附上文章具體網(wǎng)址，謝謝！