关于数据结构和算法:cs61b-week8-Binary-Search-Tree

1.ADT 抽象数据类型

抽象数据类型就是只定义一些操作，而不去具体实现这些操作，例如双端队列(Deque)：

Deque ADT:
addFirst(Item x);
addLast(Item x);
boolean isEmpty();
int size();
printDeque();
Item removeFirst();
Item removeLast();
Item get(int index);

在 Project 1 中，Deque 只给了一些 API，而具体的实现代码交由咱们解决，由此产生了 ArrayDeque 和 LinkedListDeque。
还有就是之前课上讲的 List61B 接口，只申明一些办法，具体实现为 AList 和 SLList
精确来说,Java 的 interface 并不是 ADT，因为 interface 容许存在一些 default 的办法。

一个乏味的问题

现有一种抽象数据类型名为 GrabBag, 反对以下操作:

• insert(int x)向 GrabBag 中插入 x
• int remove(): 随机地从 GrabBag 中移除
• int sample(): 随机地从 GrabBag 中返回一个样本值
• in size()：返回 GrabBag 的元素个数

那么选取何种底层数据结构来实现 GrabBag 性能更佳?(数组 or 单链表)

答案是:数组
GrabBag 中最须要思考的操作就是随机地从 Grab 中删除一个元素，在数组中的实现为:

\(把数组最初一个元素 B 与待删除的元素 A 进行替换，而后指向数组开端的指针减一 \)

Map Example

简直 java.util library 中最重要的 interface 是 Collections，List,Set,Map 均继承了该接口:

Map 即 <Key,Value> 的映射，内置的 Map 有 HashMap 和 TreeMap, 上面是一个 HashMap 的应用例子，为列表中的单词与其呈现次数之间建设映射关系:

Map<String, Integer> m = new TreeMap<>();
String[] text = {"sumomo", "mo", "momo", "mo",
                 "momo", "no", "uchi"};
for (String s : text) {int currentCount = m.getOrDefault(s, 0);
   m.put(s, currentCount + 1);
}

其中,getOrDefault(Object key, V defaultValue)办法获取指定 key 对应对 value，如果找不到 key，则返回设置的默认值。

2.BST 的定义

BST(Binary Search Tree)二叉搜寻树的定义:
二叉搜寻树是一棵有根树，且满足 BST 性质:
树的所有左子树的结点的值 (key) 小于根结点，且所有右子树的结点的值 (key) 大于根节点
BST 的有序性必须满足：完整性，传递性和反对称性
给定两个 key p 和 q:

\(拥护称:p<q 或 q<p 必须有一个为真，p<q 则 q <p 不满足 \)
\(传递: 若 p <q，且 q <r，则 p <r \)

且二叉搜寻树中不能有反复的值，即不能呈现雷同的值(Josh 的说法)

3.BST 的搜寻

在二叉搜寻树中查问某个值:

• 如果未找到，返回 null
• 找到了，返回对应的 key

查问的路线即基于树的 BST 性质，对于通过的每个结点，将查问值与结点值进行比拟，
若小于以后结点值，则进入左子树持续搜寻
若大于以后结点值，则进入右子树进行搜寻，尔后递归进行。
伪代码:

static BST find(BST T, Key sk) {if (T == null)
      return null;
   if (sk.equals(T.key))
      return T;
   else if (sk ≺ T.key)
      return find(T.left, sk);
   else
      return find(T.right, sk);
}

工夫复杂度

对于一棵 bushy BST(浓密的二叉搜寻树)，当结点个数 N 为 2 的整次幂时，因为树的高度为 \(log_{2}N\), 其查问的工夫复杂度为 \(\Theta(logN) \)

4.BST 的插入

在二叉搜寻树中插入某个值:

• 先在 BST 中查问该值，如果找到了，do nothing

• 如果没找到

  • 申请一个新的结点，设置 key 为插入值
  • 建设与父节点的连贯(指针)

例如下图二叉搜寻树字母按字典排列，当初要向其中插入 eyes:

大于 dog–> 进入右子树 –> 小于 flat–> 进入左子树 –> 大于 elf–> 作为其右孩子

伪代码:

static BST insert(BST T, Key ik) {if (T == null)
    return new BST(ik);
  if (ik ≺ T.key)
    T.left = insert(T.left, ik);
  else if (ik ≻ T.key)
    T.right = insert(T.right, ik);
  return T;
}

5.BST 的删除

三种状况:

• 待删除结点无孩子
• 待删除结点有一个孩子
• 待删除结点有两个孩子

状况 1:
间接将其删除，随后被垃圾回收器回收

状况 2:
假如咱们要删除 flat，删除之后 肯定要放弃 BST 的性质, 那么将 flat 的父节点 dog 指向 flat 的子树 elf 即可

状况 3:

删除 k
如果对二叉搜寻树进行中序遍历，那么失去的后果就是一系列有序的字符，如图即 abdefgkmprvxyz
如果咱们称中序程序中某一结点的前一个结点为前驱，后一个结点为后继，那么就是相当于用前驱或后继替换该结点的过程
因为本次课并没有讲中序遍历，以 Josh 的定义:

• 前驱: 所有小于以后结点的最大值，k 的左子树中，最右端结点，g
• 后继：所有大于以后结点的最小值，k 的右子树中，最左端的结点，m

因而在 g 和 m 中二选一，将其作为新的根节点，替换掉 k 即可，假如咱们抉择 g，须要做的是:

1. 删除 g, 回到状况 2，将 g 的父亲 e 指向 g 的孩子 f
2. 将 k 替换为 g

有人可能有疑难，假如前驱或后继有两个孩子，那么删除操作会变得更加简单?
事实上，前驱或后继只有一个孩子或没有孩子，例如:

• 前驱至少只能有左孩子，假如前驱有右孩子，那么右孩子的值必定大于前驱且小于根结点，呈现矛盾
• 后继至少只能有右孩子，假如后继有左孩子，那么左孩子的值必定小于后继且大于根节点，违反定义

以上删除结点的办法被称作 Hibbard deletion

6.TreeMap 的例子

回忆一下后面咱们应用 Map 统计单词与其呈现次数之间的映射关系，应用 BST 也能够实现

这就相似于 TreeMap。