目录

Binary Trees, Heaps, SkipLists and HashMaps

Gtx CS1332x II Notes

BST Introduction

Trees

树（Tree） 是一种链式，非线性的数据结构。在树中：

树中的一些术语示例：

树的特点

Binary Trees

二叉树的三个特点：

其节点的组成部分为：

Binary Tree 的形状分类
二叉树的遍历

二叉树的遍历是通过递归来进行的。总体的思路是不断的以先左后右的顺序遍历子树： 

public void traverse(Node node) {
    if(node != null) {
       taverse(node.left);
       taverse(node.right);
    }
}

Binarey Search Tree

BST 是 二叉树的一种。除此之外，BST 中内容都是有序的。排序的规则是：左子节点 < 父节点 < 右子节点。这个规则包含了子节点下面的所有子节点。比如下面的二叉树就不是一个有效的二叉树：



虽然右子节点 30 大于其父节点 10 满足定义，但对于其组父节点 20 来说，30 算作左子节点，不满足左子节点小于父节点的规定，因此该树不是有效的 BST。

BST in JAVA
搜索的方式
  • $n$ 个元素可以组成的 BST 种类等于其卡特兰数（Catalan Numbers），公式为 $\frac{2n!}{n!(n+1)!}$
  • $n$ 个元素可以组成的二叉树种类等于 $n!$ 乘以其卡特兰数。

Tree Traversals

Depth Traversals: Preorder

Preorder 会首先进行节点的操作，再进行递归 

preorder(Node node):
    if node is not null:
        look at the data first
        recurse left
        recurse right

Depth Traversals: Postorder

postorder(Node node):
    if node is not null:
        recurse left
        recurse right
        look at the data first

Depth Traversals: Inoder

inorder(Node node):
    if node is not null:
        recurse left
        look at the data first
        recurse right

Breadth (Iterative) Traversals

广度优先遍历 Breadth Traversals，又被称为 Levelorder，指以树中节点的层级来进行遍历。遍历从 0 层 的 root 开始，每行从左到右依次遍历，是一种很符合直觉的遍历。

实现上，Breadth Traversals 需要额外借助一个 Queue 来实现。其基本的原理为：

也就是每次父节点读取完毕时，都会将其清除出队列，将其子节点加入队列。如果父节点同层有其他节点，那么会接着处理其他同层节点。这样保证了父节点所有同层的节点处理完毕之后，才会接着进行下一层的遍历。 

levelorder():
Create Queue q
Add root to q
while q is not empty:
    Node curr = q.dequeue()
    if curr is not null:
        q.enqueue(curr.left)
        q.enqueue(curr.right)

BST Operations

Searching in a BST

BST 的平均 & 最好 & 最坏复杂度

BST 的复杂度：

  • 平均搜索复杂度 $O(log(n))$
  • worst case：degenerated tree，$O(n)$

Adding to a BST

Adding 的实现：Pointer Reinforcement

Adding 使用 Pointer Reinforcement 的策略：

Adding 的实现：细节

public void add (T data):
    // important step
    // the return data from the recursive method will be used to "reinforce" the tree construction
    root <- rAdd(root, data)

// method should be private
// return Node type for reconstruction
private Node rAdd(Node curr, T data):
    // base case
    // return the newAdded Node for reconstruction
    if curr == null:
        size++
        return new Node(data)
    // if the return data is less than the data in current node
    // the return Node should be the left child of the current node
    
    else if data < curr.data:
        curr.left <- rAdd(curr.left, data)
    // if the return data is geater than the data in current node
    // the return node should be the right child of the current node
    else if data > curr.data:
        curr.right <- rAdd(curr.right, data)
    
    // otherwise:
    // return the current node for the upperlevel reconstruction
    // if node is unchanged, it will be return directly
    // duplicate will be handled as well in this method
    return curr

Adding 的边界条件

Removing from a BST

从二叉搜索树中移除元素需要考虑三种情况：

原理：无子节点 & 单子节点的情况

这两种情况比较容易处理：

原理：双子节点的情况

这种情况需要详细的讨论。首先要明确的是，移除节点不能破坏 BST 的结构。也就是说，节点移除之后，BST 中节点的顺序性依然需要存在。因此，有必要思考通过什么样的手段来维持这种顺序性。

