一. 簡介
二叉查找樹（BST）是二叉樹的一個(gè)重要的應(yīng)用，它在二叉樹的基礎(chǔ)上加上了這樣的一個(gè)性質(zhì)：對于樹中的每一個(gè)節(jié)點(diǎn)來說钞螟，如果有左兒子的話，它的左兒子的值一定小于它本身的值谎碍，如果有右兒子的話鳞滨，它的右兒子的值一定大于它本身的值。
??我用一句話概括：左 < 中 < 右椿浓。 根據(jù)這個(gè)原理太援，我們可以推斷：BST的中序遍歷必定是嚴(yán)格遞增的。
二. 數(shù)據(jù)結(jié)構(gòu)
public class BST<T extends Comparable<T>> {
class Node {
private T data;
private Node left;
private Node right;
private int N;
public Node(T data, int N) {
this.data = data;
this.N = N;
this.left = null;
this.right = null;
}
}
private Node root;
public int size() {
return size(root);
}
private int size(Node n) {
if (n == null) return 0;
else return n.N;
}
public void put(T x) {
root = put(root, x);
}
public Node min() {
return min(root);
}
private Node min(Node n) {
if (n == null)
return null;
while (n.left != null) {
n = n.left;
}
return n;
}
private Node put(Node n, T x) {
if (n == null) return new Node(x, 1); //樹為空
int cmp = x.compareTo(n.data);
if (cmp < 0) {
n.left = put(n.left, x);
} else if (cmp > 0) {
n.right = put(n.right, x);
} else n.data = x;
n.N = 1 + size(n.left) + size(n.right);
return n;
}
public void delete(T x) {
if (x == null) throw new IllegalArgumentException("called delete() with a null key");
root = delete(root, x);
}
private Node delete(Node n, T x) {
if (n == null) return null;
int cmp = x.compareTo(n.data);
if (cmp < 0) {
n.left = delete(n.left, x);
} else if (cmp > 0) {
} else { //如果相等,此節(jié)點(diǎn)就是要?jiǎng)h除的節(jié)點(diǎn)
if (n.left == null)
return n.right; // 這里return扳碍，相當(dāng)于把當(dāng)前節(jié)點(diǎn)的直接右節(jié)點(diǎn)連到當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)
if (n.right == null)
return n.left; // 這里return提岔，相當(dāng)于把當(dāng)前節(jié)點(diǎn)的直接左節(jié)點(diǎn)連到當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)
// 有2個(gè)孩子
Node t = n;
n = min(t.right); // t的右子樹最小的節(jié)點(diǎn)替換這個(gè)被刪除的節(jié)點(diǎn)
n.right = deleteMin(t.right);
n.left = t.left;
}
n.N = size(n.left) + size(n.right) + 1;
return n;
}
private Node deleteMin(Node n) {
if (n.left == null) return n.right;
n.left = deleteMin(n.left);
n.N = size(n.left) + size(n.right) + 1;
return n;
}
}
- 插入:
??根據(jù)二叉查找樹的性質(zhì)，插入一個(gè)節(jié)點(diǎn)的時(shí)候笋敞，如果根節(jié)點(diǎn)為空碱蒙，就此節(jié)點(diǎn)作為根節(jié)點(diǎn)，如果根節(jié)點(diǎn)不為空夯巷，就要先和根節(jié)點(diǎn)比較赛惩，如果比根節(jié)點(diǎn)的值小，就插入到根節(jié)點(diǎn)的左子樹中趁餐，如果比根節(jié)點(diǎn)的值大就插入到根節(jié)點(diǎn)的右子樹中喷兼，如此遞歸下去，找到插入的位置后雷。重復(fù)節(jié)點(diǎn)用新值更新季惯。如圖1是一個(gè)插入的過程。
- 查找:
??查找的功能和插入差不多一樣臀突，按照插入那樣的方式遞歸下去勉抓，如果找到了，就返回這個(gè)節(jié)點(diǎn)的地址候学，如果沒有找到藕筋，就返回null。
3.刪除:
??1?? 首先先實(shí)現(xiàn)刪除這個(gè)樹中最小的元素: Node deleteMin(Node n){}函數(shù).
思路是:
- 一直找節(jié)點(diǎn)Node的左子樹梳码，直到找到當(dāng)前節(jié)點(diǎn)的左兒子為空(n.left == null,)
- 用找到的這個(gè)節(jié)點(diǎn)n的右兒子來替代它自己隐圾，這個(gè)節(jié)點(diǎn)n會沒有引用被gc掉
- 更新節(jié)點(diǎn)數(shù)目
2?? 然后刪除某個(gè)節(jié)點(diǎn):
??如果是葉子節(jié)點(diǎn)的話伍掀，直接刪除就可以了。比如圖3翎承，要?jiǎng)h除的是C節(jié)點(diǎn)硕盹，它是葉子節(jié)點(diǎn)符匾，那么很簡單把它父節(jié)點(diǎn)的引用置為null叨咖。
??如果只有一個(gè)孩子的話，就讓它的父親指向它的兒子啊胶，然后刪除這個(gè)節(jié)點(diǎn)甸各。如下圖:
刪除有兩個(gè)兒子的節(jié)點(diǎn)會比較復(fù)雜一些。一般的刪除策略是用其右子樹最小的數(shù)據(jù)代替該節(jié)點(diǎn)的數(shù)據(jù)并遞歸的刪除掉右子樹中最小數(shù)據(jù)的節(jié)點(diǎn)焰坪。因?yàn)橛易訕渲袛?shù)據(jù)最小的節(jié)點(diǎn)肯定沒有左兒子趣倾，所以刪除的時(shí)候容易一些。(比如刪除下圖的E節(jié)點(diǎn)某饰，那么會找到E節(jié)點(diǎn)右子樹中最小的節(jié)點(diǎn)來替代節(jié)點(diǎn)E儒恋，如圖是H節(jié)點(diǎn), 當(dāng)H代替完E節(jié)點(diǎn)，接下來調(diào)用deleteMin(E節(jié)點(diǎn))刪除H節(jié)點(diǎn))
三. 復(fù)雜度
平均復(fù)雜度 最壞情況復(fù)雜度
插入操作 O(logN) ??O(N)
查詢操作 O(logN) ??O(N)
刪除操作 O(logN) ??O(N)
如果BST不是平衡的樹黔漂，如下圖退化成list诫尽，那么最大復(fù)雜度O(N)。如插入有序序列(1, 2, 3, 4, 5)炬守，插入操作完成后的BST如下圖：
