515
技術社區[雲棲]
Java實現 二叉搜索樹算法（BST）
一、樹 & 二叉樹
樹是由節點和邊構成，儲存元素的集合。節點分根節點、父節點和子節點的概念。
如圖：樹深=4; 5是根節點；同樣8與3的關係是父子節點關係。
二叉樹binary tree，則加了“二叉”（binary），意思是在樹中作區分。每個節點至多有兩個子（child）,left child & right child。二叉樹在很多例子中使用，比如二叉樹表示算術表達式。
如圖：1/8是左節點；2/3是右節點；
二、二叉搜索樹 BST
顧名思義，二叉樹上又加了個搜索的限製。其要求：每個節點比其左子樹元素大，比其右子樹元素小。
如圖：每個節點比它左子樹的任意節點大，而且比它右子樹的任意節點小
三、BST Java實現
直接上代碼，對應代碼分享在 Github 主頁
BinarySearchTree.java
package org.algorithm.tree;
/*
* Copyright [2015] [Jeff Lee]
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
* https://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
/**
* 二叉搜索樹(BST)實現
*
* Created by bysocket on 16/7/7.
*/
public class BinarySearchTree {
/**
* 根節點
*/
public static TreeNode root;
public BinarySearchTree() {
this.root = null;
}
/**
* 查找
* 樹深(N) O(lgN)
* 1. 從root節點開始
* 2. 比當前節點值小,則找其左節點
* 3. 比當前節點值大,則找其右節點
* 4. 與當前節點值相等,查找到返回TRUE
* 5. 查找完畢未找到,
* @param key
* @return
*/
public TreeNode search (int key) {
TreeNode current = root;
while (current != null
&& key != current.value) {
if (key < current.value )
current = current.left;
else
current = current.right;
}
return current;
}
/**
* 插入
* 1. 從root節點開始
* 2. 如果root為空,root為插入值
* 循環:
* 3. 如果當前節點值大於插入值,找左節點
* 4. 如果當前節點值小於插入值,找右節點
* @param key
* @return
*/
public TreeNode insert (int key) {
// 新增節點
TreeNode newNode = new TreeNode(key);
// 當前節點
TreeNode current = root;
// 上個節點
TreeNode parent = null;
// 如果根節點為空
if (current == null) {
root = newNode;
return newNode;
}
while (true) {
parent = current;
if (key < current.value) {
current = current.left;
if (current == null) {
parent.left = newNode;
return newNode;
}
} else {
current = current.right;
if (current == null) {
parent.right = newNode;
return newNode;
}
}
}
}
/**
* 刪除節點
* 1.找到刪除節點
* 2.如果刪除節點左節點為空 , 右節點也為空;
* 3.如果刪除節點隻有一個子節點 右節點 或者 左節點
* 4.如果刪除節點左右子節點都不為空
* @param key
* @return
*/
public TreeNode delete (int key) {
TreeNode parent = root;
TreeNode current = root;
boolean isLeftChild = false;
// 找到刪除節點 及 是否在左子樹
while (current.value != key) {
parent = current;
if (current.value > key) {
isLeftChild = true;
current = current.left;
} else {
isLeftChild = false;
current = current.right;
}
if (current == null) {
return current;
}
}
// 如果刪除節點左節點為空 , 右節點也為空
if (current.left == null && current.right == null) {
if (current == root) {
root = null;
}
// 在左子樹
if (isLeftChild == true) {
parent.left = null;
} else {
parent.right = null;
}
}
// 如果刪除節點隻有一個子節點 右節點 或者 左節點
else if (current.right == null) {
if (current == root) {
root = current.left;
} else if (isLeftChild) {
parent.left = current.left;
} else {
parent.right = current.left;
}
}
else if (current.left == null) {
if (current == root) {
root = current.right;
} else if (isLeftChild) {
parent.left = current.right;
} else {
parent.right = current.right;
}
}
// 如果刪除節點左右子節點都不為空
else if (current.left != null && current.right != null) {
// 找到刪除節點的後繼者
TreeNode successor = getDeleteSuccessor(current);
if (current == root) {
root = successor;
} else if (isLeftChild) {
parent.left = successor;
} else {
parent.right = successor;
}
successor.left = current.left;
}
return current;
}
/**
* 獲取刪除節點的後繼者
* 刪除節點的後繼者是在其右節點樹種最小的節點
* @param deleteNode
* @return
*/
public TreeNode getDeleteSuccessor(TreeNode deleteNode) {
// 後繼者
TreeNode successor = null;
TreeNode successorParent = null;
TreeNode current = deleteNode.right;
while (current != null) {
successorParent = successor;
successor = current;
current = current.left;
}
// 檢查後繼者(不可能有左節點樹)是否有右節點樹
// 如果它有右節點樹,則替換後繼者位置,加到後繼者父親節點的左節點.
if (successor != deleteNode.right) {
successorParent.left = successor.right;
successor.right = deleteNode.right;
}
return successor;
}
public void toString(TreeNode root) {
if (root != null) {
toString(root.left);
System.out.print("value = " + root.value + " -> ");
toString(root.right);
}
}
}
/**
* 節點
*/
class TreeNode {
/**
* 節點值
*/
int value;
/**
* 左節點
*/
TreeNode left;
/**
* 右節點
*/
TreeNode right;
public TreeNode(int value) {
this.value = value;
left = null;
right = null;
}
}
1. 節點數據結構
首先定義了節點的數據接口，節點分左節點和右節點及本身節點值。如圖
代碼如下：
/**
* 節點
*/
class TreeNode {
/**
* 節點值
*/
int value;
/**
* 左節點
*/
TreeNode left;
/**
* 右節點
*/
TreeNode right;
public TreeNode(int value) {
this.value = value;
left = null;
right = null;
}
}
2. 插入
插入，和刪除一樣會引起二叉搜索樹的動態變化。插入相對刪處理邏輯相對簡單些。如圖插入的邏輯：
a. 從root節點開始
b.如果root為空,root為插入值
c.循環:
d.如果當前節點值大於插入值,找左節點
e.如果當前節點值小於插入值,找右節點
代碼對應：
/**
* 插入
* 1. 從root節點開始
* 2. 如果root為空,root為插入值
* 循環:
* 3. 如果當前節點值大於插入值,找左節點
* 4. 如果當前節點值小於插入值,找右節點
* @param key
* @return
*/
public TreeNode insert (int key) {
// 新增節點
TreeNode newNode = new TreeNode(key);
// 當前節點
TreeNode current = root;
// 上個節點
TreeNode parent = null;
// 如果根節點為空
if (current == null) {
root = newNode;
return newNode;
}
while (true) {
parent = current;
if (key < current.value) {
current = current.left;
if (current == null) {
parent.left = newNode;
return newNode;
}
} else {
current = current.right;
if (current == null) {
parent.right = newNode;
return newNode;
}
}
}
}
3.查找
其算法複雜度 : O(lgN),樹深(N)。如圖查找邏輯：
a.從root節點開始
b.比當前節點值小,則找其左節點
c.比當前節點值大,則找其右節點
d.與當前節點值相等,查找到返回TRUE
e.查找完畢未找到
代碼對應：
/**
* 查找
* 樹深(N) O(lgN)
* 1. 從root節點開始
* 2. 比當前節點值小,則找其左節點
* 3. 比當前節點值大,則找其右節點
* 4. 與當前節點值相等,查找到返回TRUE
* 5. 查找完畢未找到,
* @param key
* @return
*/
public TreeNode search (int key) {
TreeNode current = root;
while (current != null
&& key != current.value) {
if (key < current.value )
current = current.left;
else
current = current.right;
}
return current;
}
4. 刪除
首先找到刪除節點，其尋找方法：刪除節點的後繼者是在其右節點樹種最小的節點。如圖刪除對應邏輯：
結果為：
a.找到刪除節點
b.如果刪除節點左節點為空 , 右節點也為空;
c.如果刪除節點隻有一個子節點 右節點 或者 左節點
d.如果刪除節點左右子節點都不為空
代碼對應見上麵完整代碼。
案例測試代碼如下，BinarySearchTreeTest.java
package org.algorithm.tree;
/*
* Copyright [2015] [Jeff Lee]
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
* https://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
/**
* 二叉搜索樹(BST)測試案例 {@link BinarySearchTree}
*
* Created by bysocket on 16/7/10.
*/
public class BinarySearchTreeTest {
public static void main(String[] args) {
BinarySearchTree b = new BinarySearchTree();
b.insert(3);b.insert(8);b.insert(1);b.insert(4);b.insert(6);
b.insert(2);b.insert(10);b.insert(9);b.insert(20);b.insert(25);
// 打印二叉樹
b.toString(b.root);
System.out.println();
// 是否存在節點值10
TreeNode node01 = b.search(10);
System.out.println("是否存在節點值為10 => " + node01.value);
// 是否存在節點值11
TreeNode node02 = b.search(11);
System.out.println("是否存在節點值為11 => " + node02);
// 刪除節點8
TreeNode node03 = b.delete(8);
System.out.println("刪除節點8 => " + node03.value);
b.toString(b.root);
}
}
運行結果如下：
value = 1 -> value = 2 -> value = 3 -> value = 4 -> value = 6 -> value = 8 -> value = 9 -> value = 10 -> value = 20 -> value = 25 -> 是否存在節點值為10 => 10 是否存在節點值為11 => null 刪除節點8 => 8 value = 1 -> value = 2 -> value = 3 -> value = 4 -> value = 6 -> value = 9 -> value = 10 -> value = 20 -> value = 25 ->
四、小結
與偶爾吃一碗“老壇酸菜牛肉麵”一樣的味道，品味一個算法，比如BST，的時候，總是那種說不出的味道。
樹，二叉樹的概念
BST算法
最後更新：2017-05-19 14:33:09