---
tags: summer 2018 cs61bl
---
# CS 61BL Week 4 Notes
Hi! Every week, I like to compile notes based off concepts that my tutees get confused about and good questions that they ask! If you’re already familiar with all the topics, check out the **Resources** section for practice problems or insights.

Also, if there’s anything that doesn’t make sense or seems confusing, feel free to shoot me an [email](mailto:[e-mail]).

## Table of Contents
[TOC]

## Data Structure Analysis
When considering what data structure to use for a program, we need to think of two things:
1. Purpose *(e.g. output in certain order, store keys and values, store unique values, etc.)*
2. Efficiency *(Consider drawbacks and performance)*

### Array
**Purpose:** All-purpose. Fast access due to indexing.

**Drawbacks:** Arrays are immutable and must be instantiated with a size. If we're inserting elements into an array and run out of space in the array, we have to create a new array with a larger size.

**Runtimes:**
* Lookup by index - O(1)
* Insert (with space) - O(1)
* Resize - O(N)
* Insert (without space) - O(N)

### Stack
**Purpose:** Outputs things in LIFO (Last In, First Out) Order. *(Think of stack as putting things into a container or test tube and trying to take them out)*

**Runtime:**
* Look at top - O(1)
* Remove top - O(1)

### Queue
**Purpose:** Order elements by when they were inserted (FIFO) *(Think of people waiting in line for a concert)*

**Runtime:**
* Look at first - O(1)
* Remove first - O(1)
* Insert at end - O(1)
* *Note: Based off DLList implementation*

### SLList
**Purpose:** Builds other data structures. Fast insertion.

**Drawbacks:** Slow access and search

**Runtime:**
* Search for item - O(N)
* Get item at index - O(N)
* Insertion (without searching) - O(1)
* Deletion (without searching) - O(1)

### DLList
**Purpose:** A more efficient implementation of SLList and fixes many of the performance issues that SLList has.

**Drawback:** More complicated and harder to implement

**Runtime:**
* Look at first/last - O(1)
* Look at some item - O(N)
* Insert at start/end - O(1)
* Insert somewhere in DLL - O(N)

### HashSet
**Purpose:** Ensure unique elements only, quickly check if item is in set.

**Drawback:** More complicated and harder to implement

**Runtime:**
* Insert - O(1)
* Delete - O(1)
* Lookup membership - O(1)

### HashMap
**Purpose**: Mapping one thing (key) to another.

**Runtime:**
* Insert - O(1)
* Delete - O(1)
* Lookup by Key - O(1)

### BST
**Purpose:** Looking for things. Keeping things in sorted order.

**Drawback:** Spindly BSTs lead to bad performance.

**Runtime:**
* Search for item: O(N) *(Remember spindly trees!)*
* O(lgN) insertion, deletion, check for membership.

### Heap
**Purpose:** Keeping track of minimum/maximum items.

**Runtime:**
* Bottom-up heapification - O(N)
* Top-down heapification - O(NlgN)
* Insertion - O(lgN)
* Deletion of max/min item - O(lgN)
* Peek of max/min item - O(1)

*Note: N represents the number of nodes. Also, don't worry about heaps until next Monday.*

## Trees
Trees are recursively defined data structures and look like the diagram below.

Trees, in general, do not have to retain any certain order or have a limited number of children. The structure above with 3 as the right child of 7 is still a tree.

When a tree is limited to at most 2 children, it is referred to as a **binary tree**.

If you want your binary tree to sort its nodes by some order, then we get a **binary search tree** **(BST)**. The tree below is an example of a BST.


**Insertion Into a BST:**
For BSTs, we usually insert items at leaves.
* If the item being inserted is **smaller** than the leaf, we assign it to be its **left child**.
* If the item being inserted is **greater** than the leaf, we assign it to be its **right child**.
* In CS61B, we usually do not account for duplicate nodes.

### Performance
BSTs are great for searching and insertion. However, they have a few drawbacks performance-wise (i.e. spindly trees). Spindly trees are trees with only right children or only left children. Searching for an item in a spindly tree can mean iterating through all possible nodes (*like a SLList*).

**Example of spindly tree:**

We make up for these performances issues by creating *balanced search trees*.

