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項目如何連接MySQL8.0數(shù)據(jù)庫
這篇文章主要介紹了SpringBoot項目如何連接MySQL8.0數(shù)據(jù)庫，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-11-11
SpringBoot加載不出來application.yml文件的解決方法
這篇文章主要介紹了SpringBoot加載不出來application.yml文件的解決方法,文中通過示例代碼講解的非常詳細,對大家的學習或者工作有一定的幫助,需要的朋友跟著小編來一起來學習吧2023-12-12
這篇文章主要介紹了Java類的加載連接和初始化,結合具體實例形式分析了java類的加載、連接、初始化相關原理與實現(xiàn)技巧,需要的朋友可以參考下2019-07-07
使用Spring靜態(tài)注入實現(xiàn)讀取配置工具類新方式
這篇文章主要介紹了使用Spring靜態(tài)注入實現(xiàn)讀取配置工具類新方式，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-02-02
這篇文章主要介紹了Java幾種常用的斷言風格你怎么選，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2020-01-01
這篇文章主要介紹了Spring框架 注解配置事務控制的流程，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2021-09-09
Java實現(xiàn)讀取文件夾下（包括子目錄）所有文件的文件名
這篇文章主要介紹了Java實現(xiàn)讀取文件夾下（包括子目錄）所有文件的文件名,本文把代碼組織成了一個模塊,可以很方便的使用,需要的朋友可以參考下2015-06-06
SpringBoot使用Sa-Token實現(xiàn)權限認證
本文主要介紹了SpringBoot使用Sa-Token實現(xiàn)權限認證，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2023-04-04
這篇文章主要介紹了MyBatis-Plus非表字段的三種處理方法小結，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2021-08-08
BeanUtils.copyProperties()參數(shù)的賦值順序說明
這篇文章主要介紹了BeanUtils.copyProperties()參數(shù)的賦值順序說明，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2021-09-09