Day 4 - Everything else

Bag

Collection that allows duplicates and has no order, unlike a set

Bag vs set

A set rejects duplicates, a bag allows them

Bag vs list

A list has order and index positions, a bag does not

Heap left child index

2 times i plus 1, where i is the parent index

Heap right child index

2 times i plus 2

Heap parent index

i minus 1, divided by 2 using integer division

Heap insertion process

Add the new element at the end of the array, then repeatedly swap it with its parent until the heap property is restored, called bubble up or sift up

Heap deletion process

Remove the root, move the last element into the root position, then repeatedly swap it with the smaller or larger child until the heap property is restored, called bubble down or sift down

Why the last heap element replaces the root

Keeps the heap a complete binary tree with no gaps

BST property

Every node's left subtree contains smaller values, right subtree contains larger values

BST search

Go left if the target is smaller, right if larger, repeat until found or a null is reached

BST insertion

Search for where the value would be, then insert it there as a new leaf

BST deletion with two children

Replace the node's value with its in order successor, the smallest value in the right subtree, then delete that successor

In order traversal

Left, node, right, visits nodes in sorted order

Pre order traversal

Node, left, right, useful for copying a tree

Post order traversal

Left, right, node, useful for deleting a tree

BST Big O balanced

O(log N) for search, insert, and delete

BST Big O worst case

O(N), happens when the tree is degenerate like a linked list

Stack push

Adds an item to the top of the stack

Stack pop

Removes and returns the item from the top of the stack

Queue enqueue

Adds an item to the back of the queue

Queue dequeue

Removes and returns the item from the front of the queue

Singly linked list node

Stores data and a reference to the next node only

Doubly linked list node

Stores data plus references to both the next and previous nodes

Linked list access Big O

O(N), no random access like an array

Linked list insertion at a known node

O(1), just pointer updates

Array vs linked list tradeoff

Arrays give fast random access but slow insertion and deletion, linked lists give fast insertion and deletion at a known point but slow access

Set union

All elements from both sets, no duplicates

Set intersection

Only elements that exist in both sets

Set difference

Elements in this set but not in the other set

Set filter

New set containing only elements that satisfy a condition

Set map

New set formed by applying a function to every element

Hash table Big O

O(1) average case for search, insert, and dele