查找算法
不管是之前學過的數(shù)組矩动、鏈表有巧、隊列、還是棧悲没，這些線性結構中篮迎，如果想在其中查找一個元素，效率是比較慢的示姿，只有甜橱，因此如果你的需求是實現(xiàn)快速查找，那么就需要新的算法設計栈戳，也需要新的數(shù)據(jù)結構支持岂傲。
還記得最先介紹的那個二分查找算法嗎？它的查找效率能夠達到 子檀，是不是還不錯镊掖？不過呢乃戈，它需要對數(shù)組事先排好序，而排序的成本是比較高的亩进。那么有沒有一個折中的辦法呢症虑？有，那就是接下來要給大家介紹的二叉搜索樹
1. 二叉搜索樹
二叉搜索樹（也稱二叉排序樹）是符合下面特征的二叉樹：
- 樹節(jié)點增加 key 屬性归薛，用來比較誰大誰小谍憔，key 不可以重復
-
對于任意一個樹節(jié)點，它的 key 比左子樹的 key 都大主籍，同時也比右子樹的 key 都小习贫，例如下圖所示
image.png
輕易看出要查找 7 （從根開始）自然就可應用二分查找算法，只需三次比較
- 與 4 比崇猫，較之大沈条，向右找
- 與 6 比，較之大诅炉，繼續(xù)向右找
- 與 7 比，找到
查找的時間復雜度與樹高相關屋厘，插入涕烧、刪除也是如此。
- 如果這棵樹長得還不賴（左右平衡）上圖汗洒，那么時間復雜度均是
- 當然议纯，這棵樹如果長得丑（左右高度相差過大）下圖，那么這時是最糟的情況溢谤，時間復雜度是
image.png
注：
- 二叉搜索樹 - 英文 binary search tree瞻凤，簡稱 BST
- 二叉排序樹 - 英文 binary ordered tree 或 binary sorted tree
定義節(jié)點
static class BSTNode {
int key; // 若希望任意類型作為 key, 則后續(xù)可以將其設計為 Comparable 接口
Object value;
BSTNode left;
BSTNode right;
public BSTNode(int key) {
this.key = key;
this.value = key;
}
public BSTNode(int key, Object value) {
this.key = key;
this.value = value;
}
public BSTNode(int key, Object value, BSTNode left, BSTNode right) {
this.key = key;
this.value = value;
this.left = left;
this.right = right;
}
}
查詢
遞歸實現(xiàn)
public Object get(int key) {
return doGet(root, key);
}
private Object doGet(BSTNode node, int key) {
if (node == null) {
return null; // 沒找到
}
if (key < node.key) {
return doGet(node.left, key); // 向左找
} else if (node.key < key) {
return doGet(node.right, key); // 向右找
} else {
return node.value; // 找到了
}
}
非遞歸實現(xiàn)
public Object get(int key) {
BSTNode node = root;
while (node != null) {
if (key < node.key) {
node = node.left;
} else if (node.key < key) {
node = node.right;
} else {
return node.value;
}
}
return null;
}
Comparable
如果希望讓除 int 外更多的類型能夠作為 key，一種方式是 key 必須實現(xiàn) Comparable 接口世杀。
public class BSTTree2<T extends Comparable<T>> {
static class BSTNode<T> {
T key; // 若希望任意類型作為 key, 則后續(xù)可以將其設計為 Comparable 接口
Object value;
BSTNode<T> left;
BSTNode<T> right;
public BSTNode(T key) {
this.key = key;
this.value = key;
}
public BSTNode(T key, Object value) {
this.key = key;
this.value = value;
}
public BSTNode(T key, Object value, BSTNode<T> left, BSTNode<T> right) {
this.key = key;
this.value = value;
this.left = left;
this.right = right;
}
}
BSTNode<T> root;
public Object get(T key) {
return doGet(root, key);
}
private Object doGet(BSTNode<T> node, T key) {
if (node == null) {
return null;
}
int result = node.key.compareTo(key);
if (result > 0) {
return doGet(node.left, key);
} else if (result < 0) {
return doGet(node.right, key);
} else {
return node.value;
}
}
}
還有一種做法不要求 key 實現(xiàn) Comparable 接口阀参，而是在構造 Tree 時把比較規(guī)則作為 Comparator 傳入，將來比較 key 大小時都調(diào)用此 Comparator 進行比較瞻坝，這種做法可以參考 Java 中的 java.util.TreeMap
最小
遞歸實現(xiàn)
public Object min() {
return doMin(root);
}
public Object doMin(BSTNode node) {
if (node == null) {
return null;
}
// 左邊已走到頭
if (node.left == null) {
return node.value;
}
return doMin(node.left);
}
非遞歸實現(xiàn)
public Object min() {
if (root == null) {
return null;
}
BSTNode p = root;
// 左邊未走到頭
while (p.left != null) {
p = p.left;
}
return p.value;
}
最大
遞歸實現(xiàn)
public Object max() {
return doMax(root);
}
public Object doMax(BSTNode node) {
if (node == null) {
return null;
}
// 右邊已走到頭
if (node.left == null) {
return node.value;
}
return doMin(node.right);
}
非遞歸實現(xiàn)
public Object max() {
if (root == null) {
return null;
}
BSTNode p = root;
// 右邊未走到頭
while (p.right != null) {
p = p.right;
}
return p.value;
}
新增
遞歸實現(xiàn)
public void put(int key, Object value) {
root = doPut(root, key, value);
}
private BSTNode doPut(BSTNode node, int key, Object value) {
if (node == null) {
return new BSTNode(key, value);
}
if (key < node.key) {
node.left = doPut(node.left, key, value);
} else if (node.key < key) {
node.right = doPut(node.right, key, value);
} else {
node.value = value;
}
return node;
}
- 若找到 key蛛壳，走 else 更新找到節(jié)點的值
- 若沒找到 key，走第一個 if所刀，創(chuàng)建并返回新節(jié)點
- 返回的新節(jié)點衙荐，作為上次遞歸時 node 的左孩子或右孩子
- 缺點是，會有很多不必要的賦值操作
非遞歸實現(xiàn)
public void put(int key, Object value) {
BSTNode node = root;
BSTNode parent = null;
while (node != null) {
parent = node;
if (key < node.key) {
node = node.left;
} else if (node.key < key) {
node = node.right;
} else {
// 1. key 存在則更新
node.value = value;
return;
}
}
// 2. key 不存在則新增
if (parent == null) {
root = new BSTNode(key, value);
} else if (key < parent.key) {
parent.left = new BSTNode(key, value);
} else {
parent.right = new BSTNode(key, value);
}
}
前驅后繼
image.png
一個節(jié)點的前驅（前任）節(jié)點是指比它小的節(jié)點中浮创，最大的那個
一個節(jié)點的后繼（后任）節(jié)點是指比它大的節(jié)點中忧吟，最小的那個
例如上圖中
- 1 沒有前驅，后繼是 2
- 2 前驅是 1斩披，后繼是 3
- 3 前驅是 2溜族，后繼是 4
- ...
簡單的辦法是中序遍歷讹俊，即可獲得排序結果，此時很容易找到前驅后繼
要效率更高斩祭，需要研究一下規(guī)律劣像，找前驅分成 2 種情況：
image.png
- 節(jié)點有左子樹，此時前驅節(jié)點就是左子樹的最大值摧玫，圖中屬于這種情況的有
- 2 的前驅是1
- 4 的前驅是 3
- 6 的前驅是 5
- 7 的前驅是 6
- 節(jié)點沒有左子樹耳奕，若離它最近的祖先自從左而來，此祖先即為前驅诬像，如
- 3 的祖先 2 自左而來屋群，前驅 2
- 5 的祖先 4 自左而來，前驅 4
- 8 的祖先 7 自左而來坏挠，前驅 7
- 1 沒有這樣的祖先芍躏，前驅 null
找后繼也分成 2 種情況
image.png
- 節(jié)點有右子樹，此時后繼節(jié)點即為右子樹的最小值降狠，如
- 2 的后繼 3
- 3 的后繼 4
- 5 的后繼 6
- 7 的后繼 8
- 節(jié)點沒有右子樹对竣，若離它最近的祖先自從右而來，此祖先即為后繼榜配，如
- 1 的祖先 2 自右而來否纬，后繼 2
- 4 的祖先 5 自右而來，后繼 5
- 6 的祖先 7 自右而來蛋褥，后繼 7
- 8 沒有這樣的祖先临燃，后繼 null
public Object predecessor(int key) {
BSTNode ancestorFromLeft = null;
BSTNode p = root;
while (p != null) {
if (key < p.key) {
p = p.left;
} else if (p.key < key) {
ancestorFromLeft = p;
p = p.right;
} else {
break;
}
}
if (p == null) {
return null;
}
// 情況1 - 有左孩子
if (p.left != null) {
return max(p.left);
}
// 情況2 - 有祖先自左而來
return ancestorFromLeft != null ? ancestorFromLeft.value : null;
}
public Object successor(int key) {
BSTNode ancestorFromRight = null;
BSTNode p = root;
while (p != null) {
if (key < p.key) {
ancestorFromRight = p;
p = p.left;
} else if (p.key < key) {
p = p.right;
} else {
break;
}
}
if (p == null) {
return null;
}
// 情況1 - 有右孩子
if (p.right != null) {
return min(p.right);
}
// 情況2 - 有祖先自右而來
return ancestorFromRight != null ? ancestorFromRight.value : null;
}
刪除
要刪除某節(jié)點（稱為 D），必須先找到被刪除節(jié)點的父節(jié)點烙心，這里稱為 Parent
- 刪除節(jié)點沒有左孩子膜廊，將右孩子托孤給 Parent
- 刪除節(jié)點沒有右孩子，將左孩子托孤給 Parent
- 刪除節(jié)點左右孩子都沒有淫茵，已經(jīng)被涵蓋在情況1爪瓜、情況2 當中，把 null 托孤給 Parent
- 刪除節(jié)點左右孩子都有痘昌，可以將它的后繼節(jié)點（稱為 S）托孤給 Parent钥勋，設 S 的父親為 SP，又分兩種情況
- SP 就是被刪除節(jié)點辆苔，此時 D 與 S 緊鄰算灸，只需將 S 托孤給 Parent
- SP 不是被刪除節(jié)點，此時 D 與 S 不相鄰驻啤，此時需要將 S 的后代托孤給 SP菲驴，再將 S 托孤給 Parent
非遞歸實現(xiàn)
/**
* <h3>根據(jù)關鍵字刪除</h3>
*
* @param key 關鍵字
* @return 被刪除關鍵字對應值
*/
public Object delete(int key) {
BSTNode p = root;
BSTNode parent = null;
while (p != null) {
if (key < p.key) {
parent = p;
p = p.left;
} else if (p.key < key) {
parent = p;
p = p.right;
} else {
break;
}
}
if (p == null) {
return null;
}
// 刪除操作
if (p.left == null) {
shift(parent, p, p.right); // 情況1
} else if (p.right == null) {
shift(parent, p, p.left); // 情況2
} else {
// 情況4
// 4.1 被刪除節(jié)點找后繼
BSTNode s = p.right;
BSTNode sParent = p; // 后繼父親
while (s.left != null) {
sParent = s;
s = s.left;
}
// 4.2 刪除和后繼不相鄰, 處理后繼的后事
if (sParent != p) {
shift(sParent, s, s.right); // 不可能有左孩子
s.right = p.right;
}
// 4.3 后繼取代被刪除節(jié)點
shift(parent, p, s);
s.left = p.left;
}
return p.value;
}
/**
* 托孤方法
*
* @param parent 被刪除節(jié)點的父親
* @param deleted 被刪除節(jié)點
* @param child 被頂上去的節(jié)點
*/
// 只考慮讓 n1父親的左或右孩子指向 n2, n1自己的左或右孩子并未在方法內(nèi)改變
private void shift(BSTNode parent, BSTNode deleted, BSTNode child) {
if (parent == null) {
root = child;
} else if (deleted == parent.left) {
parent.left = child;
} else {
parent.right = child;
}
}
遞歸實現(xiàn)
public Object delete(int key) {
ArrayList<Object> result = new ArrayList<>();
root = doDelete(root, key, result);
return result.isEmpty() ? null : result.get(0);
}
public BSTNode doDelete(BSTNode node, int key, ArrayList<Object> result) {
if (node == null) {
return null;
}
if (key < node.key) {
node.left = doDelete(node.left, key, result);
return node;
}
if (node.key < key) {
node.right = doDelete(node.right, key, result);
return node;
}
result.add(node.value);
if (node.left != null && node.right != null) {
BSTNode s = node.right;
while (s.left != null) {
s = s.left;
}
s.right = doDelete(node.right, s.key, new ArrayList<>());
s.left = node.left;
return s;
}
return node.left != null ? node.left : node.right;
}
說明
-
ArrayList<Object> result用來保存被刪除節(jié)點的值 - 第二、第三個 if 對應沒找到的情況骑冗，繼續(xù)遞歸查找和刪除赊瞬，注意后續(xù)的 doDelete 返回值代表刪剩下的先煎，因此需要更新
- 最后一個 return 對應刪除節(jié)點只有一個孩子的情況，返回那個不為空的孩子巧涧，待刪節(jié)點自己因沒有返回而被刪除
- 第四個 if 對應刪除節(jié)點有兩個孩子的情況薯蝎，此時需要找到后繼節(jié)點，并在待刪除節(jié)點的右子樹中刪掉后繼節(jié)點谤绳，最后用后繼節(jié)點替代掉待刪除節(jié)點返回占锯，別忘了改變后繼節(jié)點的左右指針
找小的
public List<Object> less(int key) {
ArrayList<Object> result = new ArrayList<>();
BSTNode p = root;
LinkedList<BSTNode> stack = new LinkedList<>();
while (p != null || !stack.isEmpty()) {
if (p != null) {
stack.push(p);
p = p.left;
} else {
BSTNode pop = stack.pop();
if (pop.key < key) {
result.add(pop.value);
} else {
break;
}
p = pop.right;
}
}
return result;
}
找大的
public List<Object> greater(int key) {
ArrayList<Object> result = new ArrayList<>();
BSTNode p = root;
LinkedList<BSTNode> stack = new LinkedList<>();
while (p != null || !stack.isEmpty()) {
if (p != null) {
stack.push(p);
p = p.left;
} else {
BSTNode pop = stack.pop();
if (pop.key > key) {
result.add(pop.value);
}
p = pop.right;
}
}
return result;
}
但這樣效率不高，可以用 RNL 遍歷
注：
- Pre-order, NLR
- In-order, LNR
- Post-order, LRN
- Reverse pre-order, NRL
- Reverse in-order, RNL
- Reverse post-order, RLN
public List<Object> greater(int key) {
ArrayList<Object> result = new ArrayList<>();
BSTNode p = root;
LinkedList<BSTNode> stack = new LinkedList<>();
while (p != null || !stack.isEmpty()) {
if (p != null) {
stack.push(p);
p = p.right;
} else {
BSTNode pop = stack.pop();
if (pop.key > key) {
result.add(pop.value);
} else {
break;
}
p = pop.left;
}
}
return result;
}
找之間
public List<Object> between(int key1, int key2) {
ArrayList<Object> result = new ArrayList<>();
BSTNode p = root;
LinkedList<BSTNode> stack = new LinkedList<>();
while (p != null || !stack.isEmpty()) {
if (p != null) {
stack.push(p);
p = p.left;
} else {
BSTNode pop = stack.pop();
if (pop.key >= key1 && pop.key <= key2) {
result.add(pop.value);
} else if (pop.key > key2) {
break;
}
p = pop.right;
}
}
return result;
}
