Data Structure Using Java

Front 1

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 ( ? )

Back 1

1. Big O(1)
2. Big O(n)
3. Big O(1)
4. Big O(n)

Front 2

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.

Back 2

2

Front 3

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.

Back 3

1. smaller
2. larger

Front 4

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.

Back 4

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)

Front 5

TREE:
A node with degree zero is called a _____.

Back 5

leaf

Front 6

TREE:
The _____ of a path P is k-1.

Back 6

length

Front 7

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.

Back 7

1. N-ary tree
2. empty
3. N-ary

Front 8

TREE:
The ____ of a node is the length of the longest path from r to a leaf.

Back 8

height

Front 9

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

Back 9

path

Front 10

TREE:
The ____ or depth of a node r is length of the path from the root to r.

Back 10

level

Front 11

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___.

Back 11

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

Front 12

TREE:
The height of a tree is the height of the ____.

Back 12

root

Front 13

For doublely linked list with head and tail pointer:
1. remove from end: Big O(?)

Back 13

1. Big O(1)

Front 14

For a STACK with head pointer:
1. add to front(push): Big O(?)
2. remove from front(pop): Big O(?)

Back 14

1. Big O(1)
2. Big O(1)

Front 15

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();

Back 15

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

Front 16

TREE:
The _____ of a node is the number of subtrees that it has.

Back 16

degree

Front 17

For a singlely linked list with a head and tail pointer:
1. add to end: Big O( ? )
2. remove from end: Big O( ? )

Back 17

1. Big O(1)
2. Big O(n)

Front 18

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___.

Back 18

1. tree
2. root
3. tree