树 (一)：二叉查找树

Posted on | Visitors:

写在前面

  • 本文内容来源于红色的《算法》一书，由于个人理解水平有限，故部分内容可能会出现错误，还请包涵

二叉查找树

二叉查找树高效地实现了符号表，结合了链表插入的灵活性和有序数组查找的高效性

基础知识

树由结点组成，结点包含的链接可以为空（null）或者指向其他节点

在二叉树中，除了根结点，每个结点只能有一个父节点，而且每个结点都只有左右两个链接，分别指向自己的左子结点和右子结点

尽管链接指向的是结点，但可以将每个链接视为指向了另一个二叉树，而这棵树的根结点就是被指向的结点

因此可将二叉树定义为一个空链接或是一个有左右两个链接的结点，每个链接都指向一颗（独立的）子二叉树

一颗二叉查找树（BST）是一颗二叉树，其中每个结点都含有一个 Comparable 的键（以及相关联的值）且每个结点的键都大于其左子树的任意结点的键而小于其右子树的任意结点的键

基本实现

1
2
3
4
5
6
public class BST<Key extends Comparable<Key>, Value>{
	
	// 指向树的根结点
	private Node root;

}

本文中所有实现均采用递归的方式，这样便于理解代码的工作方式，但实际情况中 BST 的实现往往是非递归的

Node

通过定义一个内部私有类来表示 BST 上的一个结点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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;
		
	}

}

变量 n 代表了以该结点为根结点的树中的结点总数

size

1
2
3
4
5
6
7
8
9
10
11
public int size() {

	return size(root);
	
}

private int size(Node x) {

	return x == null ? 0 : x.n;
	
}

对于二叉树中的任意结点，size(x) = size(x.left) + size(x.right) + 1

get

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public Value get(Key key) {

	return get(root, key);
	
}

private Value get(Node x, Key key) {

	if (x == null) return null;
	
	// 将待查找的 key 与当前 Node.key 进行比较
	int cmp = key.compareTo(x.key);
	
	// 若小于则在 Node 的左子树中进行查找
	if (cmp < 0) return get(x.left, key);
	
	// 若大于则在 Node 的右子树中进行查找
	else if (cmp > 0) return get(x.right, key);
	
	// 若等于则返回当前 Node.val
	else return x.val;
	
}

put

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public void put(Key key, Value val) {

	root = put(root, key, val);
	
}

private Node put(Node x, Key key, Value val) {

    // 若当前 Node 为 null，则在此处创建一个新的结点
	if (x==null) return new Node(key, val, 1);
	
	// 此过程同 get 类似
	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;
	
	// 更新 Node 保存的 size 信息
	x.n = size(x.left) + size(x.right) + 1;
	
	return x;
	
}

有序性相关的方法

BST 的一个重要特性就是能够保持键的有序性

min

由于在 BST 中每个结点的键都大于其左子树的任意结点的键，故 min() 的基本思路是：若根结点的左链接为空，则返回根结点，如果左链接不为空，则树中的最小键就是其左子树中的最小键

1
2
3
4
5
6
7
8
9
10
11
12
13
public Node min() {

	return min(root);
	
}

private Node min(Node x) {

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

max() 方法的基本思想与 min() 类似，故不作具体描述

floor

floor() 方法为返回树中结点键小于等于 key 的最大那个结点的 key，基本思路是：

  • 如果给定的 key 小于 BST 的 root.key，则 floor(key) 一定在 root.left 中
  • 如果给定的 key 大于 BST 的 root.key，则若 root.right 中存在小于等于 key 的结点时，floor(key) 才在 root.right 中，若不存在，则 floor(key) 等于 root.key
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public Key floor(Key key) {

	Node x = floor(root, key);
	
	return x == null ? null : x.key;
	
}

private Node floor(Node x, Key key) {

	if (x == null) return null;
	
	int cmp = key.compareTo(x.key);
	
	// floor(key) 在 Node.left 中
	if (cmp < 0) return floor(x.left, key);
	
	else if (cmp == 0) return x;
	
	Node t = floor(x.right, key);
	
	// 若返回的 t 为 null，则dai代表 Node.right 中没有小于等于 key 的结点
	return t == null ? x : t;
	
}

select

select(int k) 方法的作用是在树中找到排名为 k 的键（即树中有 k 个小于它的键），基本思路为

  • 若左子树中的结点数 t 大于 k，则在左子树中（递归地）查找排名为 k 的键
  • 若 t 等于 k，则返回根结点中的键
  • 若 t 小于 k，则在右子树中（递归地）查找排名为 k-t-1 的键
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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 (t > k) return select(x.left, k);
    
    else if (t < k) return select(x.right, k-t-1);
    
    else return x;
    
}

而 rank(Key key) 的作用是给定 key，得到其在整颗树中的排名，rank 方法是 select 方法的逆方法，不多作介绍

删除相关的方法

deleteMin

若根结点的左链接不为空，则 deleteMin(root) 相当于 deleteMin(root.left)；若为空，则根结点是整棵树中 key 最小的结点，直接返回 root.right 即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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;
	
}

deleteMax() 方法类似

delete

基本思路为：

  • 将 t 指向即将被删除的结点 x
  • 若 x.left 为空，则返回 x.right 即可
  • 若不为空，将 x 指向它的后继结点，即 min(t.right)
  • 将 x 的右链接指向 deleteMin(t.right)
  • 将 x 的左链接设为 t.left，返回 x
    而选取 x 的后继结点有两种选择，另外一种即为 max（t.left)
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    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);
    	
    	// 当前指向的 Node 即为要删除的结点
    	else {
    	
    		if (x.left == null) return x.right;
    		
    		else if (x.right == null) return x.left;
    		
    		else {
    		
    			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;
    	
    }

总结

BST 结合了链表插入灵活和有序数组查找高效的有点，但是 BST 依旧存在一定的缺陷，即 BST 的性能和其结点插入的顺序有关。在最坏的情况下，即插入的结点有序时，BST 相当于一个链表