Use LEFT and RIGHT arrow keys to navigate between flashcards;
Use UP and DOWN arrow keys to flip the card;
H to show hint;
A reads text to speech;
18 Cards in this Set
- Front
- Back
For singely linked list with a head pointer:
1. adding to the front: Big O( ? ) 2. adding to the end: Big O ( ? ) 3. remove from front: Big O ( ? ) 4. remove from end: Big O ( ? ) |
1. Big O(1)
2. Big O(n) 3. Big O(1) 4. Big O(n) |
|
Binary Tree:
A binary tree is an N-ary tree where N=___, and each child is considered to be either the left or the right child. |
2
|
|
Binary Search Tree:
- for every node X in the tree, the values of all the keys in the left subtree are __1___ than the key in X and the value of all the keys in the right subtree are ___2___ than the key in X. |
1. smaller
2. larger |
|
Perfect Binary Tree:
A perfect binary tree of height h>=0 is a binary tree with the following properties: 1. if h = 0, then there's only ____ node (i.e. left and right subtrees are empty) 2. otherwise (h>0), both the left and right subtrees are perfect binary trees. |
one,
finding height n = 2^(h+1) - 1 n + 1 = 2^(h+1) log base 2 (n+1) = h + 1 (log base 2 (n+1)) - 1 = h h is in theta(log n) |
|
TREE:
A node with degree zero is called a _____. |
leaf
|
|
TREE:
The _____ of a path P is k-1. |
length
|
|
An ___1___ tree T is a finite set of nodes, where:
1. either T is ___2___ 2. or T consists of a root, r, and exactly N distinct ___3___ trees. |
1. N-ary tree
2. empty 3. N-ary |
|
TREE:
The ____ of a node is the length of the longest path from r to a leaf. |
height
|
|
TREE:
A ____ in a tree T is defined as a non-empty sequence of nodes. P = { R1, R2,..., Rk} Ri must be the parent of R(i+1) ALL 1<=i<k |
path
|
|
TREE:
The ____ or depth of a node r is length of the path from the root to r. |
level
|
|
AVL trees are "almost balanced" BST's (binary search tree):
The height of an empty tree is __1___. An AVL tree is a BST in which all nodes have the AVL __2____. For every node n in a BST T, we say that n has the AVL property if the heights of it's left and right subtrees differ by at most __3___. |
1. -1
2. property 3. 1 height of tree is maintained at O(log n): yes balancing can't take longer than O(log n) time: yes |
|
TREE:
The height of a tree is the height of the ____. |
root
|
|
For doublely linked list with head and tail pointer:
1. remove from end: Big O(?) |
1. Big O(1)
|
|
For a STACK with head pointer:
1. add to front(push): Big O(?) 2. remove from front(pop): Big O(?) |
1. Big O(1)
2. Big O(1) |
|
deque (deck) Double-ended queue
common operations: 1. enqueue Front(I); 2. enqueue Back(I); 3. dequeue Front(); 4. dequeue Back(); 5. front(); 6. back(); |
1. add an item (I) to front
2. add an item (I) to back 3. remove an item from front 4. remove an item from back 5. return the item at front 6. return the item at back |
|
TREE:
The _____ of a node is the number of subtrees that it has. |
degree
|
|
For a singlely linked list with a head and tail pointer:
1. add to end: Big O( ? ) 2. remove from end: Big O( ? ) |
1. Big O(1)
2. Big O(n) |
|
A __1__ is a finite, non-empty set of nodes, T.
T={r} U T1 U T2 U ... U Tn (U = union) r is a node called the __2___ the remaining nodes are partitioned into subsets T1, T2,...,Tn each of which is a __3___. |
1. tree
2. root 3. tree |