Study your flashcards anywhere!
Download the official Cram app for free >
 Shuffle
Toggle OnToggle Off
 Alphabetize
Toggle OnToggle Off
 Front First
Toggle OnToggle Off
 Both Sides
Toggle OnToggle Off
 Read
Toggle OnToggle Off
How to study your flashcards.
Right/Left arrow keys: Navigate between flashcards.right arrow keyleft arrow key
Up/Down arrow keys: Flip the card between the front and back.down keyup key
H key: Show hint (3rd side).h key
A key: Read text to speech.a key
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 Nary 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 k1. 
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. Nary tree
2. empty 3. Nary 

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 nonempty 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) Doubleended 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, nonempty 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 