解决方案是使用 Predecessor 或者 Successor。

Predecessor（最大前继） 是指在 BST 中，比 root 小的节点中最大的一个节点；而 Successor（最大后继） 是指在 BST 中，比 root 大的节点中最小的一个节点。比如下面 BST 中的 21 和 30 就是 root 24 的最大前继和最小后继：

这种解决方案来源于一种很朴素的想法，化繁为简。首先可以明确的是，直接删除拥有两个子节点的节点，并且还要保证 BST 的结构不出问题，是非常困难的。但相比之下，删除只有一个子节点或者没有子节点的节点则非常简单。因此，相比直接删除节点，我们选择替换节点中的内容，而这正是使用 Predecessor 或 Successor 的精妙之处。

首先，如果希望替换掉 root，那么新的 root 的值必须符合 BST 的规则。也就是说，该 root 必须大于其左树所有节点，并小于其右树的所有节点。root 的 Predecessor 和 Successor 都满足该要求，而且是最符合直觉的两个选择。

其次，来关注一下 Predecessor 和 Successor 所处的位置。由于 Predecessor 大于所有左树中的节点，按照 BST 的排序方法，其只能处于左树的最右端。也就是说，该节点不能拥有右子节点，否则它就不是最大的那一个了。因此可以确认， Predecessor 所在的节点，只可能有两种情况：存在一个左子节点，或者本身就是 leaf。同理，Successor 处于右树的最左边，因此其只能拥有一个右子节点，或者其本身就是 leaf。

Predecessor 和 Successor 这两个特性使得我们可以将删除带两个孩子的节点的操作转变为删除单子节点 / Leaf 的操作。具体的步骤：

  1. 选择 Predecessor 或者 Successor 作为新的 root
  2. 交换 Predecessor 或者 Successor 与当前 root 中的值
  3. 此时需要移除的值已经存在于 Predecessor 或者 Successor 的位置，将其移除即可
实现 1：wrapper

本实现依然使用 point reinforcement 来重建 BST。不过相较于 adding, wrapper 还需要返回被删除的数据： 

//init dummy Node for the returning value
Node dummy <- new Node(1)
//reinforcement call
root <-rRemove(root, data, dummy)
return dummy.data
由于删除节点需要搜许是否存在该节点，因此需要如下的递归搜寻操作： 
//base case: data note foound
if curr == null:
     //do sth
//general recursion for searching the element in the subtrees
else if data < curr.data:
    curr.left <- rRemove(curr.left, data, dummy)
else if data > curr.data:
    curr.right<-rRemove(curr.right, data, dummy)
//data found case
else:
    //..do sth
//return the current node for reconstruction
return curr

实现 2：found cases

这一部分是实现之前 else 部分中的内容，也就是当存在被删除的内容时，应该如何去执行。我们按照之前的三种情况来实现： 

//caching the data of the current node to dummy
dummy.data <- curr.data
//downsize the tree
decrement size

/* CASES */
// no child case
// If a node has no children, removing it means setting its parent points to null
if 0 children:
    return null
// one child case
// If a node has one child, removing it means setting its parent points to its child (either left or right)
else if left child is non-null:
    return left child
else if right child is non-null:
    return right child
// two children case
else:
// A temporary node dummy2 is created for exchanging the roots and successors' values
Node dummy2 <- new Node(-1)
// find the successor and exchange the value
    // recounstuction will using the right child of the successor
    // assign successor's value to the current root 
curr.right <- removeSucessor(curr.right, dummy2)
    // saving the dummy2 data (root data) to the suceessor node, finish the exchange
curr.data <- dummy2.data

实现 3：helper method for successor

这一部分讨论 removeSucessor 的实现。该方法的功能有两点： 

private Node removeSucessor(Node curr, Node dummy):
    //if the sucesssor is found
    if curr.left == null:
        dummy.data <- curr.data
        return curr.right
    else:
        curr.left <- removeSucessor(curr.left, dummy)
    return curr

SkipLists

SkipList 是链表的一个变种。与链表不同，SkipList 是一种随机（基于概率的）数据结构。Skiplist 的主要优势是将链表中元素搜寻的平均复杂度从 $O(n)$ 降低到了 $O(log(n))$。

Skiplist 的结构

Skiplist 的构建

