Java深入了解數(shù)據(jù)結(jié)構(gòu)之二叉搜索樹增 插 刪 創(chuàng)詳解
①概念
二叉搜索樹又稱二叉排序樹，它或者是一棵空樹**，或者是具有以下性質(zhì)的二叉樹:
若它的左子樹不為空，則左子樹上所有節(jié)點(diǎn)的值都小于根節(jié)點(diǎn)的值
若它的右子樹不為空，則右子樹上所有節(jié)點(diǎn)的值都大于根節(jié)點(diǎn)的值
它的左右子樹也分別為二叉搜索樹
②操作-查找
二叉搜索樹的查找類似于二分法查找
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;
}
④操作-刪除
刪除操作較為復(fù)雜，但理解了其原理還是比較容易
設(shè)待刪除結(jié)點(diǎn)為 cur, 待刪除結(jié)點(diǎn)的雙親結(jié)點(diǎn)為 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
需要使用替換法進(jìn)行刪除，即在它的右子樹中尋找中序下的第一個(gè)結(jié)點(diǎn)(關(guān)鍵碼最小)，用它的值填補(bǔ)到被刪除節(jié)點(diǎn)中，再來處理該結(jié)點(diǎn)的刪除問題
當(dāng)我們在左右子樹都不為空的情況下進(jìn)行刪除，刪除該節(jié)點(diǎn)會(huì)破壞樹的結(jié)構(gòu)，因此用替罪羊的方法來解決，實(shí)際刪除的過程還是上面的兩種情況，這里還是用到了搜索二叉樹的性質(zhì)
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;
}
}
}
⑤性能分析
插入和刪除操作都必須先查找，查找效率代表了二叉搜索樹中各個(gè)操作的性能。
對有n個(gè)結(jié)點(diǎn)的二叉搜索樹，若每個(gè)元素查找的概率相等，則二叉搜索樹平均查找長度是結(jié)點(diǎn)在二叉搜索樹的深度 的函數(shù)，即結(jié)點(diǎn)越深，則比較次數(shù)越多。
但對于同一個(gè)關(guān)鍵碼集合，如果各關(guān)鍵碼插入的次序不同，可能得到不同結(jié)構(gòu)的二叉搜索樹：
最優(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;
}
}
}
}
到此這篇關(guān)于Java深入了解數(shù)據(jù)結(jié)構(gòu)之二叉搜索樹增 插 刪 創(chuàng)詳解的文章就介紹到這了,更多相關(guān)Java 二叉搜索樹內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
SpringBoot項(xiàng)目如何連接MySQL8.0數(shù)據(jù)庫
這篇文章主要介紹了SpringBoot項(xiàng)目如何連接MySQL8.0數(shù)據(jù)庫，具有很好的參考價(jià)值，希望對大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2022-11-11
SpringBoot加載不出來application.yml文件的解決方法
這篇文章主要介紹了SpringBoot加載不出來application.yml文件的解決方法,文中通過示例代碼講解的非常詳細(xì),對大家的學(xué)習(xí)或者工作有一定的幫助,需要的朋友跟著小編來一起來學(xué)習(xí)吧2023-12-12
這篇文章主要介紹了Java類的加載連接和初始化,結(jié)合具體實(shí)例形式分析了java類的加載、連接、初始化相關(guān)原理與實(shí)現(xiàn)技巧,需要的朋友可以參考下2019-07-07
使用Spring靜態(tài)注入實(shí)現(xiàn)讀取配置工具類新方式
這篇文章主要介紹了使用Spring靜態(tài)注入實(shí)現(xiàn)讀取配置工具類新方式，具有很好的參考價(jià)值，希望對大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2022-02-02
這篇文章主要介紹了Java幾種常用的斷言風(fēng)格你怎么選，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-01-01
這篇文章主要介紹了Spring框架 注解配置事務(wù)控制的流程，具有很好的參考價(jià)值，希望對大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2021-09-09
Java實(shí)現(xiàn)讀取文件夾下（包括子目錄）所有文件的文件名
這篇文章主要介紹了Java實(shí)現(xiàn)讀取文件夾下（包括子目錄）所有文件的文件名,本文把代碼組織成了一個(gè)模塊,可以很方便的使用,需要的朋友可以參考下2015-06-06
SpringBoot使用Sa-Token實(shí)現(xiàn)權(quán)限認(rèn)證
本文主要介紹了SpringBoot使用Sa-Token實(shí)現(xiàn)權(quán)限認(rèn)證，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2023-04-04
MyBatis-Plus非表字段的三種處理方法小結(jié)
這篇文章主要介紹了MyBatis-Plus非表字段的三種處理方法小結(jié)，具有很好的參考價(jià)值，希望對大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2021-08-08
BeanUtils.copyProperties()參數(shù)的賦值順序說明
這篇文章主要介紹了BeanUtils.copyProperties()參數(shù)的賦值順序說明，具有很好的參考價(jià)值，希望對大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2021-09-09