C++高級數據結構之二叉查找樹怎么實現

本文小編為大家詳細介紹“C++高級數據結構之二叉查找樹怎么實現”，內容詳細，步驟清晰，細節處理妥當，希望這篇“C++高級數據結構之二叉查找樹怎么實現”文章能幫助大家解決疑惑，下面跟著小編的思路慢慢深入，一起來學習新知識吧。

高級數據結構（Ⅳ）二叉查找樹

基礎概念

此數據結構由結點組成，結點包含的鏈接可以為空（null）或者指向其他結點。在二叉樹中，每個結點只能有一個父結點（只有一個例外，也就是根結點，它沒有父結點），而且每個結點都只有左右兩個鏈接，分別指向自己的左子結點和右子結點。每個結點的兩個鏈接都指向了一棵獨立的子二叉樹或空鏈接。在二叉查找樹中，每個結點還包含了一個鍵和一個值，鍵之間也有順序之分以支持高校的查找。

定義：一棵二叉查找樹（BST）是一棵二叉樹，
其中每個結點都含有一個Comparable的鍵（以及相關聯的值）
且每個結點的鍵都大于其左子樹中的任意結點的鍵而小于右子樹的任意結點的鍵。

以int類型為鍵，string類型為值的二叉查找樹的API如下：

class BST<Key extends Comparable<Key>, Value>
-------------------------------------------------------------------------------------
Node root; 根結點
int size(Node x); 返回以結點x為根節點的子樹大小
Value get(Key key) 返回鍵key對應的值
void put(Key key, Value val) 插入鍵值對{key : val}
Key min() 返回最小鍵
Key max() 返回最大鍵
Key floor(Key key) 向下取整（返回小于等于key的最大值）
Key ceiling(Key key) 向上取整（返回大于等于key的最小值）
Key select(int k) 返回排名為k的鍵
int rank(Key key) 返回鍵key的排名
Iterable<Key> keys(Key lo, Key hi) 返回查找（返回指定范圍內的所有鍵值）
void deleteMin() 刪除最小鍵
void deleteMax() 刪除最大鍵
void delete (Key key) 刪除鍵key

基本實現

數據表示

我們嵌套定義一個私有類來表示二叉查找樹上的一個結點。每個結點都含有一個鍵、一個值、一條左鏈接、一條右鏈接和一個結點計數器。左鏈接指向一棵由小于該結點的所有鍵組成的二叉查找樹，右鏈接指向一棵由大于該結點的所有鍵組成的二叉查找樹。變量N給出了以該結點為根的子樹的結點總數。

實現：

class BST<Key extends Comparable<Key>, Value> {
private Node root; //二叉查找樹的根節點
private class Node{
private Key key; //鍵
private Value val; //值
private Node left, right; //指向子樹的鏈接
private int N; //以該結點為根的子樹中的結點總數
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;
}
}
}

一棵二叉查找樹代表了一組鍵（及其相應的值）的集合，而同一個集合可以用多棵不同的二叉查找樹表示。如果我們將一棵二叉查找樹的所有鍵投影到一條直線上，保證一個結點的左子樹中的鍵出現在它的左邊，右子樹中的鍵出現在它的右邊，那么我們一定可以得到一條有序的鍵列。

查找

一般來說，在符號表中查找一個鍵可能得到兩種結果。如果含有該鍵的結點存在于表中，我們的查找就命中了，然后返回相應的值。否則查找未命中（并返回null）。根據數據表示的遞歸結構我們馬上就能得到，在二叉查找樹中查找一個鍵的遞歸算法：如果樹是空的，則查找未命中；如果被查找的鍵和根結點的鍵相等，查找命中，否則我們就（遞歸地）在適當的子樹中繼續查找。如果被查找的鍵較小就選擇左子樹，較大則選擇右子樹。

/*** 查找 ***/
public Value get(Key key) {
return get(root, key);
}
private Value get(Node x, Key key) {
//在以x為根節點的子樹中查找并返回key所對應的值
//如果找不到則返回null
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;
}
}

