Java深入了解數(shù)據(jù)結構之二叉搜索樹增 插 刪 創(chuàng)詳解
①概念
二叉搜索樹又稱二叉排序樹，它或者是一棵空樹**，或者是具有以下性質的二叉樹:
若它的左子樹不為空，則左子樹上所有節(jié)點的值都小于根節(jié)點的值
若它的右子樹不為空，則右子樹上所有節(jié)點的值都大于根節(jié)點的值
它的左右子樹也分別為二叉搜索樹
②操作-查找
二叉搜索樹的查找類似于二分法查找
public Node search(int key) {
Node cur = root;
while (cur != null) {
if(cur.val == key) {
return cur;
}else if(cur.val < key) {
cur = cur.right;
}else {
cur = cur.left;
}
}
return null;
}
③操作-插入
public boolean insert(int key) {
Node node = new Node(key);
if(root == null) {
root = node;
return true;
}
Node cur = root;
Node parent = null;
while(cur != null) {
if(cur.val == key) {
return false;
}else if(cur.val < key) {
parent = cur;
cur = cur.right;
}else {
parent = cur;
cur = cur.left;
}
}
//parent
if(parent.val > key) {
parent.left = node;
}else {
parent.right = node;
}
return true;
}
④操作-刪除
刪除操作較為復雜，但理解了其原理還是比較容易
設待刪除結點為 cur, 待刪除結點的雙親結點為 parent
1. cur.left == null
1. cur 是 root，則 root = cur.right
2. cur 不是 root，cur 是 parent.left，則 parent.left = cur.right
3. cur 不是 root，cur 是 parent.right，則 parent.right = cur.right
2. cur.right == null
1. cur 是 root，則 root = cur.left
2. cur 不是 root，cur 是 parent.left，則 parent.left = cur.left
3. cur 不是 root，cur 是 parent.right，則 parent.right = cur.left
第二種情況和第一種情況相同，只是方向相反，這里不再畫圖
3. cur.left != null && cur.right != null
需要使用替換法進行刪除，即在它的右子樹中尋找中序下的第一個結點(關鍵碼最小)，用它的值填補到被刪除節(jié)點中，再來處理該結點的刪除問題
當我們在左右子樹都不為空的情況下進行刪除，刪除該節(jié)點會破壞樹的結構，因此用替罪羊的方法來解決，實際刪除的過程還是上面的兩種情況，這里還是用到了搜索二叉樹的性質
public void remove(Node parent,Node cur) {
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 targetParent = cur;
Node target = cur.right;
while (target.left != null) {
targetParent = target;
target = target.left;
}
cur.val = target.val;
if(target == targetParent.left) {
targetParent.left = target.right;
}else {
targetParent.right = target.right;
}
}
}
public void removeKey(int key) {
if(root == null) {
return;
}
Node cur = root;
Node parent = null;
while (cur != null) {
if(cur.val == key) {
remove(parent,cur);
return;
}else if(cur.val < key){
parent = cur;
cur = cur.right;
}else {
parent = cur;
cur = cur.left;
}
}
}
⑤性能分析
插入和刪除操作都必須先查找，查找效率代表了二叉搜索樹中各個操作的性能。
對有n個結點的二叉搜索樹，若每個元素查找的概率相等，則二叉搜索樹平均查找長度是結點在二叉搜索樹的深度 的函數(shù)，即結點越深，則比較次數(shù)越多。
但對于同一個關鍵碼集合，如果各關鍵碼插入的次序不同，可能得到不同結構的二叉搜索樹：
最優(yōu)情況下，二叉搜索樹為完全二叉樹，其平均比較次數(shù)為：
最差情況下，二叉搜索樹退化為單支樹，其平均比較次數(shù)為：
⑥完整代碼
public class TextDemo {
public static class Node {
public int val;
public Node left;
public Node right;
public Node (int val) {
this.val = val;
}
}
public Node root;
/**
* 查找
* @param key
*/
public Node search(int key) {
Node cur = root;
while (cur != null) {
if(cur.val == key) {
return cur;
}else if(cur.val < key) {
cur = cur.right;
}else {
cur = cur.left;
}
}
return null;
}
/**
*
* @param key
* @return
*/
public boolean insert(int key) {
Node node = new Node(key);
if(root == null) {
root = node;
return true;
}
Node cur = root;
Node parent = null;
while(cur != null) {
if(cur.val == key) {
return false;
}else if(cur.val < key) {
parent = cur;
cur = cur.right;
}else {
parent = cur;
cur = cur.left;
}
}
//parent
if(parent.val > key) {
parent.left = node;
}else {
parent.right = node;
}
return true;
}
public void remove(Node parent,Node cur) {
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 targetParent = cur;
Node target = cur.right;
while (target.left != null) {
targetParent = target;
target = target.left;
}
cur.val = target.val;
if(target == targetParent.left) {
targetParent.left = target.right;
}else {
targetParent.right = target.right;
}
}
}
public void removeKey(int key) {
if(root == null) {
return;
}
Node cur = root;
Node parent = null;
while (cur != null) {
if(cur.val == key) {
remove(parent,cur);
return;
}else if(cur.val < key){
parent = cur;
cur = cur.right;
}else {
parent = cur;
cur = cur.left;
}
}
}
}
到此這篇關于Java深入了解數(shù)據(jù)結構之二叉搜索樹增 插 刪 創(chuàng)詳解的文章就介紹到這了,更多相關Java 二叉搜索樹內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
這篇文章主要介紹了SpringBoot之如何指定配置文件啟動問題，具有很好的參考價值，希望對大家有所幫助。2023-04-04
SpringBoot調用第三方WebService接口的兩種方法
本文主要介紹了SpringBoot調用第三方WebService接口的兩種方法，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2023-06-06
本章,是MapReduce的最終章,我在寫本章的時候,發(fā)現(xiàn)前面忘記介紹MpaTask與ReduceTask了,所以本章補上哈,另外還有兩個擴展的知識點,講完這些,我會對整個MapReduce進行總結一下,讓大家再次了解MapReduce的工作流程,更加清晰地認識MapReduce ,需要的朋友可以參考下2021-05-05
springboot配置druid多數(shù)據(jù)源的示例代碼
這篇文章主要介紹了springboot配置druid多數(shù)據(jù)源的示例代碼,本文通過實例代碼給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下2022-09-09
這篇文章主要為大家詳細介紹了JAVA提高第九篇集合體系的相關資料，具有一定的參考價值，感興趣的小伙伴們可以參考一下2017-10-10
這篇文章主要介紹了基于redis key占用內存量分析，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2020-11-11
MyBatis-Plus詳解(環(huán)境搭建、關聯(lián)操作)
MyBatis-Plus 是一個 MyBatis 的增強工具，在 MyBatis 的基礎上只做增強不做改變，為簡化開發(fā)、提高效率而生，今天通過本文給大家介紹MyBatis-Plus環(huán)境搭建及關聯(lián)操作，需要的朋友參考下吧2022-09-09
這篇文章主要介紹了Java編碼輔助工具Mapstruct用法詳解，手動編碼setter/getter各個對應屬性，會顯得臃腫繁瑣。通過Mapstruct框架可簡單方便地完成這一工作。,需要的朋友可以參考下2019-06-06
spring?boot+mybatis-plus配置讀寫分離的操作
這篇文章主要介紹了spring?boot+mybatis-plus配置讀寫分離的操作，本文通過實例代碼給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值,需要的朋友可以參考下2024-01-01
SpringBoot使用Apache Tika實現(xiàn)多種文檔的內容解析
在日常開發(fā)中,我們經常需要解析不同類型的文檔,如PDF、Word、Excel、HTML、TXT等,Apache Tika是一個強大的內容解析工具,可以輕松地提取文檔中的內容和元數(shù)據(jù)信息,本文將通過SpringBoot和Apache Tika的結合,介紹如何實現(xiàn)對多種文檔格式的內容解析2024-12-12