Graphs

Linked Data Structures

		desc
list-insert(L,x)	$O (1)$	insert x onto the front of the linked list
list-delete(L,x)	$O (1)$	delete element x from the linked list
list-search(L,k)	$O (n)$	returning a pointer to the first element with key k

A binary heap (or heap) is defined as a binary tree with two additional constraints:
- shape property: a binary heap is a complete binary tree
- heap property:
  - (max-heap) for every node $i$ other than the root, $A [parent (i)] \geq A [i]$ )
  - (min-heap) for every node $i$ other than the root, $A [parent (i)] \leq A [i]$ )
- Heaps are commonly implemented with an array $A$ of length $n$ .
  - In our implementation, the root of is in $A [1]$ , so
    - $parent (i) = ⌊ i /2 ⌋$
    - $left (i) = 2 i$
    - $right (i) = 2 i + 1$
    - the last index is $n$
  - (Alternatively, the root can be in $A [0]$ , so $left (i) = 2 i + 1$ , $right (i) = 2 i + 2$ , and $parent (i) = ⌊ (i - 1) /2 ⌋$ , and the last index is $n - 1$ )
Theorems:
- The index $i$ of the $k$ -greatest ( $k \neq = 1$ ) element in max-heap is $2 \leq i \leq 2^{k} - 1$
  - (the same for $k$ -smallest element in min-heap)
- (6.3-3)todo There are at most $⌈ n / 2^{h + 1} ⌉$ nodes of height $h$ in any $n$ -element heap

procedure (max heap)	Run Time
`heapify(A, i)`	$O (h)$	(the height of $A [i]$ is $h$ )
`max-heapify(A, i)`	$O (l g n)$
`build-max-heap(A)`	$O (n)$
`heap-maximum(A)`	$O (1)$	returns the element of $A$ with the largest key
`heap-extract-max(A)`	$O (l g n)$	remove max and retrun it
`heap-increase-key(A,i,key)`	$O (l g n)$	increases the value of $i$ to new value $k ey$ (larger or equal)
`max-heap-insert(A,key)`	$O (l g n)$	insert $k ey$ to $A$

in min-heap the procedures will be: min-heapify, build-min-heap, heap-minimum, heap-extract-min, heap-decrease-key, min-heap-insert

Type of: Binary Tree
Sorted data structure
all dynamic set operations take $O (h)$ time
Traversal (Inorder, preorder, and postorder) take $Θ (n)$ time
(12.4) The expected height of a randomly built BST on $n$ distinct keys is $O (l g n)$

Red-Black Tree is Binary Search Tree, which staify the Red-Black tree properties:
- Every node is either black or red
- The root is black
- Every leaf (NIL) is black
- if node red, then both of its children are black (thus, red nodes $<$ black nodes)
- For each node, all simple paths from the node to leaves have the same number of black nodes, (limiting h ???)
$bh (x)$ is the black-height of the node $x$ , which is the number of black nodes on any path from a node $x$ (not including) down to a leaf
$bh (T)$ is the black-height of a RB tree, which is the black-height of the root
(13.1) A red-black tree with $n$ internal nodes has height at most $2 l g (n + 1)$ . (which means that it’s approximatly balanced)
dynamic set operations take $O (l g n)$ time

(Theorem 14.1) Augmenting a red-black tree - Let $f$ be a field that augments a red-black tree $T$ of $n$ nodes, and suppose that the contents of $f$ for a node $x$ can be computed using only the information in nodes $x$ , $left [x]$ , and $right [x]$ , including $f [left [x]]$ and $f [right [x]]$ . Then, we can maintain the values of $f$ in all nodes of $T$ during insertion and deletion without asymptotically affecting the $O (l g n)$ performance of these operations.
order-statistic tree is RB Tree with additional node field: size.
- $OS-Select (x, i)$ returns a pointer to the node containing the $i$ th smallest key in the subtree rooted at $x$ . ( $O (l g n)$ (worst case))
- $OS-Rank (T, x)$ returns the position of $x$ in the linear order determined by an inorder tree walk of $T$ . ( $O (l g n)$ (worst case))