Study your flashcards anywhere!

Download the official Cram app for free >

  • Shuffle
    Toggle On
    Toggle Off
  • Alphabetize
    Toggle On
    Toggle Off
  • Front First
    Toggle On
    Toggle Off
  • Both Sides
    Toggle On
    Toggle Off
  • Read
    Toggle On
    Toggle 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


Play button


Play button




Click to flip

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.
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.
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)
A node with degree zero is called a _____.
The _____ of a path P is k-1.
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
The ____ of a node is the length of the longest path from r to a leaf.
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
The ____ or depth of a node r is length of the path from the root to r.
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
The height of a tree is the height of the ____.
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
The _____ of a node is the number of subtrees that it has.
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