詳解二叉查找樹(BST)

詳解二叉查找樹(BST)

本篇随筆簡單講解一下資料結構——二叉查找樹(\(Binary\,\,Sort\,\,Tree,BST\))，（後文的“二叉查找樹”一詞均用\(BST\)代替）。

BST的概念

首先，\(BST\)是一棵二叉樹。

它的定義是，根節點左子樹全部嚴格小于根節點，右子樹大于等于根節點，并且，左右子樹都是\(BST\)。

很好了解，很明朗很簡單的定義。

可以看出，這是一個通過遞歸方式定義的資料結構，是以，它的諸多操作自然要用到遞歸。

BST的功能

我們可以看出來，這個二叉查找樹就是把一個有序數列按照一個樹的方式排布了起來，說白了，就是一個以樹的方式存在的有序數列。把這個序列變成樹，友善我們在這個序列上進行對某一個值的查找，插入和删除。

我在學習\(BST\)的時候冒出了很多大膽的想法，在這裡也一并說一聲，讓讀者見笑了。

比如，我在想，如果對某一個值進行查找的話，二分的複雜度貌似也是log的樣子？

\(BST\)比它強，因為它還支援插入和删除，複雜度都是\(log\)級别的。

我又在想，那進行查找和删除，貌似連結清單也可以？

\(BST\)比它強，因為它的複雜度都是\(log\)級别的，而連結清單是\(O(n)\)的。

總之，記住\(BST\)的形态和功能，一個字，有用就完了(不是......

BST的操作

建樹

我們先來想一下，BST的建樹過程：

對于一組資料來講，我們要建BST的話，就直接按照定義遞歸建，與根節點判大小，大了往右走，小了往左走，直到一個空位置，就是它的位置了，插進去就可以。

但是這樣的話會有幾個問題。

首先，如果碰到一組單調的資料，BST瞬間變成鍊。

這個時候我們要麼用平衡樹對BST進行旋轉來維護BST的平衡，要麼用随機化算法把資料打亂。

如果有對打亂資料還懵圈的小可愛可以走這邊：

數組的随機打亂

其次，因為這個樹的形态未知，是以我們開多大空間也是未知的。

是以需要我們進行動态開點。

管于動态開點的講解與分析，會在以後在部落格上新，還不會的同志自學一下哦！

增加元素

增加元素的操作比較好想，就是從上面遞歸一層層找，找到對應位置插進去就可以。

删除元素

寫在後面