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。