1/57
Why is a tree considered nonlinear?
They are not stored sequentially, but instead arranged on levels.
What is the height of a tree?
The maximum level of the tree, starting from 0.
For a tree, how do you calculate the maximum number of nodes given N levels?
2^N
For a tree, how do you calculate the minimum number of levels required to hold N nodes?
log2(N)
How many parents can a node of a tree have?
1
How many child nodes can a parent node have for a binary tree?
2
How many child nodes can a parent node have for a ternary tree?
3
How many child nodes can a parent node have for a N-nary tree?
N
What is a full tree?
A tree where every node either has 0 or 2 children.
What is a complete tree?
A tree where every level is filled (2 child nodes) except for the last. The last level may have 0 or 1 node.
What is a degenerate tree?
A tree with one node on each level except for the last. Can be skewed left or right.
What is a perfect tree?
A tree that is filled completely on every level except for the last level. The last level has no single nodes.
What is a balanced tree?
A tree with depth <= 1
What two trees can a perfect tree also be considered?
Complete and Full
What is depth?
The difference in levels along the left and right nodes. |height of the left nodes - height of right nodes|
What are the requirements for a binary search tree?
The left node contains values less than the parent node.
The right node contains values greater than the parent node.
The left and right nodes are binary search trees.
What are the basic operations of a binary search tree?
Size
Length
Insert
Delete
Search
Traverse
What is the order of In-Order Traversal?
Left, Root, Right. If each value is listed in order, it will be from least to greatest.
What is the order of Pre-Order Traversal?
Root, Left, Right
What is the order of Post-Order Traversal?
Left, Right, Root
Will binary search tree traversal ever start with a right node?
No
What are the steps for a binary search tree Search operation?
1.) Compare the target node to the current node starting from the root.
If matched, return target location.
If target < root, move to left subtree.
If target > rootm move to right subtree.
2.) Repeat recursively until matched.
3.) Return NULL if not found.
What are the steps for a binary search tree Insertion operation?
1.) Conduct a Search operation for a leaf node.
2.) The new node is added as a child of the leaf node.
What are the steps for a binary search tree Delete operation?
1.) Conduct a Search operation for the target.
2.)
If the target is a leaf node, deallocate (set to NULL).
If the target has 1 child node, replace the target node with the child node.
If the target has 2 child nodes, replace the target with the in-order successor and delete the original in-order successor,
What are the steps for finding an in-order successor?
1.) Reach a node in a tree
2.)
If right child ≠NULL, return leftmost child
If the node is the rightmost in the tree, return NULL
3.) Travel up tree and repeat until right child ≠NULL
What is a heap?
A type of binary tree with 2 more properties: shape and order
What are the operations of a heap?
Insertion, deletions, arrange
What is the insertion operation for a heap?
1.) Add the new node as a leaf node on the leftmost open spot.
2.) Is parent > new node?
3.) Is it the right order? If not, rearrange and loop to step 2.
What is the root node deletion operation for a heap?
1.) Swap with the leaf on the rightmost bottom level
2.) Delete original root.
3.) Child > new root?
4.) Is it the right order? If not, rearrange and loop to step 3
What is the term for the arrange method for a heap?
Heapify
What two kinds of heaps are there?
Minimum and maximum
What type of shape must a heap be?
A complete binary tree
How can heaps be represented as an array?
Set the root to index 0. Parent nodes are each element after.
Left children have an index of (2i + 1) and right children have an index of (2i + 2).
What is the process for a min heapify function?
1.) Is (index of left node) < size and (key of left node) < (key of right node)? Then smallest node = left node.
2.) Is (index of right node) < size and (key of right node) < (key of smallest node)? Then smallest node = right node.
3.) Is the smallest node ≠current node? Then swap current node with the smallest node and repeat for the smallest node.
What is a graph?
A non-linear data structure consisting of vertices and edges.
What is weight?
The cost associated with an edge.
Can a graph have a negative weight?
No. Not usually.
What is the “weight” for edges of unweighted graphs?
The same weight. Value doesn’t matter.
When is a graph considered connected?
When every vertex has some path between them..
When is a graph considered strongly connected?
When every vertex has a way of reaching every other vertex.
What is a directed graph?
A graph with directions defined for edges.
What is the equation for the maximum number of edges given vertices on a directed graph?
e <= v(v-1)
Given a directed graph with 4 vertices, what is the maximum number of edges the graph can have?
12
What is the equation for the maximum number of edges given vertices on a undirected graph?
e <= v(v-1)/2
Given a undirected graph with 4 vertices, what is the maximum number of edges the graph can have?
6
When is a graph sparse?
When it has too few edges.
When is a graph dense?
When it has too many edges.
What is a path?
A sequence of edges from a vertex to another/
What is the degree for a vertex?
The number of edges touching a vertex.
What is a simple path?
A path with no repeated vertices.
What is a trial path?
A path with no repeated edges.
When are 2 vertices considered neighbors/adjecent?
When they are connected by an edge.
What is the edge list representation of a graph?
A list of the origin and destination vertices side-by-side.
What is an adjacency matrix?
A 2D array of equal length, where the side length is the number of vertices. Edges that exist between the vertex on each axis is 1, and those that don’t are 0.
What is a weighted adjacency matrix?
A 2D array of equal length, where the side length is the number of vertices. Edges that exist between the vertex on each axis is the edge weight, and those that don’t are infinity.
What is an adjacency list?
A 2D list where each level of the list is an origin vertex, and the further across a level of the list correlates to a destination vertex. Edges across a list level BEFORE the final destination vertex are 0, and those that exist are 1.
Should a weighted adjacency matrix be used for dense graphs?
No. It has a time complexity of O(n²)
Where are edge lists commonly used?
Linked-list graphs.