插入

二叉查找樹插入的實現難度和查找差不多。如果樹是空的，就返回一個含有該鍵值對的新結點；如果被查找的鍵小于根結點的鍵，繼續在左子樹中搜索插入該鍵，否則在右子樹中插入該鍵。

/*** 插入 ***/
public void put(Key key, Value val) {
//查找key，找到則更新它的值，否則為它創建一個新的結點
root = put(root, key, val);
}
private Node put(Node x, Key key, Value val) {
//如果key存在于以x為根結點的子樹中則更新它的值；
//否則將以key和val為鍵值對的新結點插入到該子樹中
if (x == null) {
return new Node(key, val, 1);
}
int cmp = key.compareTo(x.key);
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;
}
x.N = size(x.left) + size(x.right) + 1;
return x;
}

有序性相關的方法

二叉查找樹得以廣泛應用的一個重要原因就是它能夠保持鍵的有序性，因此它可以作為實現有序符號表API中的眾多方法的基礎。這使得符號表的用例不僅能夠通過鍵還能通過鍵的相對順序來訪問鍵值對。

最小鍵和最大鍵

如果根節點的左鏈接為空，那么一棵二叉查找樹中最小的鍵就是根結點；如果左鏈接非空，那么樹中的最小鍵就是左子樹中的最小鍵，顯示可以由遞歸操作實現。

找出最大鍵的方法也是類似的，只不過是變為查找右子樹而已。

最小鍵

/*** 最小鍵 ***/
public Key min() {
if (root == null) {
return null;
}
return min(root).key;
}
private Node min(Node x) {
if (x.left == null) {
return x;
}
return min(x.left);
}

最大鍵

/*** 最大鍵 ***/
public Key max() {
if (root == null) {
return null;
}
return max(root).key;
}
private Node max(Node x) {
if (x.right == null) {
return x;
}
return max(x.right);
}

向上取整和向下取整

如果給定的鍵key小于二叉查找樹的根結點的鍵，那么小于等于key的最大鍵floor(key)一定在根結點的左子樹中；如果給定的鍵key大于二叉查找樹的根結點，那么只有當根結點右子樹中存在小于等于key的結點時，小于等于key的最大鍵才會出現在右子樹中，否則根結點就是小于等于key的最大鍵。這段描述說明了floor()方法的遞歸實現，同時也遞推地證明了它能夠計算出預期的結果。將“左”變為“右”（同時將小于變為大于）就能夠得到ceiling()的算法。

向下取整

/*** 向下取整 ***/
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);
if (cmp == 0) {
return x;
}
if (cmp < 0) {
return floor(x.left, key);
}
Node t = floor(x.right, key);
if (t != null) {
return t;
} else {
return x;
}
}

向上取整

/**** 向上取整 **/
public Key ceiling(Key key) {
Node x = ceiling(root, key);
if (x == null) {
return null;
}
return x.key;
}
private Node ceiling(Node x, Key key) {
if (x == null) {
return null;
}
int cmp = key.compareTo(x.key);
if (cmp == 0) {
return x;
}
if (cmp > 0) {
return ceiling(x.right, key);
}
Node t = ceiling(x.left, key);
if (t != null) {
return t;
} else {
return x;
}
}

選擇操作

/*** 選擇操作(返回排名為k的鍵) ***/
public Key select(int k) {
if (root == null) {
return null;
}
return select(root, k).key;
}
private Node select(Node x, int k) {
//返回排名為k結點
if (x == null) {
return null;
}
//注：書中此處為int t = size(x.left);
//個人覺得此處應該加上當前結點,即+1（若有建議歡迎指正）
int t = size(x.left) + 1;
if (t > k) {
return select(x.left, k);
} else if (t < k) {
return select(x.right, k - t - 1);
} else {
return x;
}
}