我们通过投掷硬币（Coin Toss）的方法来决定更高层的链表的元素为哪些。每添加一个元素，我们投掷一次硬币。如果掷出的硬币是正面（head），那么该元素就会被提升（poromote）到下一层；如果结果是反面（tail），则结束操作。之前我们提到过，理想状态下上层元素应该为下层元素的一半；这也很符合投硬币概率的直觉。

这样的创建方式使 skiplist 具有两个明显的特征：

Skiplist 的不同层级可以想象成起始点一样，终点一样，但停站不一样的公交路线：

  • 底层可以想象为每站都要停的公交车
  • 上层可以想象为只停其中某些站的快速公交车

需要注意的是，skiplist 中存在负/正 无穷的边界。实现上，该边界被称为 Phamtom nodes，用于作为 skiplist 的起始和终止的标记。

Skiplist 的搜索原理

搜索的算法如下：

  1. 从左上角的 phamtom node （head）开始
  2. 比较当前 data 是否与同层右边的数据
    1. 如果大于，则移动查找位置到当前比较的节点，并继续往右边查找
    2. 如果小于或是本层元素已经比较完毕，则往下层进行查找
  3. 重复以上的处理，直到达到最底层

下面是一个查找 50 的例子：

Adding in Skiplist

//wrapper
procedure Add(data)
    datalevels ← highest level the data resides on (based on coin toss)
    while current level < datalevels do
        create another level
    end while
    Add(data, datalevels, top-left phantom node, NULL)
end procedure
//helper
procedure Add(data, levels, node, upperNode)
    if node is not valid then
        return
    else
        while data > node.next.data do
             node ← node.next
        end while
        if node.level <= levels then
            Add new node containing data after node
            node.up ← upperNode
            upperNode ← newly-added node
        end if
        Add(data, levels, node.down, upperNode)
        end if
end procedure

Removing in Skiplist
  1. 搜索元素
    1. 如果元素不存在，则返回 Null
    2. 否则，以第一次搜索到的层级位置为基础，自上往下移除所有该元素。

Heaps

Heap（本课讨论的是 Binary Heap） 的本质是二叉完成树（Complete Tree）

与 BST 不同的是，Heap 只对父节点和子节点的大小有要求（对 sibling 没有限制）。根据子节点与父节点的大小关系，Heap 分为：

由于 Heap 的最大（最小）元素处于 root 的位置，我们通常使用其作为 Priority Queue 的实现基础。Heap 不是搜索型数据结构，在 Heap 中的元素查找复杂度为 $O(n)$。

Heap 在 Array 中的表现

Heap 使用 1-indexed 的方式来决定下标，即 index 0 不存储任何值。配合 levelorder 的排序方式，假设当前节点的 index 为 $n$，可以得到如下几个性质：

Heap Operations

根据 Heap 的定义，Heap 的操作通常包括添加与删除。操作过程需要遵循如下的两个要求：

这两个要求决定了 Heap 的添加与删除的特性：

Adding in heap

Adding 的操作分两个步骤：

Remove in heap

Remove 的操作也分两个步骤：

Up-heap 和 Down-heap 的复杂度均为 $O(log(n))$

The BuildHeap Algorithm

如果已知一个数组，希望将其生成 Heap 的话，有两种办法：

Down-heap 的生成原理和方式

Down-heap 的方式是指，从 heap 中末尾的元素所在子树开始重建；子树重建完毕之后，再基于该结果进行更大的子树重建，直到整个数组中的元素用完为止。这样做的好处是，Down-heap 的规模不会超过当前子树的规模。这样使得 down-heap 生成 heap 的方式的复杂度不会超过 $O(n)$。

按上述的思路，重建的父节点的遍历起始点是 size / 2，因为最后一个节点的 index 为 size。因此可以确认：

HashMaps

Maps

Map 是一种非顺序的数据结构。其元素由 Key 和与其绑定的 Value 组成。其中：

Map 的常见方法

HashMap

HashMap 是 Map 的一种。这种数据结构是基于数组实现的，并将数组中的元素（Key）与特定的数进行绑定，从而达到 $O(1)$ 查找的效果。该特定的数通过特定的 Hash Function 生成，其被称为 Hash Code。

HashCode Collision

Hash Code 有一个很重要的特性：

