天天看點
傳回

動态查找---->二叉查找樹(Binary Search Tree)

二叉查找樹(Binary Search Tree)

一、二叉查找樹的定義

----或是一棵空樹；或者是具有如下性質的非空二叉樹：

 （1）左子樹的所有結點均小于根的值；

 （2）右子樹的所有結點均大于根的值；

動态查找---->二叉查找樹(Binary Search Tree)

結論：中序周遊一棵二叉查找樹可以得到一個按關鍵字遞增的有序序列。

1、查找

查找的遞歸實作 ：

private Node binTSearchRe(BinTreeNode rt, Object ele) {
		if (rt == null)
			return null;
		switch (strategy.compare(ele, rt.getData())) {
		case 0:
			return rt; // 等于
		case -1:
			return binTSearchRe(rt.getLChild(), ele);// 小于
		default:
			return binTSearchRe(rt.getRChild(), ele);// 大于
		}
	}

調用

// 傳回查找表中與元素ele關鍵字相同的元素位置；否則，傳回null
	public Node search(Object ele) {
		return binTSearch(root, ele);
	}

查找的非遞歸實作

private Node binTSearch(BinTreeNode rt, Object ele) {
		while (rt != null) {
			switch (strategy.compare(ele, rt.getData())) {
			case 0:
				return rt; // 等于
			case -1:
				rt = rt.getLChild();
				continue;// 小于
			default:
				rt = rt.getRChild(); // 大于
			}
		}
		return null;
	}

查找分析

含有n個結點的二叉查找樹的平均查找長度和樹的形态有關。

在具有n個結點的二叉樹中，樹的最小高度為log n ，即在最好的情況下二叉查找樹的平均查找長度與折半查找一樣與log n 成正比。具有n個結點的二叉樹可以退化為一個單連結清單，其深度為n-1，此時其平均查找長度為(n+1)/2，與順序查找相同，這是最差的情況。在平均情況下，如果随機生成二叉查找樹，其平均查找長度和log

n 是等數量級的。

2、最大最小值

在二叉查找樹中，最小元素總是能夠通過根結點向左不斷深入，直到到達最左的一個葉子結點找到；而最大元素總是能夠通過根結點向右不斷深入，直到到達最右的一個葉子結點找到。

Max

public Node max(BinTreeNode v) {
		if (v != null)
			while (v.hasRChild())
				v = v.getRChild();
		return v;
	}

3、前驅和後續

在二叉查找樹中确定某個結點v 的後續結點的算法思想如下：如果結點v 有右子樹，那麼v 的後續結點是v 的右子樹中關鍵字最小的；如果結點v

右子樹為空，并且v 的後續結點存在，那麼v 的後續結點是從v（包含v）到根的路徑上第一個作為左孩子結點的父結點。

代碼：求v在中序周遊序列中的後續結點

// 傳回結點v在中序周遊序列中的後續結點
	private BinTreeNode getSuccessor(BinTreeNode v) {
		if (v == null)
			return null;
		if (v.hasRChild())
			return (BinTreeNode) min(v.getRChild());
		while (v.isRChild())
 			v = v.getParent();
		return v.getParent();
	}

代碼：求v在中序周遊序列中的前驅結點

// 傳回結點v在中序周遊序列中的前驅結點
	private BinTreeNode getPredecessor(BinTreeNode v) {
		if (v == null)
			return null;
		if (v.hasLChild())
			return (BinTreeNode) max(v.getLChild());
		while (v.isLChild())
			v = v.getParent();
		return v.getParent();
	}

4、插入

為了判定新結點的插入位置，需要從根結點開始逐層深入，判斷新結點關鍵字與各子樹根結點關鍵字的大小，若新結點關鍵字小，則向相應根結點的左子樹深入，否則向右子樹深入；直到向某個結點的左子樹深入而其左子樹為空，或向某個結點的右子樹深入而其右子樹為空時，則确定了新結點的插入位置。

// 按關鍵字插入元素ele
	public void insert(Object ele) {
		BinTreeNode p = null;
		BinTreeNode current = root;
		while (current != null) { // 找到待插入位置
			p = current;
			if (strategy.compare(ele, current.getData()) < 0)
				current = current.getLChild();
			else
				current = current.getRChild();
		}
				if (p == null)
			root = new BinTreeNode(ele); // 樹為空
		else if (strategy.compare(ele, p.getData()) < 0)
			p.setLChild(new BinTreeNode(ele));
		else
			p.setRChild(new BinTreeNode(ele));
	}

