What do we know

:cyclone: collections

Interfaces Hash table Implementations Resizable array Implementations Tree Implementations Linked list Implementations Hash table + Linked list Implementations
Set HashSet   TreeSet   LinkedHashSet
List   ArrayList   LinkedList  
Queue          
Deque   ArrayDeque   LinkedList  
Map HashMap   TreeMap   LinkedHashMap
  • This week: Trees
  • Next week: Hash
  • January: Map

Trees

Binary Search Trees

src: sedgewick

Definition. A binary search tree (BST) is a binary tree where each node has a Comparable key (and an associated value) and satisfies the restriction that the key in any node is larger than the keys in all nodes in that node’s left subtree and smaller than the keys in all nodes in that node’s right subtree.

<img src=http://algs4.cs.princeton.edu/32bst/images/binary-tree-anatomy.png /> <img src=http://algs4.cs.princeton.edu/32bst/images/bst-anatomy.png />

rules:

So good :heart: wikipedia

nice visualization : youtube

longer lesson: youtube

Balance

The bad tree:

unbalanced

how to balance

AVL trees: actual balance

Red-Black trees: fast almost balance

Java

java implementation

A word about comparators.

Assignment

clone the assignment repo: https://github.com/daltonschool/CS3A-bst.git

Due: 11/14

  1. write contains (4pts)
  2. write traverseInorder (4pts)
  3. write randomizedSort (5pts)
  4. write delete (5pts)
  5. improve insert to self balance using AVL (4pts)
  6. improve delete to self balancing using AVL (3pts)