二叉查找樹的選擇操作和基于切分的數組選擇操作類似。我們在二叉查找樹中的每個結點中維護的子樹結點計數器變量N就是用來支持此操作的。

排名

/*** 返回給定鍵key的排名 ***/
public int rank(Key key) {
if (root == null) {
return 0;
}
return rank(root, key);
}
private int rank(Node x, Key key) {
//返回以x為根結點的子樹中小于x.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 {
//若返回給定鍵的排名，我認為這里要+1，不然可以在上面調用后的return語句后+1
//書中此處為return size(x.left)（若有建議歡迎指正）;
return size(x.left) + 1;
}
}

rank()方法是select()方法的逆方法，它會返回給定鍵的排名。它的實現和select()類似：如果給定的鍵和根結點的鍵相等，我們返回左子樹中的結點總數t；如果給定的鍵小于根結點，我們會返回該鍵在左子樹中的排名（遞歸計算）；如果給定的鍵大于根結點，我們會返回t+1（根結點）加上它在右子樹中的排名（遞歸計算）。

范圍查找

/*** 范圍查找（返回給定范圍內的所有鍵值） ***/
public Iterable<Key> keys() {
return keys(min(), max());
}

public Iterable<Key> keys(Key lo, Key hi) {
Queue<Key> queue = new LinkedList<Key>();
keys(root, queue, lo, hi);
return queue;
}
private void keys(Node x, Queue<Key> queue, Key lo, Key hi) {
if (x == null) {
return;
}
int cmplo = lo.compareTo(x.key);
int cmphi = hi.compareTo(x.key);
if (cmplo < 0) {
keys(x.left, queue, lo, hi);
}
if (cmplo <= 0 && cmphi >= 0) {
queue.offer(x.key);
}
if (cmphi > 0) {
keys(x.right, queue, lo, hi);
}
}

要實現能夠返回給定范圍鍵的keys()方法，我們首先需要一個遍歷二叉查找樹的基本方法，為中序遍歷。要說明這個方法，我們先看看如何能夠將二叉查找樹中的所有鍵按照順序打印出來。要做到這一點，我們應該先打印出根結點的 左子樹中的所有鍵（根據二叉查找樹的定義它們應該都小于根結點的鍵），然后打印出根結點的鍵，最后打印出根結點的右子樹中的所有鍵（根據二叉查找樹的定義它們應該都大于根結點的鍵）。

與刪除相關的方法

刪除最小鍵

二叉查找樹中最難實現的方法就是delete()方法，即從符號表中刪除一個鍵值對。在此之前，我們先考慮deleteMin()方法（刪除最小鍵所對應的鍵值對）。對于deleteMin()，我們要不斷深入根節點的左子樹直至遇見一個空鏈接，然后將指向該結點的右子樹（只需要在遞歸調用中返回它的右鏈接即可）。此時它會被垃圾收集器清理掉。我們給出的標準遞歸代碼在刪除結點后會正確地設置它的父結點的鏈接并更新它到根結點的路徑上的所有結點的計數器的值。

/*** 刪除最小鍵 ***/
public void deleteMin() {
if (root == null) {
return;
}
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;
}

刪除最大鍵

deletemax()方法的實現和deletemin()完全類似，相應地，只需刪除右子樹最右端結點，然后返回其最右端結點的左子樹即可。

/*** 刪除最大鍵 ***/
public void deleteMax() {
if (root == null) {
return;
}
deleteMax(root);
}
private Node deleteMax(Node x) {
if (x.right == null) {
return x.left;
}
x.right = deleteMax(x.right);
x.N = size(x.left) + size(x.right) + 1;
return x;
}

刪除操作

• 將指向即將被刪除的結點的鏈接保存為t;

• 將x指向它的后繼結點min(t.right);

• 將x的右鏈接（原本指向一棵所有結點都大于x.key的二叉查找樹）指向deleteMin(t.right)，也就是在刪除后所有結點仍然都大于x.key的子二叉查找樹；