5、删除算法

對于二叉查找樹，删除樹上一個結點相當于删除有序序列中的一個記錄，删除後仍需保持二叉查找樹的特性。在二叉查找樹中删除的結點不總是葉子結點，是以在删除一個非葉子結點時需要處理該結點的子樹。

如何删除一個結點？

下面我們分三種情況讨論結點v 的删除：

⑴如果結點v為葉子結點，即其左右子樹Pl和Pr均為空，此時可以直接删除該葉子結點v，而不會破壞二叉查找樹的特性，是以直接從樹中摘除v即可。

⑵如果結點v隻有左子樹Pl或隻有右子樹Pr，此時，當結點v是左孩子時，隻要令Pl或Pr為其雙親結點的左子樹即可；當結點v是右孩子時，隻要令Pl或Pr為其雙親結點的右子樹即可。

⑶如果結點v既有左子樹Pl又有右子樹Pr，此時，不可能進行如上簡單處理。為了在删除結點v之後，仍然保持二叉查找樹的特性，我們必須保證删除v之後，樹的中序序列必須仍然有序。為此，我們可以先用中序序列中結點v的前驅或後序替換v，然後删除其前驅或後序結點即可，此時v的前驅或後序結點必然是沒有右孩子或沒有左孩子的結點，其删除操作可以使用前面規定的方法完成。

動态查找----&gt;二叉查找樹(Binary Search Tree)

情況一舉例：由于結點2 是葉子結點，則直接摘除即可。

情況2舉例：例如在圖所示的二叉查找樹中删除結點3 和7，由于3 是左孩子，是以在删除結點3 之後，将其右子樹設為其父結點6 的左子樹即可；同樣，因為7 是右孩子，是以在删除結點7之後，将其右子樹設為其父結點6 的右子樹即可。

情況3舉例：例如在圖所示的樹中删除結點15，由于結點15既有左子樹又有右子樹，則此時，可以先找到其前驅結點13,并用13替換15，然後删除結點13即可。

public Object remove(Object ele) {
		BinTreeNode v = (BinTreeNode) binTSearch(root, ele);
		if (v == null)
			return null; // 查找失敗
		BinTreeNode del = null; // 待删結點
		BinTreeNode subT = null; // 待删結點的子樹
		if (!v.hasLChild() || !v.hasRChild()) // 确定待删結點
			del = v;
		else {
			del = getPredecessor(v);
			Object old = v.getData();
			v.setData(del.getData());
			del.setData(old);
		}
		// 此時待删結點隻有左子樹或右子樹
		if (del.hasLChild())
			subT = del.getLChild();
		else
			subT = del.getRChild();
		if (del == root) { // 若待删結點為根
			if (subT != null)
				subT.sever();   //斷開與父親的關系
			root = subT;
		} else if (subT != null) {
			// del為非葉子結點
			if (del.isLChild())
				del.getParent().setLChild(subT);
			else
				del.getParent().setRChild(subT);
		} else
			// del為葉子結點
			del.sever();
		return del.getData();
	}

将資料元素構造成二叉查找樹的優點：

①查找過程與順序結構有序表中的折半查找相似，查找效率高；

②中序周遊此二叉樹，将會得到一個關鍵字的有序序列（即實作了排序運算）；

③如果查找不成功，能夠友善地将被查元素插入到二叉樹的葉子結點上，而且插入或删除時隻需修改指針而不需移動元素。

package dsa.adt;

import dsa.adt.BinaryTreeLinked;
import dsa.adt.SearchTable;
import dsa.strategy.Strategy;
import dsa.strategy.DefaultStrategy;

public class BSTree extends BinaryTreeLinked implements SearchTable {
	protected BinTreeNode startBN; // 在AVL樹中重新平衡的起始結點

	// 構造方法
	public BSTree() {
		this(new DefaultStrategy());
	}

	public BSTree(Strategy strategy) {
		this.root = null;
		this.strategy = strategy;
		startBN = null;
	}

	// 查詢查找表目前的規模
	public int getSize() {
		return root == null ? 0 : root.getSize();
	}

	// 判斷查找表是否為空
	public boolean isEmpty() {
		return getSize() == 0;
	}

	// 傳回查找表中與元素ele關鍵字相同的元素位置；否則，傳回null
	public Node search(Object ele) {
		return binTSearch(root, ele);
	}

