CS61B(16): ADTs, Sets, Maps. BSTs

Posted on | In , |

This is the lecture note of CS61B - Lecture 16.

Abstrtact Data Types

Before explaining the term, first, let's review the difference between interfaces and their implementations we've learnt so far.

So, we can conclude that interface is abtract, and its implementations are distinct.

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

1
2
3
4
5
6
7
8
9
10
Deque ADT:

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

So, ArrayDeque and LinkedListDeque are implementations of the Deque ADT.

So, think about which implementation result in faster overall performance of stack? Linked List, or Array?

The answer is both of them are the same. Since no resizing for linked lists, so probably a lil faster.

Binary Search Trees

The proble here is that, even though this linked list set is ordered, we can't take advantage of it, searching is still slow.

One solution:

But this lecture's topic is BST, so we won't talk about the above method, we will talk about implementing BST by optimizting this ordered linked list set.

Do even better?

Definition

One consequence of these rules: No duplicate keys allowed!

Search Operation

The answer is A, and the height of the tree is log(N).

Insert Operation

Delete Operation

Deletion involves 3 Cases:

  • Deletion key has no children.
  • Deletion key has one child.

  • Deletion key has two children.

  • Case 1:

  • Case 2:
  • Case 3:

Summary

Finally, let's talk about how to use the knowledge we've learnt so far to implement Set and Map.

Tips for BST Lab