## Tree Traversals
Tree traversals are meant to describe when nodes in a binary tree are processed (one way of processing a node would be printing its value).

### Level Order
**Purpose:** Visit nodes by level, from top to bottom and left to right. Given the tree below, we could visit each node level by level.

**Result:** 1 2 7 5 9 3 4

### Depth First Traversal
**Purpose:** Visit deeper nodes first (before shallow nodes).

**PreOrder**
* Visit a node and then traverse its children.
* Usually in the order of **root, left, right**.

**Quick way of traversing nodes in PreOrder:**
1. Draw out the tree.
2. Draw a **left peg** for each node.
3. Draw a line around the entire tree structure.
4. Start from the root and follow the line left. Mark the node as visited when the the node's peg passes through the line.


**Result:** 1 2 5 9 7 3 4

**InOrder**
* Traverse left child, visit root, then traverse right child.
* Usually in the order of **left root right**.

**Quick way of traversing nodes in InOrder:**
Follow the same steps as the method for preorder, but assign **downward** pegs to each node.

**Result:** 5 2 9 1 7 4 3

**PostOrder**
* Traverse left, traverse right, then visit.
* Usually in the order of **left right root**.

**Quick way of traversing nodes in PostOrder:**


**The result:** 5 9 2 4 3 7 1

### Difference between Search and Traversal
During lab, you may have learned about **breadth first search** and **depth first search** and related them to **level order traversal** and **depth first traversal** respectively. Preorder, inorder, and postorder traversals all fit into the category of depth first search.

While they do act in a similar way to their counterpart, **searches** imply that you look through the tree for an arbitrary node. Meanwhile, **traversals** imply that you visit every node in a binary tree.

## Resources

### Practice Problems and Review
[Week 3 CS 61BL Notes](https://hackmd.io/s/BkFrjIb77): written by Tina on Generics, Comparators and Comparables, Iterables and Iterators, and Exceptions

[Week 4 Practice Problems & Resources](https://drive.google.com/drive/folders/113zG4_9jo655emP3Re3bP6voMN3-xQkf?usp=sharing): relevant problems compiled by Tina and sent to tutees. **Please check this out if you want extra practice problems for next week!**

### Midterm Review
[CSM MT2 Review Slides](https://docs.google.com/presentation/d/1QjR7Fki-0gjVlOH2aTWX6-AkPj_aHqIi0PUIQdKfnLw/edit#slide=id.g345868e7db_0_125): covers Asymptotics, Trees/BSTs/Self Balancing BST’s, Disjoint Sets, Heaps, Hashing, and ADT Selection Problems

[HKN MT2 Review Slides](https://docs.google.com/presentation/d/1bJhYwdF6H_AYe7Fs_bCMaNhwDL5BdXOHii3roC8WzvI/edit#slide=id.p7): covers Generics, Iterators and Iterables, Exceptions, Heaps, Asymptotic Analysis, Disjoint Sets, Hashing, Binary Search Tree, B-tree, Red black tree

### Disjoint Sets
[CSM Disjoint Sets Crib Sheet](https://d1b10bmlvqabco.cloudfront.net/attach/j9j0udrxjjp758/is6p8ixhpm47pr/jexi79yool1a/disjoint_sets_walkthrough_updated.pdf): contains disjoint set explanations and problems

### Trees
[CSM Trees Crib Sheet](https://d1b10bmlvqabco.cloudfront.net/attach/j9j0udrxjjp758/is6p8ixhpm47pr/jexhuf2m5jeq/asymptotics_edited.pdf): contains tree explanations and contains some problems

[Visualizer for Tree Traversals](http://www.cs.armstrong.edu/liang/animation/web/BST.html): builds trees and gives you the preorder, inorder, and postorder results

### Performance
[Big O Cheat Sheet](http://bigocheatsheet.com/): used as a reference for Data Structure Section

### Git Guides
[Short Guide](http://rogerdudler.github.io/git-guide/)
[Visual Guide](http://marklodato.github.io/visual-git-guide/index-en.html)
[Interactive Guide](http://git-school.github.io/visualizing-git/): really nice interactive visualizer for creating commits

### Data Structure Design
[When to Use Certain Data Structures](http://www.kartikkapur.com/documents/whentouse.pdf)