这是因为，理想状态下，HashCode 应该与 Key 一对一的关联。但实际上，这样的操作会造成大量的资源浪费。假设我们学院下存在 6 个部门，每个部门有一个 10 位长度的电话。理想情况下，我们应该使用电话号码作为与部门绑定的 Hash Code。但这样做相当于使用了 10 位长度的数组（组合为 10^9）的 Hash Code, 来表示仅仅 6 个 Key，这完全是得不偿失的。这也是为什么我们需要使用 Hash Function：尽量的使用最少的资源来绑定所有的 Key。

以上面的电话为例，一种可行的 Hash function 是，取电话的后 4 位来作为 Hash Code。这样之后，单个 Hashcode 的长度从 10 位变为了 4 位。当然，我们还可以做进一步的优化，比如将 4 位的 HashCode 末除 100，最后得到的结果只需要 2 位的数组就可以表示。这种进一步的优化过程被称为 Hash Compression。

不过，在上述的过程中，就可能会导致相同的 HashCode 指向不同的 Key。比如有两个电话：4048942261 / 4048940961。经过上述的第一步筛选后，其对应 HashCode 为 2261 / 0961；但再通过第二轮筛选后，结果都变成了 61。这种情况被称为 Hash Collision。通常情况下，这种情况是不可避免的。

减少 Hash Collsion 的策略

由于 Hash 的过程缩小了原有 Key 绑定的可选择范围，为了尽量避免出现 Hash Collision，最好的策略是对 Hash Code 数组的可选范围进行控制。一般来说，当出现了 Hash Coolsion 时，我们可以：

从设计上避免 Hash Collision

Hash Function 的选择在设计 Hashmap 中至关重要。一个好的 Hash Function 可以阻止 Hash Collision 的发生。

以 String Key 为例子：

$$ 1 \times 10^3 + 2 \times 10^2 + 1\times 10^1 + 2 \times 10 ^10 = 1212 $$

其他设计中的重点

首先，设计 hash function 必须满足两个条件：

其次，需要考虑 compression function 的设计：

最后，考虑 loading factror。loading factor 越低，出现 Collision 的几率就越低，但带来的资源消耗就越高。

External Caining

External Chaining 是处理 Collision 的一种方式。当 Entries 的 index 相同（ Hashcode 相同或是 compreesion 的结果相同）时：

比如课中的例子，压缩后 61 index 下的 Collision 会以如下方式存储：

Resizing

使用 External Chaining 管理 Collision 时，由于使用链表来存储 Index 相同的元素，在 Hash function 不是很好的情况下，有时候会导致某一个 index 下的链表特别长。链表的查询效率为 $O(n)$，因此我们需要在链表的长度达到一定的情况下进行 resize，来重新排列已经存储的元素。

实现上，是否 Resizing 也根据 Loading Factor 来决定。但 External Chaining 管理的 Hashmap 中，Size 不是单指 Backing array 中所占用的空间，而是要把所有的元素都计算进去。比如整个 Backing Array 的 Capacity 是 10，Backing Array 中只有 0 位置被占用了，但 index 0 下有 5 个元素，那么该 Hashmap 的 Loading Factor 就是 5 / 10 = 50%。可以看出来，External CHaining 下的 Hashmap, Loading Factor 是可以大于 1 的。

这种类型的 Hashmap, 其 Resizing 的过程是希望重新按新的 index 进行元素的分配，通过减少 Collision 链表的长度来达到更好的查询效率，而不是像 Vector 一样翻倍空间再拷贝。因此，Hashmap 的 Resizing 不涉及元素的拷贝，而是对原有的每个 index 下 所有 的元素，使用其 Hashcode % new BackingArray.length 来进行重新排列。

Linear Probing

与 Extenral Chaining 将元素锁定在对应的 Index 不同，Probing 是一种 Open addressing 的策略。Probing 在处理 Collision 的过程中，会按相应的策略将元素置于 backing Array 的其他位置。Linear Probing 指采用了如下策略的 Probing ：

put() in Linear Probing

查询空位（index 自增）的过程是一个循环的过程。最坏情况下，查询会进行 $n$ 次（如果元素为 $n$ 个）。如果起点不是 index 0，那么当查询达到 backing array 的末尾时，需要回滚到数组的前段继续进行查找。因此，如果令 $h$ 为当前递增的步数，那么 当前递增后的 index 的计算方式为： $$\texttt{index = (h + oriIndex) mod backingArray.length} $$

