If a binary tree is nonempty, it must have at least one node called ________.
the root node
A subtree is composed of ________.
a node in a binary tree and its children
A node in a binary tree can have two subtrees, called ________.
the left and right subtrees
The node of a binary tree has ________ links in it.
two
A node in a binary tree is called a leaf if ________.
it has no children
A node U is clled the parent of node V if ________.
there is a branch from U to V
What is a path from node A to node Y in a binary tree?
It is a sequence of pairs of nodes from node A to node Y, like A->B, B->C, ... X->Y.
What is the length of a path in a binary tree?
It is the number of branches on that path.
What is the level of a node on a binary tree?
It is the number of branches on the path from the root to that node.
What is the level of the root node of the binary tree?
0
What is the level of a child of the root node in a binary tree?
1
What is the height of a binary tree?
It is the number of nodes on the longest path from the root to a leaf.
What is the order in which nodes are traversed in an inorder traversal of a binary tree?
1) left subtree of the node
2) visit the node
3) right subtree of the node
What is the order in which nodes are traversed in an preorder traversal of a binary tree?
1) visit the node
2) left subtree of the node
3) right subtree of the node
What is the order in which nodes are traversed in an postorder traversal of a binary tree?
1) left subtree of the node
2) right subtree of the node
3) visit the node
What condition must be met for a binary tree to be a binary search tree?
In a binary search tree, the data in the root node must be larger than the data in every node in the left subtree and smaller than the data in every node in the right subtree. This condition must also be met for every subtree in the tree as well.
How do you delete a node from a binary search tree that has both left and right subtrees that are nonempty?
You have to locate the immediate predecessor of the node to be deleted (the largest value in the subtrees of the node to be deleted - it will always be the rightmost node in the left subtree of the node to be deleted.) Then the immediate predecessor's value replaces the value of the node to be deleted. If the node containing the immediate predecessor has nonempty left and right subtrees, the changes must "percolate".
What is a graph?
A graph is a finite nonempty set of vertices and a finite set of edges between those vertices.
What is a directed graph (or digraph)?
It is a graph in which the vertices are ordered pairs (indicating that travel between the vertices may not be allowed in both directions).
What is an undirected graph?
It is a graph in which (u,v) represents the same edge as (v,u). In this notation, a letter represents a vertex.
Define a subgraph.
A graph H is called a subgraph of a graph G if every vertex of H is a vertex of G and every edge in H is an edge in G.
With regard to matrices, what does it mean to say that two vertices are adjacent?
It means that there is an edge from one to another.
(T/F) An edge can be incident to only one vertex.
true. This is called a loop. Incident means "an endpoint of"
What is a path in a graph?
A path from one vertex to another in a graph is a sequence of vertices that are all connected with edges that form a connected path from the starting point to the ending point.
What
What are connected vertices?
Vertices are said to be connected if there is a path between them.
What is a simple path?
A simple path is a path in which all of the vertices, except possibly the first and last vertices, are distinct.
What is a cycle?
A cycle in a graph G is a simple path in which the first and last vertices are the same.
What does it mean if a graph is connected?
A graph is said to be connected if there is a path from any vertex to any other vertex.
If a graph is directed, it is important to know if, for two vertices u and v, u is ________ v AND if v is ________ u. They do not both have to be true or both false.
adjacent from, adjacent from
When is a graph said to be strongly connected?
A directed graph is strongly connected if there is a path between any two of its vertices. (If any two vertices are connected)
When is a graph said to be weakly connected?
A directed graph is said to be weakly connected if there is a path between any two vertices IF all edges are treated as being undirected.
What is an adjacency matrix?
An adjacency matrix is used to show which vertices are adjacent. If two vertices are adjacent, they are represented with a nonzero value; if they are not the entry is zero.
What is an adjacency list?
It is an alternative to an adjacency matrix. In this form, there is a list of adjacent nodes for each node in the graph.
The ________ traversal of a graph is similar to the preorder traversal of a binary tree.
depth first
The ________ traversal of a graph is similar to the level by level traversal of a binary tree.
breadth first
What is an articulation point?
A vertex v in a graph G is called an articulation point if its removal from G would cause the graph to be disconnected (if any vertices are only reachable by way of that vertex).
This is an important concept when working with networks.
What type of search can be used to find all of a graph's articulation points?
A depth first search.
On a visual representation of a graph, how can you identify articulation points?
Good question. Bottlenecks in traffic is a good description of these nodes.
What does the shortest path algorithm do?
It gives the shortest distance for a given node to every other node in the graph.
In a weighted graph, every edge ________.
has a non-negative weight
To calculate the weight of a path between two vertices, ________.
sum the weights of all of the edges on the path P.
What is a tree?
A tree is a simple graph such that if u and v are two vertices in T, there is a unique path from u to v.
What is a spanning tree?
A tree is a spanning tree of graph G if all of the vertices of G are in T.
What is a minimum spanning tree?
A minimum spanning tree of G is a spanning tree with the minimum weight.
How can you build a minimum spanning tree?
You build the tree iteratively by adding edges until a minimal spanning tree is obtained. At each iteration, a new edge that does not complete a cycle is added to the tree.
What are the 3 "basic" sorting methods?
selection sort
bubble sort
insertion sort
Name 3 more advanced sorting algorithms.
merge sort
quick sort
radix sort
Describe how selection sort works.
Find the smallest element in the list and put it in the sorted part of the list (the front). The element that was in that position is put where the smallest element was.
Describe how bubble sort works.
For each position in the list, compare that element and the next element. If they are out of order, swap them. Continue until the end of the list. This is one iteration.
Repeat until no exchanges are made in one whole iteration.
Describe how insertion sort works.
Consider the first element in the list to be sorted.
Get the first element in the unsorted portion of the list; put it into its position in the sorted portion of the list.
Repeat until no elements remain in the unsorted portion of the list.
Describe how merge sort works.
Divide the list in half repeatedly until each element is separate.
Merge each list back together in order, repeating all the way up to the original list.
Describe how quick sort works.
Partition the list into two lists by choosing a pivot point and sorting the remaining elements into elements smaller than pivot and elements larger than pivot.
Repeat on every sublist created until the entire list is sorted.
Describe how radix sort works.
Radix sort uses buckets.
Sort each element by its least significant digit into the appropriate buckets.
Using the order obtained in the first sort, sort the next least significant digit.
Repeat step 2 until all numbers have had all of their digits sorted.
What is a binary tree?
A tree that has a special node called the root node. Each node in the tree has two sets of nodes called the left subtree and the right subtree.
What is a binary insertion tree?
A tree that contains nodes that are ordered so that the data in the root node is larger than the data in any node in its left subtree and smaller than the data in any node in its right subtree.
What are the six orders ov traversal in binary trees?
preorder
postorder
inorder
and the reverse of each of these
A binary tree can be implemented as an ________ or a ________.
array, linked structured
Why is it preferable for a binary tree to be balanced?
A balanced tree can be searched more efficiently.
In an array implementation of a binary tree, how many dimensions should the array have?
one - so the formulas work
Where should the value stored in the root of a binary tree go in an array?
at index 0
If the index of a node is given by k, what is the formula for the index of its left child?
2k+1
If the index of a node is given by k, what is the formula for the index of its right child?
2k+2
If the index of a node is given by k, what is the formula for the index of its parent?
(k-1)/2
What is a heap?
A heap is a type of binary tree.
Name and describe the two types of heaps.
A min heap is structured so that a parent node is always <= its children REGARDLESS OF WHETHER THEY ARE LEFT OR RIGHT OF THE PARENT.
A max heap is structured so that a parent node is always >= its children REGARDLESS OF WHETHER THEY ARE LEFT OR RIGHT OF THE PARENT.
Which implementation is used for heaps?
Array implementation
How does heapsort work?
You build the heap, then pop items. The heap is effectively a priority queue which means it is very good at finding either the largest or smallest element.
If you want to find the smallest element build a max heap, then pop the items.
If you want to find the largest item, build a min heap, then pop the items.
A graph consists of a set of ________ and a set of ________.
vertices, edges
If the edges are ________ pairs of vertices, then the graph is ________.
ordered, directed
You can tell if a graph is directed because ________.
the edges have arrows
A graph can be represented using a/an ________.
adjacency matrix
An adjacency matrix will contain the same number of rows and columns as there are ________ in the graph.
vertices
Most graphs have ________ adjacency matrices.
sparse
Define a topological sort.
A topological sort of an acyclic directed graph orders the vertices so that if there is a path from the vertex u to vertex v, then vertex v appears after vertex u in the ordering. Example given in class: CS classes at SIUE.
What algorithm would you use to find the shortest path from a specified vertex to every other vertex in a directed unweighted graph?
Starting at the specified vertex, mark each adjacent vertex with its distance from the specified vertex and its predecessor until all vertices are marked. (Dijkstra's algorithm)
If a directed graph has a cycle, can it be sorted using a topological sort?
No.
(T/F) A topological sort will always yield the same sort order.
false
What is indegree?
The number of incoming connections a node has in a graph.