• 將x的左鏈接（本為空）設為t.left（其下所有的鍵都小于被刪除的結點和它的后繼結點）。

實現：

/*** 刪除操作 ***/
public void delete (Key key) {
root = delete(root, key);
}

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.right == null) {
return x.left;
}
if (x.left == null) {
return x.right;
}
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;
}

性能分析

我見過二叉查找樹，但它的實現沒有使用遞歸。這兩種方式各有哪些優缺點？
答：一般來說，遞歸的實現更容易驗證其正確性，而非遞歸的實現效率更高。

完整代碼和測試

完整代碼

class BST<Key extends Comparable<Key>, Value> {
private Node root; //二叉查找樹的根節點
private class Node{
private Key key; //鍵
private Value val; //值
private Node left, right; //指向子樹的鏈接
private int N; //以該結點為根的子樹中的結點總數

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;
}
}

/*** 查找 ***/
public Value get(Key key) {
return get(root, key);
}

private Value get(Node x, Key key) {
//在以x為根節點的子樹中查找并返回key所對應的值
//如果找不到則返回null
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;
}
}

/*** 插入 ***/
public void put(Key key, Value val) {
//查找key，找到則更新它的值，否則為它創建一個新的結點
root = put(root, key, val);
}

private Node put(Node x, Key key, Value val) {
//如果key存在于以x為根結點的子樹中則更新它的值；
//否則將以key和val為鍵值對的新結點插入到該子樹中
if (x == null) {
return new Node(key, val, 1);
}
int cmp = key.compareTo(x.key);
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;
}
x.N = size(x.left) + size(x.right) + 1;
return x;
}

/*** 最小鍵 ***/
public Key min() {
if (root == null) {
return null;
}
return min(root).key;
}

private Node min(Node x) {
if (x.left == null) {
return x;
}
return min(x.left);
}

/*** 最大鍵 ***/
public Key max() {
if (root == null) {
return null;
}
return max(root).key;
}

private Node max(Node x) {
if (x.right == null) {
return x;
}
return max(x.right);
}

/*** 向下取整 ***/
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);
if (cmp == 0) {
return x;
}
if (cmp < 0) {
return floor(x.left, key);
}
Node t = floor(x.right, key);
if (t != null) {
return t;
} else {
return x;
}
}

/**** 向上取整 **/
public Key ceiling(Key key) {
Node x = ceiling(root, key);
if (x == null) {
return null;
}
return x.key;
}
private Node ceiling(Node x, Key key) {
if (x == null) {
return null;
}
int cmp = key.compareTo(x.key);
if (cmp == 0) {
return x;
}
if (cmp > 0) {
return ceiling(x.right, key);
}
Node t = ceiling(x.left, key);
if (t != null) {
return t;
} else {
return x;
}
}
/*** 選擇操作(返回排名為k的鍵) ***/
public Key select(int k) {
if (root == null) {
return null;
}
return select(root, k).key;
}
private Node select(Node x, int k) {
//返回排名為k結點
if (x == null) {
return null;
}
int t = size(x.left) + 1;
if (t > k) {
return select(x.left, k);
} else if (t < k) {
return select(x.right, k - t - 1);
} else {
return x;
}
}
/*** 返回給定鍵key的排名 ***/
public int rank(Key key) {
if (root == null) {
return 0;
}
return rank(root, key);
}

private int rank(Node x, Key key) {
//返回以x為根結點的子樹中小于x.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;
}
}

/*** 范圍查找（返回給定范圍內的所有鍵值） ***/
public Iterable<Key> keys() {
return keys(min(), max());
}

public Iterable<Key> keys(Key lo, Key hi) {
Queue<Key> queue = new LinkedList<Key>();
keys(root, queue, lo, hi);
return queue;
}