remove() in Linear Probing

移除 Hashmap 中的元素与 put() 的操作类似：

  1. 根据初始的 Index 计算 probe 的起始位置
  2. 将当前元素于需要被删除的元素相比
    1. 如果是，则删除
    2. 如果不是，则递增当前 Index 进行下一个位置的比较

但上述的步骤存在一个问题：假设存在多次 remove 的操作，如果第一次删除的位置处于第二次删除的位置之前，那么第二次的 probing 会在第一次删除的位置处中断，因为此处为空，已经没有元素可以进行相比。

为了解决这个问题，probing 的删除采用了软删除（sofe removal）的方式来实现。当删除一个元素时，我们会在其位置填充一个 DEL Marker，来体现此处曾经有元素存在，从而来保证 probing 的过程不被中断。

DEL marker 会给 put() 带来一些变化。假设我们向带有 DEL marker 的 hashmap 中添加元素，如果该元素在 DEL marker 之前都没有位置可以放置，那么该元素将存放于其遇到的第一个 DEL marker 处。

resizing with DEL markers

DEL marker 会带来一个性能上的缺点：其占据 probing 的位置，但又不会影响 loading factor。可以考虑这样一种特例：数组中只有最后一个元素存在，其前面所有的空位都被 DEL marker 填充。这导致了无论是什么样的操作，都必须遍历完整个 backing array ($O(n)$)。因此，当 resizing 的时候，任何之前 hashmap 中 DEL marker 都会被舍弃掉，不参与 rehash。

DEL marker 应该被考虑到 loading factor 中，且应该设置一个 removal 的上限来触发 resizing。

Quadratic Probing

Linear Probing 带来的问题被称为 primary clustering (turtling)。该问题指当 hash map 中连续的区域越来越大时（这是必然的，因为递增找空最终会将整个 hashmap 变为连续的区块。），我们每做一次 Probing 找空位都要跨越之前的连续区块。因此，我们需要一种更快的方式来找空位。

一种方式是将之前计算 index 中的 (h + oriIndex) % backArray.length 更改为：

$$ \texttt{index = (h² + oriIndex) mod backingArray.length} $$ 也就是 Probing 的实际次数会按照 Probing 的 step 的平方进行计算。我们将这样的 Probing 方式成为 Quadratic Probing。

secondary clustering

由于 Quadratic Probing 中 index 的计算方式是跳跃的，在某些情况下，该计算方式会导致 index 的计算结果一直在已经被占用的 index 之间来回横跳，从而导致 Infinite Probing。解决这个问题的两个策略：

Double Hashing

Double Hashing 通过综合使用 linear / quadratic Probing，在降低 probing clustering 的同时，尽量优化了性能。通常，Double Hashing 包含两个 hash function：

Linear Probing 可以被视作是 double hashing 的特殊形式。

Preformance

SkipList
Best Case Average Case Worst Case
Search$O(log(n))$$O(log(n))$$O(n)$
Add$O(log(n))$$O(log(n))$$O(n)$
Remove$O(log(n))$$O(log(n))$$O(n)$
Space$O(n)$$O(n)$$O(nlog(n))$
Heap
OperationBestAverageWorst
Find Min / max$O(1)$$O(1)$$O(1)$
Add$O(1)$$O(1)$$O(n)/O(log(n))*$
Remove Min/max$O(1)$$O(log(n))$$O(log(n))$
Aribitray Search/Remove$O(1)$$O(n)$$O(n)$
BuildHeap-$O(n)$$O(n)$$O(n)$
Space Complexity$O(n)$$O(n)$$O(n)$
HashMap
OperationBestAverageWorst
Put / Add New Key (Closed Addressing)$O(1)$$O(1)$$O(n)$
Put / Add New Key (Open Addressing)$O(1)$$O(1)$$O(n)^*$ / $O(n^2)$
Remove Key$O(1)$$O(1)$$O(n)$
Searching for a Key$O(1)$$O(1)$$O(n)$
Obtaining a KeySet$O(1)$$O(1)$$O(n)$
Obtaining a List of Values$O(1)$$O(1)$$O(n)$