二叉查找樹的特點是什么？

左子樹所有的節點都小于父節點，右子樹所有的節點都大于父節點。投影到平面以后，就是一個有序的線性表。

二叉查找樹既能夠實現快速查找，又能夠實現快速插入。

但是二叉查找樹有一個問題：

就是它的查找耗時是和這棵樹的深度相關的，在最壞的情況下時間復雜度會退化成O(n)。

什么情況是最壞的情況呢？

我們打開這樣一個網站來看一下，這里面有各種各樣的數據結構的動態演示，包括BST 二叉查找樹：

https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

還是剛才的這一批數字，如果我們插入的數據剛好是有序的，2、6、11、13、17、22。

這個時候我們的二叉查找樹變成了什么樣了呢？

它會變成鏈表（我們把這種樹叫做“斜樹”），這種情況下不能達到加快檢索速度的目的，和順序查找效率是沒有區別的。

造成它傾斜的原因是什么呢？

因為左右子樹深度差太大，這棵樹的左子樹根本沒有節點——也就是它不夠平衡。

所以，我們有沒有左右子樹深度相差不是那么大，更加平衡的樹呢？

這個就是平衡二叉樹，叫做Balanced binary search trees，或者AVL 樹（AVL 是發明這個數據結構的人的名字）。

?

總結

以上是生活随笔為你收集整理的二叉查找树（BST Binary Search Tree）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。