二叉查找數(shù)
定義
一個(gè)二叉查找數(shù)（BST）是一顆二叉樹，其中每個(gè)結(jié)點(diǎn)都含有一個(gè)Comparable的鍵以及相關(guān)聯(lián)的值眉踱，且每個(gè)結(jié)點(diǎn)的鍵都大于其左子樹的任意結(jié)點(diǎn)的鍵田轧，小于其右子樹的任意結(jié)點(diǎn)的鍵
基本實(shí)現(xiàn)
- 數(shù)據(jù)表示
鍵+ 值+ 左鏈接+右鏈接+結(jié)點(diǎn)計(jì)數(shù)器 - 查找
如果樹是空的玩讳，則查找未命中；如果查找的鍵小于當(dāng)前結(jié)點(diǎn)的鍵议泵，則繼續(xù)查找其左子樹；如果查找的鍵大于當(dāng)前結(jié)點(diǎn)的鍵桃熄，則繼續(xù)查找其右子樹先口；如果查找的鍵等于當(dāng)前結(jié)點(diǎn)的鍵，則查找命中瞳收。 - 插入
如果樹是空的碉京，則返回一個(gè)含有該鍵值對(duì)的新結(jié)點(diǎn)。如果被查找的鍵小于根節(jié)點(diǎn)的鍵螟深，則繼續(xù)在左子樹中插入該鍵谐宙，否則在右子樹中插入該鍵。（記得更新節(jié)點(diǎn)計(jì)數(shù)器） - 性能分析
二叉查找數(shù)的算法的運(yùn)行時(shí)間依賴于樹的形狀界弧，而樹的形狀則取決于鍵的插入順序凡蜻。如果插入一個(gè)有序的鍵值對(duì)，則會(huì)出現(xiàn)最壞情況垢箕。
由N個(gè)隨機(jī)鍵構(gòu)造的二叉查找數(shù)划栓，查找命中和插入命中的平均所需比較次數(shù)為~2lnN(1.39lgN)。
二叉查找和插入的成本都是對(duì)數(shù)級(jí)別的（相比于二分查找的優(yōu)勢(shì)）
有序性相關(guān)的方法實(shí)現(xiàn)
- 最大鍵和最小鍵
最小鍵：如果左鏈接為空条获，最小鍵就是根節(jié)點(diǎn)忠荞；如果左鏈接非空，最小鍵就是左子樹的最小鍵
最大鍵：如果右鏈接為空帅掘，最大鍵就是根節(jié)點(diǎn)钻洒；如果右鏈接非空，最大鍵就是右子樹的最大鍵 - 向上取整和向下取整
floor(key) : key等于二叉樹的根節(jié)點(diǎn)锄开，返回根節(jié)點(diǎn)的值
2.1 key小于二叉樹的根節(jié)點(diǎn)，floor（key）一定在根節(jié)點(diǎn)的左子樹中
2.2 key大于二叉樹的根節(jié)點(diǎn)
2.2.1 右子樹中存在小于等于key的結(jié)點(diǎn)時(shí)称诗，floor（key）在右子樹中
2.2.2 否則返回根節(jié)點(diǎn) - 選擇操作
查找排名為k的鍵（樹中有k個(gè)小于它的節(jié)點(diǎn)）萍悴，假設(shè)左子樹的結(jié)點(diǎn)數(shù)為t
3.1 如果t > k 在左子樹中查找排名為k的鍵
3.2 如果t < k 在右子樹中查找排名為k-t-1的鍵
3.3 如果t=k 返回根節(jié)點(diǎn) - 排名
返回給定鍵在樹中的排名
4.1 如果給定的鍵小于根節(jié)點(diǎn)的鍵，則返回該鍵在左子樹中的排名
4.2 如果給定的鍵大于根節(jié)點(diǎn)的鍵寓免，則返回該鍵在右子樹中的排名+左子樹的節(jié)點(diǎn)個(gè)數(shù)+1
4.3 如果給定的鍵等于根節(jié)點(diǎn)的鍵癣诱，則返回左子樹的節(jié)點(diǎn)個(gè)數(shù) - 刪除最大值和最小值
deleteMin():如果左子樹不為空，則要?jiǎng)h除的節(jié)點(diǎn)在左子樹袜香；如果左子樹為空撕予，則返回該節(jié)點(diǎn)的右子樹 - 刪除操作
如果某個(gè)節(jié)點(diǎn)左右子樹都不為空，刪除節(jié)點(diǎn)以后蜈首，會(huì)產(chǎn)生兩個(gè)子樹而被刪除的節(jié)點(diǎn)的父節(jié)點(diǎn)只空出了一個(gè)鏈接实抡∏纺福可以使用被刪除節(jié)點(diǎn)的后繼節(jié)點(diǎn)（右子樹中的最小節(jié)點(diǎn)）補(bǔ)充它的位置。
6.1 將指向即將被刪除的結(jié)點(diǎn)的鏈接保存為t
6.2 將x指向它的后繼結(jié)點(diǎn)min（t.right）
6.3 將x的右鏈接指向deleteMin（t.right）
6.4 將x的左鏈接設(shè)為t.left
代碼實(shí)現(xiàn)
package edu.princeton.cs.algs4.chapter3;
/**
* 使用二叉查找樹實(shí)現(xiàn)的符號(hào)表
* Created by tianxianhu on 2017/3/6.
*/
public class BST<Key extends Comparable<Key>, Value> {
private Node root;
private class Node{
private Key key;
private Value val;
private Node left;
private Node right;
private int N; //維護(hù)一個(gè)當(dāng)前節(jié)點(diǎn)為根節(jié)點(diǎn)的節(jié)點(diǎn)總數(shù)量
public Node (Key key, Value val, int N) {
this.key = key;
this.val = val;
this.N = N;
}
}
public int size() {
return size(root);
}
private int size(Node x) {
if (x == null)
return 0;
else return x.N;
}
/**
* 獲取指定鍵的值吆寨，從根節(jié)點(diǎn)開始赏淌，比較鍵值
* 小于當(dāng)前鍵值則在左子樹中繼續(xù)尋找，大于則在右子樹中繼續(xù)尋找啄清，等于則返回當(dāng)前節(jié)點(diǎn)的值
* @param key
* @return
*/
public Value get(Key key) {
return get(root, key);
}
private Value get(Node x, Key key) {
if (x == null)
return null;
int cmp = key.compareTo(x.key);
if (cmp < 0) {
return get(x.left, key);
} else if (cmp > 0) {
return get(x.right, key);
} else {
return x.val;
}
}
/**
* 尋找key六水，找到則更新它的值，否則為它創(chuàng)建一個(gè)新節(jié)點(diǎn)辣卒，同時(shí)更新節(jié)點(diǎn)數(shù)量
* @param key
* @param val
* @return
*/
public Node put(Key key, Value val) {
return put(root, key, val);
}
private Node put(Node x, Key key, Value val) {
// 如果不存在掷贾，新建節(jié)點(diǎn)插入到字?jǐn)?shù)當(dāng)中
if (x == null)
return new Node(key, val, 1);
int cmp = key.compareTo(x.key);
// 不存在，則繼續(xù)在左/右子樹上尋找
if (cmp < 0) {
x.left = put(x.left, key, val);
} else if (cmp > 0) {
x.right = put(x.right, key, val);
} else {
// 存在荣茫，則更新值
x.val = val;
}
// 增加了節(jié)點(diǎn)想帅，更新每個(gè)子樹的數(shù)量
x.N = size(x.left) + size(x.right) + 1;
return x;
}
public Key min() {
return min(root).key;
}
private Node min(Node x) {
if (x.left == null)
return x;
return min(x.left);
}
/**
* 將要查詢的鍵值和根節(jié)點(diǎn)的鍵值進(jìn)行比較
* 1. 與根節(jié)點(diǎn)鍵值相等，返回當(dāng)前節(jié)點(diǎn)的鍵
* 1. 小于根節(jié)點(diǎn)鍵值计露，則在左子樹中繼續(xù)尋找
* 2. 大于根節(jié)點(diǎn)鍵值博脑，則在右子樹中尋找（可能在右子樹中，也可能是根節(jié)點(diǎn)）
* 2.1 如果右子樹中尋找返回null票罐，則返回根節(jié)點(diǎn)
* 2.2 如果在右子樹中尋找到叉趣，則返回找到的節(jié)點(diǎn)
* @param key
* @return
*/
public Key floor(Key key) {
Node x = floor(root, key);
if (x == null)
return null;
return x.key;
}
private Node floor(Node x, Key key) {
if (x == null)
return null;
int cmp = key.compareTo(x.key);
// 相等，返回當(dāng)前值
if (cmp == 0)
return x;
// 小于根節(jié)點(diǎn)该押，在左子樹當(dāng)中尋找
if (cmp < 0)
return floor(x.left, key);
// 大于根節(jié)點(diǎn)疗杉，在右子樹中尋找
Node t = floor(x.right, key);
// 存在則返回該節(jié)點(diǎn)，不存在則返回根節(jié)點(diǎn)
if (t != null)
return t;
else
return x;
}
/**
* 查詢排名為k的鍵（0-based）
* 計(jì)算做子樹的節(jié)點(diǎn)數(shù)量t蚕礼，與排名k進(jìn)行比較
* 1. 如果t>k, 就繼續(xù)在左子樹中查找排名為k的鍵
* 2. 如果k>t, 就在右子樹中查找排名為k-t-1的鍵
* 3. 如果k=t烟具， 就返回當(dāng)前節(jié)點(diǎn)
* @param k
* @return
*/
public Key select(int k) {
return select(root, k).key;
}
private Node select(Node x, int k) {
if (x == null)
return null;
int t = size(x.left);
if (k < t) {
return select(x.left, k);
} else if (t < k) {
return select(x.right, k - t - 1);
} else {
return x;
}
}
/**
* 查詢鍵key的排名
* 將要查詢的鍵與當(dāng)前的鍵值進(jìn)行比較
* 1.如果相等，則返回根節(jié)點(diǎn)左子樹的節(jié)點(diǎn)數(shù)
* 2.小于根節(jié)點(diǎn)奠蹬，則返回該鍵在左子樹中的排名
* 3.大于根節(jié)點(diǎn)朝聋，則返回size(x.left)+1+右子樹中的排名
* @param key
* @return
*/
public int rank(Key key) {
return rank(root, key);
}
private int rank(Node x, Key key) {
if (x == null)
return 0;
int cmp = key.compareTo(x.key);
if (cmp < 0)
return rank(x.left, key);
else if (cmp > 0)
return 1 + size(x.left) + rank(x.right, key);
else
return size(x.left);
}
/**
* 1.不斷檢索左子樹，直到遇見空的左子樹
* 2.返回該節(jié)點(diǎn)的右鏈接
* 3.遞歸調(diào)用結(jié)束后更新節(jié)點(diǎn)計(jì)數(shù)器
*/
public void deleteMin() {
root = deleteMin(root);
}
private Node deleteMin(Node x) {
if (x.left == null)
return x.right;
x.left = deleteMin(x.left);
x.N = size(x.left) + size(x.right) + 1;
return x;
}
public void delete(Key key) {
root = delete(root, key);
}
/**
* 1.尋找到要?jiǎng)h除節(jié)點(diǎn)t的后繼節(jié)點(diǎn)min(t.right)
* 2.將后繼節(jié)點(diǎn)x.right指向deleteMin(x.right),即刪除后繼節(jié)點(diǎn)以后的子樹囤躁，該子樹大于后繼節(jié)點(diǎn)
* 3.將后繼節(jié)點(diǎn)x.left指向t.left
* @param x
* @param key
* @return
*/
private Node delete(Node x, Key key) {
if (x == null)
return null;
int cmp = key.compareTo(x.key);
if (cmp < 0)
x.left = delete(x.left, key);
else if (cmp > 0)
x.right = delete(x.right, key);
else {
if (x.left == null)
return x.right;
if (x.right == null)
return x.left;
Node t = x;
x = min(t.right);
x.right = deleteMin(t.right);
x.left = t.left;
}
x.N = size(x.left) + size(x.right) + 1;
return x;
}
}