private void keys(Node x, Queue<Key> queue, Key lo, Key hi) {
if (x == null) {
return;
}
int cmplo = lo.compareTo(x.key);
int cmphi = hi.compareTo(x.key);
if (cmplo < 0) {
keys(x.left, queue, lo, hi);
}
if (cmplo <= 0 && cmphi >= 0) {
queue.offer(x.key);
}
if (cmphi > 0) {
keys(x.right, queue, lo, hi);
}
}

/*** 刪除最小鍵 ***/
public void deleteMin() {
if (root == null) {
return;
}
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 deleteMax() {
if (root == null) {
return;
}
deleteMax(root);
}
private Node deleteMax(Node x) {
if (x.right == null) {
return x.left;
}
x.right = deleteMax(x.right);
x.N = size(x.left) + size(x.right) + 1;
return x;
}

/*** 刪除操作 ***/
public void delete (Key key) {
root = delete(root, key);
}

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.right == null) {
return x.left;
}
if (x.left == null) {
return x.right;
}
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;
}
}

測試

int[] keys = {6, 5, 1, 3, 2, 4, 9, 7, 8, 10};
String[] values = {"F", "E", "A", "C", "B", "D", "I", "G", "H", "J"};

public class BSTTest {
public static void main(String[] args) {
int[] keys = {6, 5, 1, 3, 2, 4, 9, 7, 8, 10};
String[] values = {"F", "E", "A", "C", "B", "D", "I", "G", "H", "J"};

BST<Integer, String> bst = new BST<Integer, String>();
//構建樹
for (int i = 0; i < keys.length; i++) {
bst.put(keys[i], values[i]);
}

System.out.println("創建樹的鍵為：");
LinkedList<Integer> queue = (LinkedList<Integer>) bst.keys();
while (!queue.isEmpty()) {
System.out.print(queue.poll() + " ");
}

System.out.println("\n創建樹的大小為：" + bst.size());
System.out.println("鍵3所對應的值為：" + bst.get(3));
System.out.println("最小鍵為：" + bst.min());
System.out.println("最大鍵為: " + bst.max());
System.out.println("小于等于11的最大鍵是：" + bst.floor(11));
System.out.println("大于等于0的最小鍵是: " + bst.ceiling(0));
System.out.println("排名為5的鍵是：" + bst.select(5));
System.out.println("鍵7的排名是：" + bst.rank(7));

System.out.println("\n鍵值在3-8之間的鍵有：");
LinkedList<Integer> queue1 = (LinkedList<Integer>) bst.keys(3, 8);
while (!queue1.isEmpty()) {
System.out.print(queue1.poll() + " ");
}
System.out.println("\n刪除最小鍵和最大鍵后的鍵值為：");
bst.deleteMin();
bst.deleteMax();
LinkedList<Integer> queue2 = (LinkedList<Integer>) bst.keys();
while (!queue2.isEmpty()) {
System.out.print(queue2.poll() + " ");
}
System.out.println("\n刪除鍵4后的鍵值為： ");
bst.delete(4);
LinkedList<Integer> queue3 = (LinkedList<Integer>) bst.keys();
while (!queue3.isEmpty()) {
System.out.print(queue3.poll() + " ");
}
}
}

創建樹的鍵為：
1 2 3 4 5 6 7 8 9 10
創建樹的大小為：10
鍵3所對應的值為：C
最小鍵為：1
最大鍵為: 10
小于等于11的最大鍵是：10
大于等于0的最小鍵是: 1
排名為5的鍵是：5
鍵7的排名是：7
鍵值在3-8之間的鍵有：
3 4 5 6 7 8
刪除最小鍵和最大鍵后的鍵值為：
2 3 4 5 6 7 8 9
刪除鍵4后的鍵值為：
2 3 5 6 7 8 9
Process finished with exit code 0

讀到這里，這篇“C++高級數據結構之二叉查找樹怎么實現”文章已經介紹完畢，想要掌握這篇文章的知識點還需要大家自己動手實踐使用過才能領會，如果想了解更多相關內容的文章，歡迎關注億速云行業資訊頻道。