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即的映射，内置的Map有HashMap和TreeMap,下面是一个HashMap的使用例子，为列表中的单词与其出现次数之间建立映射关系:

Map 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 且二叉搜索树中不能有重复的值，即不能出现相同的值(Josh的说法)
cs61b week8 -- Binary Search Tree

文章图片

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:
cs61b week8 -- Binary Search Tree

文章图片

大于dog-->进入右子树-->小于flat-->进入左子树-->大于elf-->作为其右孩子
cs61b week8 -- Binary Search Tree

文章图片

伪代码:

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的删除
三种情况: