|
當所有的靜態(tài)查找結構添加和刪除一個數(shù)據(jù)的時候，整個結構都需要重建。這對于常常需要在查找過程中動態(tài)改變數(shù)據(jù)而言，是災難性的。因此人們就必須去尋找高效的動態(tài)查找結構，我們在這討論一個非常常用的動態(tài)查找樹——二叉查找樹。 二叉查找樹的特點 下面的圖就是兩棵二叉查找樹，我們可以總結一下他的特點： (1) 若它的左子樹不空，則左子樹上所有結點的值均小于它的根結點的值 (2) 若它的右子樹不空，則右子樹上所有結點的值均大于它的根結點的值  我們中序遍歷這兩棵樹發(fā)現(xiàn)一個有序的數(shù)據(jù)序列： 【1 2 3 4 5 6 7 8 】 二叉查找樹的操作 插入操作： 現(xiàn)在我們要查找一個數(shù)9，如果不存在則，添加進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é)點上，而不會重新建樹。由此可見，動態(tài)查找結構確實在這方面有巨大的優(yōu)勢。 刪除操作： 如果二叉查找樹中需要刪除的結點左、右子樹都存在，則刪除的時候需要改變一些子樹結構，但所需要付出的代價很小。 具體的插入，刪除算法請參加《數(shù)據(jù)結構算法與應用——搜索樹》P5-8。[該章節(jié)已經(jīng)上傳到《查找結構專題(6)：動態(tài)查找樹比較》中]。 二叉查找樹的效率分析 那么我們再來看看二叉查找樹的效率問題 很顯然，在a,b兩圖的二叉查找樹結構中查找一個數(shù)據(jù)，并不需要遍歷全部的節(jié)點元素，查找效率確實提高了。但是有一個很嚴重的問題：我們在a圖中查找8需要比較5次數(shù)據(jù)，而在B圖中只需要比較3次。更為嚴重的是：如果按有序序列[1 2 3 4 5 6 7 8]建立一顆二叉查找樹，整棵樹就退化成了一個線性結構（如c輸入圖：單支樹），此時查找8需要比較8次數(shù)據(jù)，和順序查找沒有什么不同。 總結一下：最壞情況下，構成的二叉排序樹蛻變?yōu)閱沃?，樹的深度為n，其查找時間復雜度與順序查找一樣O(N)。最好的情況是二叉排序樹的形態(tài)和折半查找的判定樹相同，其平均查找長度和log2(N)成正比 （O(log2(n))）。 這說明：同樣一組數(shù)據(jù)集合，不同的添加順序會導致查找樹的結構完全不一樣，直接影響了查找效率。 那么如何解決這個問題呢? 我們會在下面的專題中：《平衡二叉樹》中來解決。 下面是java實現(xiàn)的二叉查找樹（說句老實話，沒有指針的java實現(xiàn)數(shù)據(jù)結構真是復雜）：
package net.hr.algorithm.search;
import java.util.ArrayList;
/**
* 二叉樹節(jié)點結構
* @author heartraid
*/
class BSTNode<E extends Comparable<E>>{
/**結點關鍵字*/
E key=null;
/**直接父親結點*/
BSTNode<E> parent=null;
/**結點左子樹的根節(jié)點*/
BSTNode<E> lchild=null;
/**結點右子樹的根節(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 查詢關鍵字
* @param key 關鍵字
* @return 查詢成功/true, 查詢失敗/false
*/
public boolean search(E key){
System.out.print("搜索關鍵字["+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插入關鍵字
* @param key 關鍵字
* @return 插入成功/true, 插入失敗/false
*/
public boolean insert(E key){
System.out.print("插入關鍵字["+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("刪除關鍵字["+key+"]：");
if(key==null||root==null){
System.out.println("刪除失敗");
return false;
}
else{
System.out.print("搜索路徑[");
//定位到樹中待刪除的結點
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的左結點s
BSTNode<E> s=nodeDel.lchild;
//然后再向s的右盡頭定位(這個結點將替代nodeDel)，其中q一直定位在s的直接父親結點
while(s.rchild!=null){
q=s;
s=s.rchild;
}
//換掉nodeDel的關鍵字為s的關鍵字
nodeDel.key=s.key;
//重新設置s的左子樹
if(q!=nodeDel)
q.rchild=s.lchild;
else
q.lchild=s.lchild;
}
return true;
}
}
}
/**
* 遞歸查找關鍵子
* @param node 樹結點
* @param key 關鍵字
* @return 查找成功，返回該結點，否則返回null。
*/
private BSTNode<E> searchBST(BSTNode<E> node, E key){
if(node==null){
System.out.println("]. 搜索失敗");
return null;
}
System.out.print(node.key+" —>");
//搜索到關鍵字
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);
}
}
/**
* 遞歸插入關鍵字
* @param node 樹結點
* @param key 樹關鍵字
* @return true/插入成功，false/插入失敗
*/
private boolean insertBST(BSTNode<E> node, E key){
System.out.print(node.key+" —>");
//在原樹中找到相同的關鍵字，無需插入。
if(node.key.compareTo(key)==0)
{
System.out.println("]. 搜索有相同關鍵字，插入失敗");
return false;
}
else{
//搜索node的左子樹
if(node.key.compareTo(key)>0){
//如果當前node的左子樹為空，則將新結點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;
}
//如果當前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ù)據(jù)結構》
