1 Abstract Data Types

An Abstract Data Type (ADT) is defined only by its operations, not by its implementation.

For example in Project 1, we developed an ArrayDeque and a LinkedListDeque that had the same methods, but how those methods were written was very different. In this case, we say that ArrayDeque and LinkedListDeque are implementations of the Deque ADT.

From this description, we see that ADT’s and interfaces are somewhat related. Conceptually, Deque is an interface for which ArrayDeque and LinkedListDeque are its implementations. In code, in order to express this relationship, we have the ArrayDeque and LinkedListDeque classes inherit from the Deque interface.

Some commonly used ADT’s are:

Stacks: Structures that support last-in first-out retrieval of elements

  • push(int x): puts x on the top of the stack

  • int pop(): takes the element on the top of the stack

Lists: an ordered set of elements

  • add(int i): adds an element

  • int get(int i): gets element at index i

Sets: an unordered set of unique elements (no repeats)

  • add(int i): adds an element

  • contains(int i): returns a boolean for whether or not the set contains the value

Maps: set of key/value pairs

  • put(K key, V value): puts a key value pair into the map

  • V get(K key): gets the value corresponding to the key

最后三个都是一个叫做Collections的接口的子接口

ADT’s allow us to make use of object oriented programming in an efficient and elegant way. For example, you saw in Project 1 how you can use an ArrayDeque or a LinkedListArrayDeque interchangeably because they are both part of the Deque ADT.

Java的一个特点就是，它允许在一个更广的接口/ADT右侧指定实现，例如

1
Deque<Integer> d = new ArrayDeque<>();

2 Binary Search Trees

In binary search, we know the list is sorted, so we can use this information to narrow our search. First, we look at the middle element. If it is bigger than the element we are searching for, we look to the left of it. If it is smaller than the element we are searching for, we look to the right. We then look at the middle element of the respective halves and repeat the process until we find the element we are looking for (or don’t find it because the list doesn’t contain it).

But how do we run binary search for a linked list? We would have to traverse all the way to the middle in order to check the element there, which takes linear time just on its own!

直接偷懒（

2.1 BST Definitions

Trees are composed of nodes and edges that connect those nodes.

Constraint: there is only one path between any two nodes.

In some trees, we select a root node which is a node that has no parents.

A tree also has leaves, which are nodes with no children.

Binary Trees: in addition to the above requirements, also hold the binary property constraint. That is, each node has either 0, 1, or 2 children.

Binary Search Trees: in addition to all of the above requirements, also hold the property that For every node X in the tree:

  • Every key in the left subtree is less than X’s key.

  • Every key in the right subtree is greater than X’s key.

2.2 BST Operations

Search

1
2
3
4
5
6
7
8
9
10
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);
}

这里并不是简单的<，而是弯曲的小于号，凭我剩下不多的关于离散数学的知识，这应该是偏序关系，在我没搬运离散数学的笔记过来之前，可以先参考这篇笔记

如果这棵二叉树非常的完美，两边对称且都填满的那种(称为完全二叉树)，那么find的最坏情况下的复杂度是Θ(log N)\Theta (log\ N)

Insert
First, we search in the tree for the node. If we find it, then we don’t do anything. If we don’t find it, we will be at a leaf node already. At this point, we can just add the new element to either the left or right of the leaf, preserving the BST property.

1
2
3
4
5
6
7
8
9
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;
}

注意这里递归的应用，需要理解一下，要意识到最后的return T非常关键