	private Node binTSearchRe(BinTreeNode rt, Object ele) {
		if (rt == null)
			return null;
		switch (strategy.compare(ele, rt.getData())) {
		case 0:
			return rt; // 等于
		case -1:
			return binTSearchRe(rt.getLChild(), ele);// 小于
		default:
			return binTSearchRe(rt.getRChild(), ele);// 大于
		}
	}

	private Node binTSearch(BinTreeNode rt, Object ele) {
		while (rt != null) {
			switch (strategy.compare(ele, rt.getData())) {
			case 0:
				return rt; // 等于
			case -1:
				rt = rt.getLChild();
				break;// 小于
			default:
				rt = rt.getRChild(); // 大于
			}
		}
		return null;
	}


	// 傳回所有關鍵字與元素ele相同的元素位置
	public Iterator searchAll(Object ele) {
		LinkedList list = new LinkedListDLNode();
		binTSearchAll(root, ele, list);
		return list.elements();
	}

	public void binTSearchAll(BinTreeNode rt, Object ele, LinkedList list) {
		if (rt == null)
			return;
		int comp = strategy.compare(ele, rt.getData());
		if (comp <= 0)
			binTSearchAll(rt.getLChild(), ele, list);
		if (comp == 0)
			list.insertLast(rt);
		if (comp >= 0)
			binTSearchAll(rt.getRChild(), ele, list);
	}

	// 按關鍵字插入元素ele
	public void insert(Object ele) {
		BinTreeNode p = null;
		BinTreeNode current = root;
		while (current != null) { // 找到待插入位置
			p = current;
			if (strategy.compare(ele, current.getData()) < 0)
				current = current.getLChild();
			else
				current = current.getRChild();
		}
		startBN = p; // 待平衡出發點
		if (p == null)
			root = new BinTreeNode(ele); // 樹為空
		else if (strategy.compare(ele, p.getData()) < 0)
			p.setLChild(new BinTreeNode(ele));
		else
			p.setRChild(new BinTreeNode(ele));
	}

	// 若查找表中存在與元素ele關鍵字相同元素，則删除一個并傳回；否則，傳回null
	public Object remove(Object ele) {
		BinTreeNode v = (BinTreeNode) binTSearch(root, ele);
		if (v == null)
			return null; // 查找失敗
		BinTreeNode del = null; // 待删結點
		BinTreeNode subT = null; // del的子樹
		if (!v.hasLChild() || !v.hasRChild()) // 确定待删結點
			del = v;
		else {
			del = getPredecessor(v);
			Object old = v.getData();
			v.setData(del.getData());
			del.setData(old);
		}
		startBN = del.getParent(); // 待平衡出發點
		// 此時待删結點隻有左子樹或右子樹
		if (del.hasLChild())
			subT = del.getLChild();
		else
			subT = del.getRChild();
		if (del == root) { // 若待删結點為根
			if (subT != null)
				subT.sever();
			root = subT;
		} else if (subT != null) {
			// del為非葉子結點
			if (del.isLChild())
				del.getParent().setLChild(subT);
			else
				del.getParent().setRChild(subT);
		} else
			// del為葉子結點
			del.sever();
		return del.getData();
	}

	// 傳回以v為根的二叉查找樹中最小(大)元素的位置
	public Node min(BinTreeNode v) {
		if (v != null)
			while (v.hasLChild())
				v = v.getLChild();
		return v;
	}

	public Node max(BinTreeNode v) {
		if (v != null)
			while (v.hasRChild())
				v = v.getRChild();
		return v;
	}

	// 傳回結點v在中序周遊序列中的前驅結點
	private BinTreeNode getPredecessor(BinTreeNode v) {
		if (v == null)
			return null;
		if (v.hasLChild())
			return (BinTreeNode) max(v.getLChild());
		while (v.isLChild())
			v = v.getParent();
		return v.getParent();
	}

	// 傳回結點v在中序周遊序列中的後續結點
	private BinTreeNode getSuccessor(BinTreeNode v) {
		if (v == null)
			return null;
		if (v.hasRChild())
			return (BinTreeNode) min(v.getRChild());
		while (v.isRChild())
			v = v.getParent();
		return v.getParent();
	}
}
結點 子樹 查找樹 中序周遊 删除結點
上一篇: LeetCode 110 Balanced Binary Tree（平衡二叉樹）（*）
下一篇: OBST（Optimal Binary Tree最優二叉搜尋樹）

繼續閱讀