演算法詳解資料結構與演算法：二叉搜尋樹

今天一起說說二叉搜尋樹【新增和比較】。

（一）思考

① 常規方式

在 n個動態的整數中搜索某個整數？檢視其是否存在。假設使用動態陣列存放元素，從第0個元素開始遍歷搜尋，平均時間複雜度：O（n）

② 二分搜尋的方式

如果是維護一個有序的動態陣列，使用二分搜尋，最壞時間複雜度是：O（logn）但是新增和刪除的時間複雜度是O（n），如果要找的元素是20，先找到這個動態陣列長度是10，從0開始，找到第5個位置，看看第5個位置是45，直接找前面的，後面就不管了，現在動態陣列的長度變成了5，然後在從剩餘的5個裡面在減半，對比左右的數字，20和28，就找到了20的位置。

針對這個需求，有沒有更好的方案？

使用二叉搜尋樹，新增、刪除、搜尋的最壞時間複雜度均可最佳化至：O（logn）

（二）二叉搜尋樹

① 介紹

二叉搜尋樹是二叉樹的一種，是應用非常廣泛的一種二叉樹，英文簡稱為BST。

又稱為： 二叉查詢樹，二叉排序樹。

任意一個節點的值都大於其左子樹所有節點的值。3這個大於1，，6大於4。

任意一個節點的值都小於其右子樹所有節點的值。8小於右子樹所有節點。

它的左右子樹也是一顆二叉搜尋樹。

② 二叉搜尋樹可以大大提高搜尋資料的效率

③ 二叉搜尋樹儲存的元素必須具備比較性

比如：int、double 等。

如果是自定義型別，需要指定比較方式。

④ 二叉搜尋樹的介面設計

⑤ 需要注意的是

二叉樹來說，它的元素沒有索引的概念

（三） 程式碼實現

① 先了解新增add的程式碼實現

新增一個元素的時候，先確定他的位置，二叉搜尋樹有自己的規則，需要從上往下找，根據大小往左還是往右找，上面每一個都成為節點，上面每個都儲存到節點上。

為了方便需要維護一個節點類。left左節點，right右節點，parent父節點，

建立一個節點，必然是有父節點的，左子節點，右子節點不一定有，如果新增的本身就是葉子節點肯定本身就是沒有的，既然左右都沒有left，right可以為空。

在新增之前，判斷節點是否為空

新增第一個節點

新增節點

新增12，1

新增步驟

找到父節點 parent

建立新節點node

parent。lef = node 或者 parent。right = node

遇到值相等的元素該如何處理。

建議覆蓋舊的值

如果當前傳入的節點大於當前的節點，取右節點。

如果當前傳入的節點小於當前的節點，取左節點。

需要拿到當前節點的葉子節點來進行比較。

② 比較邏輯

引入jdk的jar包，Comparator。

方便的方式定義一個構造方法，可以選擇性的傳入比較器

定義一個比較規則，可以在使用的對應的實體類中使用這種比較規則

③ 完整原始碼

PS：本節主要說說 新增和比較方法，完整程式碼內容比較多。詳細的品品程式碼，有啥疑問歡迎留言

Java零基礎入門

米粒教育

購買專欄