當(dāng)所有的靜態(tài)查找結(jié)構(gòu)添加和刪除一個數(shù)據(jù)的時候，整個結(jié)構(gòu)都需要重建。這對于常常需要在查找過程中動態(tài)改變數(shù)據(jù)而言，是災(zāi)難性的。因此人們就必須去尋找高效的動態(tài)查找結(jié)構(gòu)，我們在這討論一個非常常用的動態(tài)查找樹—— 二叉查找樹 。
?
二叉查找樹的特點
?
下面的圖就是兩棵二叉查找樹，我們可以總結(jié)一下他的特點：
(1) 若它的左子樹不空，則左子樹上所有結(jié)點的值均小于它的根結(jié)點的值
(2) 若它的右子樹不空，則右子樹上所有結(jié)點的值均大于它的根結(jié)點的值
(3) 它的左、右子樹也分別為二叉查找樹
?
?
我們中序遍歷這兩棵樹發(fā)現(xiàn)一個有序的數(shù)據(jù)序列： 【1? 2? 3? 4? 5? 6? 7? 8 】
?
?
二叉查找樹的操作
?
插入操作：
現(xiàn)在我們要查找一個數(shù)9，如果不存在則，添加進(jìn)a圖。我們看看二叉查找樹動態(tài)添加的過程：
1). 數(shù)9和根節(jié)點4比較(9>4)，則9放在節(jié)點4的右子樹中。
2). 接著，9和節(jié)點5比較(9>5)，則9放在節(jié)點5的右子樹中。
3). 依次類推：直到9和節(jié)點8比較(9>8)，則9放在節(jié)點8的右子樹中，成為節(jié)點8的右孩子。
這個過程我們能夠發(fā)現(xiàn)， 動態(tài)添加任何一個數(shù)據(jù)，都會加在原樹結(jié)構(gòu)的葉子節(jié)點上，而不會重新建樹。 由此可見，動態(tài)查找結(jié)構(gòu)確實在這方面有巨大的優(yōu)勢。
?
刪除操作：
如果二叉查找樹中需要刪除的結(jié)點左、右子樹都存在，則刪除的時候需要改變一些子樹結(jié)構(gòu)，但所需要付出的代價很小。
?
具體的插入，刪除算法請參加《數(shù)據(jù)結(jié)構(gòu)算法與應(yīng)用——搜索樹》P5-8。[該章節(jié)已經(jīng)上傳到《 查找結(jié)構(gòu)專題(6)：動態(tài)查找樹比較 》中]。
?
?
二叉查找樹的效率分析
?
?
那么我們再來看看二叉查找樹的效率問題
?
很顯然，在a,b兩圖的二叉查找樹結(jié)構(gòu)中查找一個數(shù)據(jù)，并不需要遍歷全部的節(jié)點元素，查找效率確實提高了。但是有一個很嚴(yán)重的問題：我們在a圖中查找8需要比較5次數(shù)據(jù)，而在B圖中只需要比較3次。更為嚴(yán)重的是：如果按有序序列[1 2 3 4 5 6 7 8]建立一顆二叉查找樹，整棵樹就退化成了一個線性結(jié)構(gòu)（如c輸入圖：單支樹），此時查找8需要比較8次數(shù)據(jù)，和順序查找沒有什么不同。
總結(jié)一下：最壞情況下，構(gòu)成的二叉排序樹蛻變?yōu)閱沃洌瑯涞纳疃葹閚，其查找時間復(fù)雜度與順序查找一樣O(N)。最好的情況是二叉排序樹的形態(tài)和折半查找的判定樹相同，其平均查找長度和log2(N)成正比 （O(log2(n))）。
?
這說明： 同樣一組數(shù)據(jù)集合，不同的添加順序會導(dǎo)致查找樹的結(jié)構(gòu)完全不一樣，直接影響了查找效率。
?
那么如何解決這個問題呢? 我們會在下面的專題中： 《平衡二叉樹》 中來解決。
?
下面是java實現(xiàn)的二叉查找樹（說句老實話，沒有指針的java實現(xiàn)數(shù)據(jù)結(jié)構(gòu)真是復(fù)雜）：
package net.hr.algorithm.search;
import java.util.ArrayList;
/**
* 二叉樹節(jié)點結(jié)構(gòu)
* @author heartraid
*/
class BSTNode<E extends Comparable<E>>{
/**結(jié)點關(guān)鍵字*/
E key=null;
/**直接父親結(jié)點*/
BSTNode<E> parent=null;
/**結(jié)點左子樹的根節(jié)點*/
BSTNode<E> lchild=null;
/**結(jié)點右子樹的根節(jié)點*/
BSTNode<E> rchild=null;
BSTNode(E k){
this.key=k;
}
}
/**
* 二叉查找樹 Binary Search Tree(BST)
* @author heartraid
*
*/
public class BST<E extends Comparable<E>> {
/**樹根*/
private BSTNode<E> root=null;
public BST(){
}
/**
* BST 查詢關(guān)鍵字
* @param key 關(guān)鍵字
* @return 查詢成功/true, 查詢失敗/false
*/
public boolean search(E key){
System.out.print("搜索關(guān)鍵字["+key+"]：");
if(key==null||root==null){
System.out.println("搜索失敗");
return false;
}
else{
System.out.print("搜索路徑[");
if(searchBST(root,key)==null){
return false;
}
else return true;
}
}
/**
* BST插入關(guān)鍵字
* @param key 關(guān)鍵字
* @return 插入成功/true, 插入失敗/false
*/
public boolean insert(E key){
System.out.print("插入關(guān)鍵字["+key+"]：");
if(key==null) return false;
if(root==null){
System.out.println("插入到樹根。");
root=new BSTNode<E>(key);
return true;
}
else{
System.out.print("搜索路徑[");
return insertBST(root,key);
}
}
public boolean delete(E key){
System.out.print("刪除關(guān)鍵字["+key+"]：");
if(key==null||root==null){
System.out.println("刪除失敗");
return false;
}
else{
System.out.print("搜索路徑[");
//定位到樹中待刪除的結(jié)點
BSTNode<E> nodeDel=searchBST(root,key);
if(nodeDel==null){
return false;
}
else{
//nodeDel的右子樹為空,則只需要重接它的左子樹
if(nodeDel.rchild==null){
BSTNode<E> parent=nodeDel.parent;
if(parent.lchild.key.compareTo(nodeDel.key)==0)
parent.lchild=nodeDel.lchild;
else
parent.rchild=nodeDel.lchild;
}
//左子樹為空,則重接它的右子樹
else if(nodeDel.lchild==null){
BSTNode<E> parent=nodeDel.parent;
if(parent.lchild.key.compareTo(nodeDel.key)==0)
parent.lchild=nodeDel.rchild;
else
parent.rchild=nodeDel.rchild;
}
//左右子樹均不空
else{
BSTNode<E> q=nodeDel;
//先找nodeDel的左結(jié)點s
BSTNode<E> s=nodeDel.lchild;
//然后再向s的右盡頭定位(這個結(jié)點將替代nodeDel)，其中q一直定位在s的直接父親結(jié)點
while(s.rchild!=null){
q=s;
s=s.rchild;
}
//換掉nodeDel的關(guān)鍵字為s的關(guān)鍵字
nodeDel.key=s.key;
//重新設(shè)置s的左子樹
if(q!=nodeDel)
q.rchild=s.lchild;
else
q.lchild=s.lchild;
}
return true;
}
}
}
/**
* 遞歸查找關(guān)鍵子
* @param node 樹結(jié)點
* @param key 關(guān)鍵字
* @return 查找成功，返回該結(jié)點，否則返回null。
*/
private BSTNode<E> searchBST(BSTNode<E> node, E key){
if(node==null){
System.out.println("]. 搜索失敗");
return null;
}
System.out.print(node.key+" —>");
//搜索到關(guān)鍵字
if(node.key.compareTo(key)==0){
System.out.println("]. 搜索成功");
return node;
}
//在左子樹搜索
else if(node.key.compareTo(key)>0){
return searchBST(node.lchild,key);
}
//在右子樹搜索
else{
return searchBST(node.rchild,key);
}
}
/**
* 遞歸插入關(guān)鍵字
* @param node 樹結(jié)點
* @param key 樹關(guān)鍵字
* @return true/插入成功，false/插入失敗
*/
private boolean insertBST(BSTNode<E> node, E key){
System.out.print(node.key+" —>");
//在原樹中找到相同的關(guān)鍵字，無需插入。
if(node.key.compareTo(key)==0)
{
System.out.println("]. 搜索有相同關(guān)鍵字，插入失敗");
return false;
}
else{
//搜索node的左子樹
if(node.key.compareTo(key)>0){
//如果當(dāng)前node的左子樹為空，則將新結(jié)點key node插入到左孩子處
if(node.lchild==null) {
System.out.println("]. 插入到"+node.key+"的左孩子");
BSTNode<E> newNode=new BSTNode<E>(key);
node.lchild=newNode;
newNode.parent=node;
return true;
}
//如果當(dāng)前node的左子樹存在，則繼續(xù)遞歸左子樹
else return insertBST(node.lchild, key);
}
//搜索node的右子樹
else{
if(node.rchild==null){
System.out.println("]. 插入到"+node.key+"的右孩子");
BSTNode<E> newNode=new BSTNode<E>(key);
node.rchild=newNode;
newNode.parent=node;
return true;
}
else return insertBST(node.rchild,key);
}
}
}
/**
* 得到BST根節(jié)點
* @return BST根節(jié)點f
*/
public BSTNode<E> getRoot(){
return this.root;
}
/**
* 非遞歸中序遍歷BST
*/
public void InOrderTraverse(){
if(root==null)
return;
BSTNode<E> node=root;
ArrayList<BSTNode<E>> stack=new ArrayList<BSTNode<E>>();
stack.add(node);
while(!stack.isEmpty()){
while(node.lchild!=null){
node=node.lchild;
stack.add(node);
}
if(!stack.isEmpty()){
BSTNode<E> topNode=stack.get(stack.size()-1);
System.out.print(topNode.key+" ");
stack.remove(stack.size()-1);
if(topNode.rchild!=null){
node=topNode.rchild;
stack.add(node);
}
}
}
}
/**
* 測試
*/
public static void main(String[] args) {
BST<Integer> tree=new BST<Integer>();
tree.insert(new Integer(100));
tree.insert(new Integer(52));
tree.insert(new Integer(166));
tree.insert(new Integer(74));
tree.insert(new Integer(11));
tree.insert(new Integer(13));
tree.insert(new Integer(66));
tree.insert(new Integer(121));
tree.search(new Integer(11));
tree.InOrderTraverse();
tree.delete(new Integer(11));
tree.InOrderTraverse();
}
}
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯(lián)系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機(jī)微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
