Reference是19sp的lec slides。

Trees

首先引入abstract data type的概念，然后递进/逐步优化式地介绍三种树（BST, B-Tree, LLRB）。

笔记会分成两部分，这一篇只整理ADT和BST。

Abstract Data Types（ADT）

  • An abstract data type is defined by its operations, not implementations.
层级 例子
ADT Deque; DisjointSets
Implementations of ADT ArrayDeque, LinkedListDeque;
QuickFindDS, WeightedQuickUnionDS
Operations of ADT size(), get(), addFirst(Item x), etc.
  • Among the most important interfaces in the java.util library are those that extend the Collection interface. 关系如图。
    • List
    • Set
    • Map
image-20230327205326564
  • 这次关注的是两个tree相关的，TreeSet和TreeMap。

Binary Search Tree

BST缘起

问：怎么改进linkedlist，才能更加快速地完成搜索？

答案是：1）将entry point设置在中间而不是一端 2）从中间往两端 3）跳跃地遍历（如图）

image-20230327210424890

BST定义与性质

  • A binary search tree is a rooted binary tree with the BST property.
    • Tree properties:
      • A set of nodes,
      • One path between any two nodes
    • Rooted trees prop:
      • 除root外每个节点都只有一个父节点
      • root 一般画在最顶上
      • (for binary tree) 每个节点下只能有0/1/2个子节点
    • BST properties:
      • Ordering: Every key in the left subtree is less than X’s key. Every key in the right subtree is greater than X’s key
      • No duplicate keys allowed
image-20230327211546048

（路过一颗BST）

BST Operations

介绍BST的三个operation。

Search / Find

代码实现

（看代码更方便）对比searchKey和T.key–> 找到了！/ searchKey较小，search T.left / searchKey较大，search T.right

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

// reference: Algorithms, p.399
/** Return value associated with key in the subtree rooted at x;
 *  return null if key not present in subtree rooted at x.
 */
public Value get(Key key) {
	return get(root, key);
}

private Value get(Node x, Key key) { // helper
	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;
    }
}
Runtime Analysis
  • Worst case（茂密的二叉树.jpg）runtime：$\Theta(log{N})$
  • Tree Height：~$log_2{(N)}$
    • 这样考虑：每增加一层需要x2倍的节点

Insert

代码实现
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

/** Search for key. Update value if found; grow table if new. */
public void put(Key key, Value val) {
	root = put(root, key, val);
}
/** Change key’s value to val if key in subtree rooted at x.
 *  Otherwise, add new node to subtree associating key with val. */
private Node put(Node x, Key key, Value val) {
	if (x == null) return new Node(key, val, 1);
	int cmp = key.compareTo(x.key); // compare searchKey to curKey
	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;
}
Insert.2 Runtime Analysis

应该和find一样。

Delete

删除一共有三种情况：

  • 被删除的key没有子节点（–>see “glut”, 直接断开连接）

    image-20230327215529578

  • 被删除的key有1个子节点（–> see “flat”，把父节点的指针指向子节点）

    image-20230327215709610

  • 被删除的key有2个子节点（如图，找到predecessor或successor代替它的位置）

    image-20230327220006129
代码实现 p.411
 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

private Node min(Node x) {				// 找到x下最小的节点&其子节点
    if (x.left == null) return x;
    return min(x.left);
}

public void deleteMin() {				// 返回删除最小节点后的root
    root = deleteMin(root);
}

private Node deleteMin(Node x) {		// deleteMinHelper
    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);  
}

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 {								// 假设已经找到了Node P
       if (x.right == null) return x.left;  // 确认P有无sub-nodes，A)有0/1subnodes则返回它
       if (x.left == null) return x.right;
       Node t = x;				// B) 有2个nodes就需要调整一下树
       x = min(t.right);       	// 1. find the new substitute for the deleted node P
       x.right = deleteMin(t.right); // 2. connect the updated right nodes to the new P
       x.left = t.left;			// 3. connect the original left sub-nodes to the new P
       // 注意这里的顺序matters！
    }
    x.N = size(x.left) + size(x.right) + 1;
    return x;
}
Runtime

应该和前面是一个数量级，因为只是额外多了一些修改步骤。

BSTSet v.s. BSTMap

这部分是Lab9 BSTmap的引入。

BSTset和BSTmap结构相同（tree），区别是把每个node改成了用map来表示（如图）。

image-20230327215109239