Java數據結構超詳細分析二叉搜索樹
1.搜索樹的概念
二叉搜索樹是一種特殊的二叉樹，又稱二叉查找樹，二叉排序樹，它有幾個特點：
- 如果左子樹存在，則左子樹每個結點的值均小于根結點的值。
- 如果右子樹存在，則右子樹每個結點的值均大于根結點的值。
- 中序遍歷二叉搜索樹，得到的序列是依次遞增的。
- 二叉搜索樹的左右子樹均為二叉搜索樹。
- 二叉搜索樹的結點的值不能發(fā)生重復。
2.二叉搜索樹的簡單實現(xiàn)
我們來簡單實現(xiàn)以下搜索樹，就不使用泛型了，二叉搜索樹基本結構：
public class BinarySearchTree {
static class Node {
public int val;
public Node left;
public Node right;
public Node(int val) {
this.val = val;
}
}
public Node root;
//其他方法
}
2.1查找
二叉搜索樹最擅長的就是查找，根據二叉搜索樹的定義，左子樹的元素比根小，右子樹的元素比根大，所以我們只需要根據根結點的值與目標元素的值比較，就能實現(xiàn)查找功能。
- 根與目標元素相等，表示找到了。
- 根比目標元素大，去左子樹找。
- 根比目標元素小，去右子樹找。
- 左右子樹找不到，那就找不到了。
參考實現(xiàn)代碼：
public Node search(int key) {
Node cur = this.root;
while (cur != null) {
//根與目標元素相等，表示找到了。
if (cur.val == key) return cur;
//根比目標元素大，去左子樹找。
else if (cur.val > key) cur = cur.left;
//根比目標元素小，去右子樹找。
else cur = cur.right;
}
//此時cur = null, 左右子樹找不到，那就找不到了。
return cur;
}
2.2插入
需要在二叉搜索樹中插入一個元素，首先得找到一個合適的插入位置，如何找呢？其實就是利用搜索樹查找的方式，找到一個空位，如何將目標結點插入到這個位置。
- 根與插入元素相等，插入元素不能與搜索樹中的元素相等，插入失敗。
- 根比插入元素大，去左子樹找。
- 根比插入元素小，去右子樹找。
- 找到的結點為空，那這個位置就是我們要找的空位。
由于你找到空位時，無法獲取該空位的前一個位置，所以每次查找的時候都需要保存上一次查找的位置。
找到位置后，將目標結點插入到該位置。
參考實現(xiàn)代碼：
public boolean insert(int val) {
//結點為空，直接插
if(root == null) {
root = new Node(val);
return true;
}
Node cur = this.root; //當前查找位置
Node parent = null; //查找的上一個位置
while (cur != null) {
parent = cur;
if (val > cur.val) cur = cur.right;
else if (val < cur.val) cur = cur.left;
else return false;
}
//開始插入，找到空位前一個位置，比插入元素小，空位在右邊，插入右邊
if (val > parent.val) {
parent.right = new Node(val);
} else {
//比插入元素大，空位在左邊，插入左邊
parent.left = new Node(val);
}
return true;
}
2.3刪除
刪除是搜索樹基本操作中最麻煩的一個操作，需要考慮多種情況。
不妨設需要刪除的結點為cur，cur的父結點為parent，搜索樹的根結點為root。首先需要刪除結點，那就得找到結點，所以第一步是找結點，思路與查找的思路一模一樣。
第二步那就是刪除了，刪除結點大概有下面幾種情況：
情況1：cur.left == null
- cur == root，讓root = cur.right;
- cur != root且parent.left == cur，讓parent.left = cur.right;
- cur != root且parent.right == cur，讓parent.right = cur.right。
情況2：cur.right == null
- cur == null，讓root = cur.left;
- cur != root且parent.left == cur，讓parent.left = cur.left;
- cur != root且parent.right == cur，讓parent.right = cur.left。
情況3：cur.left != null && cur.right != null
方案1：找到cur右子樹中最小的元素target，然后將該元素的值覆蓋到cur處（可以理解為交換），此時等價于刪除target處的結點，即該結點的父結點為preTarget。
因為target為cur右子樹最小的一個結點，所以target.left == null，此時preTarget.left == target，所以刪除時按照上面的情況1去進行刪除。
但是還有一種特殊情況，那就是cur.right就是最小結點，此時preTarget==cur，即preTarget.right == target，這時刪除時要將 preTarget.right = target.right。
方案2：找到cur左子樹中最大的元素target，然后將該元素的值覆蓋到cur處（可以理解為交換），此時等價于刪除target處的結點，即該結點的父結點為preTarget。
因為target為cur左子樹最大的一個結點，所以target.right == null，此時preTarget.right == target，所以刪除時按照上面的情況2去進行刪除。
但是還有一種特殊情況，那就是cur.left就是左子樹最大結點，此時preTarget==cur，即preTarget.left == target，這時刪除時要將 preTarget.left = target.left。
參考實現(xiàn)代碼：
public void remove(int key) {
Node cur = root;
Node parent = null;
while (cur != null) {
if(cur.val == key) {
//這里開始刪除
removeNode(cur,parent);
break;
}else if(cur.val < key) {
parent = cur;
cur = cur.right;
}else {
parent = cur;
cur = cur.left;
}
}
}
removeNode方法（方案1）：
public void removeNode(Node cur,Node parent) {
if(cur.left == null) {
if(cur == root) {
root = cur.right;
}else if(cur == parent.left) {
parent.left = cur.right;
}else {
parent.right = cur.right;
}
}else if(cur.right == null) {
if(cur == root) {
root = cur.left;
}else if(cur == parent.left) {
parent.left = cur.left;
}else {
parent.right = cur.left;
}
}else {
Node preTarget = cur ;
Node target = cur.right;
while (target.left != null) {
preTarget = target;
target = target.left;
}
cur.val = target.val;
if (target == preTarget.left) {
preTarget.left = target.right;
} else {
preTarget.right = target.right;
}
}
}
removeNode方法（方案2）：
public void removeNode(Node cur,Node parent) {
if(cur.left == null) {
if(cur == root) {
root = cur.right;
}else if(cur == parent.left) {
parent.left = cur.right;
}else {
parent.right = cur.right;
}
}else if(cur.right == null) {
if(cur == root) {
root = cur.left;
}else if(cur == parent.left) {
parent.left = cur.left;
}else {
parent.right = cur.left;
}
}else {
Node preTarget = cur ;
Node target = cur.left;
while (target.right != null) {
preTarget = target;
target = target.right;
}
cur.val = target.val;
if (target == preTarget.left) {
preTarget.left = target.left;
} else {
preTarget.right = target.left;
}
}
}
2.4修改
搜索樹的修改可以基于刪除和插入，先刪除目標元素，然后再插入修改元素。
參考實現(xiàn)代碼：
public void set(int key, int val) {
remove(key);
insert(val);
}
3.二叉搜索樹的性能
在平衡二叉樹的情況下（左右子樹高度差不超過1），假設有n個結點，此時時間復雜度為二叉樹的高度，即 O ( l o g 2 n ) O(log_2n) O(log2?n)，但是這只是例行情況，最不理想的情況就是二叉樹化為單分支樹，時間復雜為 O ( n ) O(n) O(n)。
為了解決這個問題，后面引申出AVL樹，紅黑樹，其中TreeMap與TreeSet的底層就是紅黑樹。具體紅黑樹是什么，這里就不多說了。
本文到底了，你學會了嗎？
到此這篇關于Java數據結構超詳細分析二叉搜索樹的文章就介紹到這了,更多相關Java 二叉搜索樹內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
Spring?Boot中使用Swagger3.0.0版本構建RESTful?APIs的方法
Swagger?是一個規(guī)范和完整的框架，用于生成、描述、調用和可視化?RESTful?風格的?Web?服務，這篇文章主要介紹了Spring?Boot中使用Swagger3.0.0版本構建RESTful?APIs的方法,需要的朋友可以參考下2022-11-11
本篇文章主要介紹了Spring Boot 使用Druid配置詳解，小編覺得挺不錯的，現(xiàn)在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2017-05-05
這篇文章主要介紹了詳解spring cloud分布式關于熔斷器，詳細的介紹了什么是熔斷器和使用，小編覺得挺不錯的，現(xiàn)在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2018-08-08
流（Stream）是指一連串的數據（字符或字節(jié)），是以先進先出的方式發(fā)送信息的通道，數據源發(fā)送的數據經過這個通道到達目的地，按流向區(qū)分為輸入流和輸出流2022-04-04
這篇文章主要介紹了Spring中依賴注入(DI)幾種方式解讀,構造器依賴注入通過容器觸發(fā)一個類的構造器來實現(xiàn)的,該類有一系列參數,每個參數代表一個對其他類的依賴,需要的朋友可以參考下2024-01-01
這篇文章主要為大家詳細介紹了java編寫汽車租賃系統(tǒng)，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-02-02
這篇文章主要介紹了Java中的FutureTask手寫代碼實例,FutureTask是Future的實現(xiàn),用來異步任務的獲取結果,可以啟動和取消異步任務,查詢異步任務是否計算結束以及獲取最終的異步任務的結果,需要的朋友可以參考下2023-12-12
這篇文章主要為大家介紹了Java實現(xiàn)計算機程序設計思路,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進步,早日升職加薪2023-11-11
這篇文章主要介紹了利用@Value注解為bean的屬性賦值方法總結，文中有詳細的代碼示例，對學習@Value注解有一定的參考價值,需要的朋友可以參考下2023-05-05
使用泛型的目的是利用Java編譯機制,在編譯過程中幫我們檢測代碼中不規(guī)范的有可能導致程序錯誤的代碼,下面這篇文章主要給大家介紹了關于Java泛型與通配符的相關資料,需要的朋友可以參考下2022-03-03