在Java中實現(xiàn)二叉搜索樹的全過程記錄
二叉搜索樹
二叉搜索樹結(jié)合了無序鏈表插入便捷和有序數(shù)組二分查找快速的特點,較為高效地實現(xiàn)了有序符號表。下圖顯示了二叉搜索樹的結(jié)構(gòu)特點(圖片來自《算法第四版》):
可以看到每個父節(jié)點下都可以連著兩個子節(jié)點,鍵寫在節(jié)點上,其中左邊的子節(jié)點的鍵小于父節(jié)點的鍵,右節(jié)點的鍵大于父節(jié)點的鍵。每個父節(jié)點及其后代節(jié)點組成了一顆子樹,根節(jié)點及其后代節(jié)點則組成了完整的二叉搜索樹。
在代碼層面看來,就是每個節(jié)點對象中包含另外兩個子節(jié)點的指針,同時包含一些要用到的數(shù)據(jù),比如鍵值對和方便后續(xù)操作的整課子樹的節(jié)點數(shù)量。
private class Node { int N = 1; K key; V value; Node left; Node right; public Node(K key, V value) { this.key = key; this.value = value; } }
上述代碼實現(xiàn)了一個節(jié)點類,這個類是二叉搜索樹類 BinarySearchTree 的內(nèi)部類,使用者無需知道這個節(jié)點類的存在,所以訪問權(quán)限聲明為 private。
有序符號表的 API
先來看下無序符號表的 API,這些方法聲明了無序符號表的基本操作,包括插入、查詢和刪除,為了方便符號表的迭代,接口中還有 Iterable<K> keys() 方法用于 foreach 循環(huán):
package com.zhiyiyo.collection.symboltable; public interface SymbolTable<K, V>{ void put(K key, V value); V get(K key); void delete(K key); boolean contains(K key); boolean isEmpty(); int size(); Iterable<K> keys(); }
接下來是有序符號表的 API,其中每個節(jié)點的鍵必須實現(xiàn)了 Comparable 接口:
package com.zhiyiyo.collection.symboltable; public interface OrderedSymbolTable<K extends Comparable<K>, V> extends SymbolTable<K, V>{ /** * 獲取符號表中最小的鍵 * @return 最小的鍵 */ K min(); /** * 獲取符號表中最大的鍵 * @return 最大的鍵 */ K max(); /** * 獲取小于或等于 key 的最大鍵 * @param key 鍵 * @return 小于或等于 key 的最大鍵 */ K floor(K key); /** * 獲取大于或等于 key 的最小鍵 * @param key 鍵 * @return 大于或等于 key 的最小鍵 */ K ceiling(K key); /** * 獲取小于或等于 key 的鍵數(shù)量 * @param key 鍵 * @return 小于或等于 key 的鍵數(shù)量 */ int rank(K key); /** * 獲取排名為 k 的鍵,k 的取值范圍為 [0, N-1] * @param k 排名 * @return 排名為 k 的鍵 */ K select(int k); /** * 刪除最小的鍵 */ void deleteMin(); /** * 刪除最大的鍵 */ void deleteMax(); /** * [low, high] 區(qū)間內(nèi)的鍵數(shù)量 * @param low 最小的鍵 * @param high 最大的鍵 * @return 鍵數(shù)量 */ int size(K low, K high); /** * [low, high] 區(qū)間內(nèi)的所有鍵,升序排列 * @param low 最小的鍵 * @param high 最大的鍵 * @return 區(qū)間內(nèi)的鍵 */ Iterable<K> keys(K low, K high); }
實現(xiàn)二叉搜索樹
二叉搜索樹類
類的基本結(jié)構(gòu)如下述代碼所示,可以看到只需用一個根節(jié)點 root 即可代表一整棵二叉搜索樹:
public class BinarySearchTree<K extends Comparable<K>, V> implements OrderedSymbolTable<K, V> { private Node root; private class Node{ ... } ... }
查找
從根節(jié)點出發(fā),拿著給定的鍵 key 和根節(jié)點的鍵進行比較,會出現(xiàn)以下三種情況:
- 根節(jié)點的鍵大于 key,接著去根節(jié)點的左子樹去查找;
- 根節(jié)點的鍵小于 key,接著去根節(jié)點的右子樹去查找;
- 根節(jié)點的鍵等于 key,返回根節(jié)點的值
當我們?nèi)プ笞訕浠蛘哂易訕洳檎視r,只需將子樹的根節(jié)點視為新的根節(jié)點,然后重復(fù)上述步驟即可。如果找到最后都沒找到擁有和 key 相等的鍵的節(jié)點,返回 null 即可。在《算法第四版》中使用遞歸實現(xiàn)了上述步驟,這里換為迭代法:
@Override public V get(K key) { Node node = root; while (node != null) { int cmp = node.key.compareTo(key); // 到左子樹搜索 if (cmp > 0) { node = node.left; } // 到右子樹搜索 else if (cmp < 0) { node = node.right; } else { return node.value; } } return null; }
插入
將鍵值對放入二叉搜索樹時會發(fā)生兩種情況:
- 二叉搜索樹中已經(jīng)包含了擁有該鍵的節(jié)點,這時需要更新節(jié)點的值
- 二叉搜索樹中沒有包含擁有該鍵的節(jié)點,這時需要創(chuàng)建一個新的節(jié)點
所以在插入的時候要從根節(jié)點出發(fā),比較根節(jié)點的鍵和給定的 key 之間的大小關(guān)系,和查找相似,比較會有三種情況發(fā)生:
- 根節(jié)點的鍵大于 key,接著去根節(jié)點的左子樹去查找;
- 根節(jié)點的鍵小于 key,接著去根節(jié)點的右子樹去查找;
- 根節(jié)點的鍵等于 key,直接更新根節(jié)點的值
如果找到最后都沒能找到那個擁有相同 key 的節(jié)點,就需要創(chuàng)建一個新的節(jié)點,把這個節(jié)點,接到子樹的根節(jié)點上,用迭代法實現(xiàn)上述過程的代碼如下所示:
@Override public put(K key, V value){ if (root == null) { root = new Node(key, value); return; } Node node = root; Node parent = root; int cmp = 0; while (node != null){ parent = node; cmp = node.key.compareTo(key); // 到左子樹搜索 if (cmp > 0){ node = node.left; } // 到右子樹搜索 else if (cmp < 0){ node = node.right; } else { node.value = value; return; } } // 新建節(jié)點并接到父節(jié)點上 if (cmp > 0) { parent.left = new Node(key, value); } else{ parent.right = new Node(key, value); } }
可以看到上述過程用了兩個指針,一個指針 node 用于探路,一個指針 parent 用于記錄子樹的根節(jié)點,不然當 node 為空時我們是找不到他的父節(jié)點的,也就沒法把新的節(jié)點接到父節(jié)點上。
上述代碼有個小問題,就是我們新建節(jié)點之后沒辦法更新這一路上所經(jīng)過的父節(jié)點的 N,也就是每一顆子樹的節(jié)點數(shù)。怎么辦呢,要么用一個容器保存一下經(jīng)過的父節(jié)點,要么老老實實用遞歸,這里選擇用遞歸。遞歸的想法很直接:
- 如果根節(jié)點的鍵大于 key,就把鍵值對插到根節(jié)點的左子樹;
- 如果根節(jié)點的鍵小于 key,就把鍵值對插到根節(jié)點的右子樹;
- 如果根節(jié)點的鍵等于 key,直接更新根節(jié)點的值
別忘了,使用遞歸的原因是我們要更新父節(jié)點的 N,所以遞歸的返回值應(yīng)該是更新后的子樹根節(jié)點,所以就有了下述代碼:
@Override public void put(K key, V value) { root = put(root, key, value); } private Node put(Node node, K key, V value) { if (node == null) return new Node(key, value); int cmp = node.key.compareTo(key); if (cmp > 0) { node.left = put(node.left, key, value); } else if (cmp < 0) { node.right = put(node.right, key, value); } else { node.value = value; } node.N = size(node.left) + size(node.right) + 1; return node; } private int size(Node node) { return node == null ? 0 : node.N; }
最小/大的鍵
從根節(jié)點出發(fā),一路向左,鍵會是一個遞減的序列,當我們走到整棵樹的最左邊,也就是 left 為 null 的那個節(jié)點時,我們就已經(jīng)找到了鍵最小的節(jié)點。上述過程的迭代法代碼如下:
@Override public K min() { if (root == null) { return null; } Node node = root; while (node.left != null) { node = node.left; } return node.key; }
查找最大鍵的節(jié)點過程和上述過程類似,只是我們這次得向右走,直到找到 right 為 null 的那個節(jié)點:
@Override public K max() { if (root == null) { return null; } Node node = root; while (node.right != null) { node = node.right; } return node.key; }
算法書中給出的 min() 實現(xiàn)代碼是用遞歸實現(xiàn)的,因為在刪除節(jié)點時會用到。遞歸的過程就是一直朝左子樹走的的過程,直到遇到一個節(jié)點沒有左子樹為止,然后返回該節(jié)點即可。
@Override public K min() { if (root == null) { return null; } return min(root).key; } private Node min(Node node) { if (node.left == null) return node; return min(node.left); }
小于等于 key 的最大鍵/大于等于 key 的最小鍵
從根節(jié)點出發(fā),拿著根節(jié)點的的鍵和 key 進行比較,會出現(xiàn)三種情況:
- 如果根節(jié)點的鍵大于 key,說明擁有小于或等于 key 的鍵的節(jié)點可能在左子樹上(也可能找不到);
- 如果根節(jié)點的鍵小于 key,這時候先記住根節(jié)點,由于根節(jié)點的右子樹上可能存在鍵更接近但不大于 key 的節(jié)點,所以還得去右子樹看看,如果右子樹沒沒找到滿足條件的節(jié)點,這時候的根節(jié)點的鍵就是小于等于 key 的最大鍵了;
- 如果根節(jié)點的鍵等于 key,直接返回根節(jié)點的鍵
@Override public K floor(K key) { if (root == null) { return null; } Node node = root; Node candidate = root; while (node != null) { int cmp = node.key.compareTo(key); if (cmp > 0) { node = node.left; } else if (cmp < 0) { candidate = node; node = node.right; } else { return node.key; } } return candidate.key.compareTo(key) <= 0 ? candidate.key : null; }
《算法第四版》中給出了一個示例圖,可以更直觀地看到上述查找過程:
查找大于等于 key 的最小鍵的方法和上述過程很像,拿著根節(jié)點的的鍵和 key 進行比較,會出現(xiàn)三種情況:
- 如果根節(jié)點的鍵小于 key,說明擁有大于或等于 key 的鍵的節(jié)點可能在右子樹上(也可能找不到);
- 如果根節(jié)點的鍵大于 key,這時候先記住根節(jié)點,由于根節(jié)點的左子樹上可能存在鍵更接近但不小于 key 的節(jié)點,所以還得去左子樹看看,如果左子樹沒沒找到滿足條件的節(jié)點,這時候的根節(jié)點的鍵就是大于等于 key 的最小鍵了;
- 如果根節(jié)點的鍵等于 key,直接返回根節(jié)點的鍵
@Override public K ceiling(K key) { if (root == null) { return null; } Node node = root; Node candidate = root; while (node != null) { int cmp = node.key.compareTo(key); if (cmp < 0) { node = node.right; } else if (cmp > 0) { candidate = node; node = node.left; } else { return node.key; } } return candidate.key.compareTo(key) >= 0 ? candidate.key : null; }
根據(jù)排名獲得鍵
假設(shè)一棵二叉搜索樹中有 N 個節(jié)點,那么節(jié)點的鍵排名區(qū)間就是 [0, N-1],也就是說,key 的排名可以看做小于 key 的鍵的個數(shù)。所以我們應(yīng)該如何根據(jù)排名獲得其對應(yīng)的鍵呢?這時候每個節(jié)點中的維護的 N 屬性就可以派上用場了。
從根節(jié)點向左看,左子樹的節(jié)點數(shù)就是小于根節(jié)點鍵的鍵個數(shù),也就是根節(jié)點的鍵排名。所以拿著根節(jié)點的左子樹節(jié)點數(shù) N 和排名 k 進行比較,會出現(xiàn)三種情況:
- 左子樹的節(jié)點數(shù)和排名相等,直接返回根節(jié)點的鍵;
- 左子樹的節(jié)點數(shù)大于排名,這時候去左子樹接著進行比較;
- 左子樹的節(jié)點數(shù)小于排名,說明符合排名要求的節(jié)點可能出現(xiàn)在右子樹上(有可能找不到,比如 k 大于整棵二叉樹的節(jié)點數(shù)),這時候我們得去右子樹搜索。由于我們直接忽略了左子樹和根節(jié)點,所以需要對排名進行一下調(diào)整,讓
k = k - N - 1
即可。
@Override public K select(int k) { Node node = root; while (node != null) { // 父節(jié)點左子樹的大小就是父節(jié)點的鍵排名 int N = size(node.left); if (N > k) { node = node.left; } else if (N < k) { node = node.right; k = k - N - 1; } else { return node.key; } } return null; }
根據(jù)鍵獲取排名
把根據(jù)排名獲取鍵的過程寫作key = select(k),那么根據(jù)鍵獲取排名的過程就是k = select-1(key) = rank(key)。說明這兩個函數(shù)互為反函數(shù)。
從根節(jié)點出發(fā),拿著根節(jié)點的鍵和 key 進行比較會出現(xiàn)三種情況:
- 根節(jié)點的鍵大于 key,這時候得去左子樹中尋找
- 根節(jié)點的鍵小于 key,這時候得去右子樹中尋找,同時得記錄一下左子樹節(jié)點數(shù)+父節(jié)點的那個1
- 根節(jié)點的鍵等于 key,返回根節(jié)點的左子樹節(jié)點數(shù)加上之前跳過的節(jié)點數(shù)
@Override public int rank(K key) { Node node = root; int N = 0; while (node != null) { int cmp = node.key.compareTo(key); if (cmp > 0) { node = node.left; } else if (cmp < 0) { N += size(node.left) + 1; node = node.right; } else { return size(node.left) + N; } } return N; }
刪除
刪除操作較為復(fù)雜,先來看下較為簡單的刪除鍵最小的節(jié)點的過程。從根節(jié)點出發(fā),一路向左,知道遇到左子樹為 null 的節(jié)點,由于這個節(jié)點可能還有右子樹,所以需要把右子樹接到父節(jié)點上。接完之后還得把這一路上遇到的父節(jié)點上的 N - 1。由于沒有其他節(jié)點引用了被刪除的節(jié)點,所以這個節(jié)點會被 java 的垃圾回收機制自動回收。算法書中給出了一個刪除的示例圖:
使用迭代法可以實現(xiàn)尋找最小節(jié)點和將右子樹連接到父節(jié)點的操作,但是不好處理每一顆子樹的 N 的更新操作,所以還是得靠遞歸法。由于我們需要將最小節(jié)點的右子樹接到父節(jié)點上,所以滿足終止條件時 deleteMin(Node node)
函數(shù)應(yīng)該把右子樹的根節(jié)點返回,否則就應(yīng)該返回更新之后的節(jié)點。
@Override public void deleteMin() { if (root == null) return; root = deleteMin(root); } private Node deleteMin(Node node) { if (node.left == null) return node.right; node.left = deleteMin(node.left); node.N = size(node.left) + size(node.right) + 1; return node; }
刪除最大的節(jié)點的過程和上面相似,只不過我們應(yīng)該將最大節(jié)點的左子樹接到父節(jié)點上。
@Override public void deleteMax() { if (root == null) return; root = deleteMax(root); } private Node deleteMax(Node node) { if (node.right == null) return node.left; node.right = deleteMax(node.right); node.N = size(node.left) + size(node.right) + 1; return node; }
討論完上面兩個較為簡單的刪除操作,我們來看下如何刪除任意節(jié)點。從根節(jié)點出發(fā),通過比較根節(jié)點的鍵和給定的 key,會發(fā)生三種情況:
根節(jié)點的鍵大于 key,接著去左子樹刪除 key
根節(jié)點的鍵小于 key,接著去右子樹刪除 key
根節(jié)點的鍵等于 key ,說明我們找到了要被刪除的那個節(jié)點,這時候我們又會遇到三種情況:
- 節(jié)點的右子樹為空,直接將左子樹的根節(jié)點接到父節(jié)點上
- 節(jié)點的左子樹為空,直接將右子樹的根節(jié)點接到父節(jié)點上
- 節(jié)點的右子樹和左子樹都不為空,這時候需要找到并刪去右子樹的最小鍵節(jié)點,然后把這個最小鍵節(jié)點頂替即將被刪除節(jié)點,把它作為新的子樹根節(jié)點
算法書中給出了第三種情況(右子樹和左子樹都不為空)的示例圖:
使用遞歸實現(xiàn)的代碼如下所示:
@Override public void delete(K key) { root = delete(root, key); } private Node delete(Node node, K key) { if (node == null) return null; // 先找到 key 對應(yīng)的節(jié)點 int cmp = node.key.compareTo(key); if (cmp > 0) { node.left = delete(node.left, key); } else if (cmp < 0) { node.right = delete(node.right, key); } else { if (node.right == null) return node.left; if (node.left == null) return node.right; Node x = node; node = min(x.right); // 移除右子樹的最小節(jié)點 node,并將該節(jié)點作為右子樹的根節(jié)點 node.right = deleteMin(x.right); // 設(shè)置左子樹的根節(jié)點為 node node.left = x.left; } node.N = size(node.left) + size(node.right) + 1; return node; }
總結(jié)
如果在插入鍵值對的時候運氣較好,二叉搜索樹的左右子樹高度相近,那么插入和查找的比較次數(shù)為 \(\sim2\ln N\) ;如果運氣非常差,差到所有的節(jié)點連成了一條單向鏈表,那么插入和查找的比較次數(shù)就是 \(\sim N\)。所以就有了自平衡二叉樹的出現(xiàn),不過這已經(jīng)超出本文的探討范圍了(絕對不是因為寫不動了,以上~~
到此這篇關(guān)于在Java中實現(xiàn)二叉搜索樹的文章就介紹到這了,更多相關(guān)Java二叉搜索樹內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
詳解JVM的內(nèi)存對象介紹[創(chuàng)建和訪問]
這篇文章主要介紹了JVM的內(nèi)存對象介紹[創(chuàng)建和訪問],文中通過示例代碼介紹的非常詳細,對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2019-03-03Spring boot定時任務(wù)的原理及動態(tài)創(chuàng)建詳解
這篇文章主要給大家介紹了關(guān)于Spring boot定時任務(wù)的原理及動態(tài)創(chuàng)建的相關(guān)資料,文中通過示例代碼介紹的非常詳細,對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面來一起學(xué)習(xí)學(xué)習(xí)吧2019-03-03mybatisplus如何解決分頁最多500條數(shù)據(jù)
這篇文章主要介紹了mybatisplus如何解決分頁最多500條數(shù)據(jù)的問題,具有很好的參考價值,希望對大家有所幫助。如有錯誤或未考慮完全的地方,望不吝賜教2022-07-07SpringBoot使用AOP與注解實現(xiàn)請求參數(shù)自動填充流程詳解
面向切面編程(aspect-oriented programming,AOP)主要實現(xiàn)的目的是針對業(yè)務(wù)處理過程中的切面進行提取,諸如日志、事務(wù)管理和安全這樣的系統(tǒng)服務(wù),從而使得業(yè)務(wù)邏輯各部分之間的耦合度降低,提高程序的可重用性,同時提高了開發(fā)的效率2023-02-02Spring Cloud-Feign服務(wù)調(diào)用的問題及處理方法
Feign 是一個聲明式的 REST 客戶端,它用了基于接口的注解方式,很方便實現(xiàn)客戶端配置。接下來通過本文給大家介紹Spring Cloud-Feign服務(wù)調(diào)用,需要的朋友可以參考下2021-10-10Presto支持Elasticsearch數(shù)據(jù)源配置詳解
這篇文章主要為大家介紹了Presto支持Elasticsearch數(shù)據(jù)源配置詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進步,早日升職加薪2022-12-12win10和win7下java開發(fā)環(huán)境配置教程
這篇文章主要為大家詳細介紹了win7下Java開發(fā)環(huán)境配置教程,win10下Java開發(fā)環(huán)境配置,具有一定的參考價值,感興趣的小伙伴們可以參考一下2018-06-06