Ch 4: Trees and Graphs Flashcards
Trees:
Basic Types of Trees
- Tree
- N-ary Tree
- Binary Tree
- Binary Search Tree
- Self Balancing Binary Search Tree
- Red-Black Trees
- AVL Trees
- Self Balancing Binary Search Tree
- Binary Heaps
- Min Heap
- Max Heap
- Binary Search Tree
- Tries (Prefix Trees)
Graphs:
Types of graphs and related data structures
- Directed Graph
- Undirected Graph
- Cyclic Graph
- Acyclic Graph
Data Structures:
* Adjacency List
* Adjacency Matrix
Trees:
Tree Basic Description
- A data structure composed of Nodes which can contain any data type as values
- It is a type of Graph
- Each tree has a Root Node
- The Root Node has 0 or more Child Nodes
- Each Child Node has 0 or more Child Nodes
- Each Node may or may not have a pointer to it’s parent node
- The tree cannot contain Cycles
- Nodes may or may not be in a particular order
Trees:
Leaf Node
A node in a tree that has no children
Trees:
Root Node
The top-most node in a tree.
Trees:
Basic Tree Class Definition
class Tree {
class Node {
public String name;
public Node[] children;
}
public Node root;
}Trees:
Binary Tree basic description
A tree in which each node has up to 2 children
Trees:
N-ary Tree basic description
A tree in which each node has up to N children
Trees:
Binary Search Tree basic description
A Binary Tree in which every node fits a specific ordering property.
Some definitions allow duplicate values, some do not.
example:
For each node with value n,
All left descendants <= n
and
All right descendants > n
Trees:
Binary Tree Classifications
- Balanced or Unbalanced
- Completeness
- Full
- Perfect
Trees:
Binary Tree Properties:
Balanced
A tree is balanced when the left and right subtrees are very close to the same size.
* Don’t have to be exactly the same size
* Should be close enough that insert and find operations are O(logn)
* Not necessarily as balanced as it could be
Trees:
Common Types of Balanced Trees
- Red-Black Trees
- AVL Trees
Trees:
Binary Tree Properties:
Completeness
A Binary Tree is Complete when:
* Every level of the tree is full, except the bottom
* Last level can be incomplete, but must be filled from left to right
Trees:
Binary Tree Properties:
Fullness
A Binary Tree is Full when:
* Each Node has either 0 or 2 Children
Trees:
Binary Tree Properties:
Perfect Binary Tree Properties
A Perfect Binary Tree
is both Complete, and Full.
This is rare, as it can only exist when the tree contains exactly
2^k - 1 nodes,
where k = number of levels in the tree
Trees:
Binary Tree Traversal methods
- In-Order Traversal
- Pre-Order Traversal
- Post-Order Traversal
Trees:
Binary Tree
In-Order Traversal
Each node of the tree is visited recursively, from left to right
Visitation Order:
Left subtree -> Current Node -> Right Subtree
In a Binary Search Tree, where the nodes are organized in ascending order, the nodes are visited in ascending order
Trees:
Binary Tree
In-Order Traversal
pseudocode
void inOrderTraversal( TreeNode node) {
if (node != null) {
inOrderTraversal(node.left); // left child
visit(node); // current
inOrderTraversal(node.right); // right child
}
}
Trees:
Binary Tree
Pre-order Traversal
Each node of the tree is visited recursively
Current Node visited BEFORE it’s children.
Visitation Order:
Current Node -> Left Subtree -> Right Subtree
The Root Node is always the first node visited.
Trees:
Binary Tree
Pre-Order Traversal Pseudocode
void preOrderTraversal( TreeNode node) {
if (node != null) {
visit(node); // current
preOrderTraversal(node.left); // left child
preOrderTraversal(node.right); // right child
}
}
Trees:
Binary Tree
Post-Order Traversal
Each node is visited recursively,
Current Node is visited AFTER it’s children
Visitation Order:
Left Subtree -> Right Subtree -> Current Node
The Root Node is always the last node visited
Trees:
Binary Tree
Post-Order Traversal Pseudocode
void postOrderTraversal( TreeNode node) {
if (node != null) {
postOrderTraversal(node.left); // left child
postOrderTraversal(node.right); // right child
visit(node); // current
}
}
Trees:
Binary Heaps:
Min-Heap
- A complete binary tree where each node is smaller than it’s children.
- There is no inherent ordering between the two children, it depends on the order of insertion.
- The root node is the minimum element in the tree
Trees:
Binary Heaps:
Max-Heap
- A complete binary tree where each node is larger than it’s children.
- There is no inherent ordering between the two children, it depends on the order of insertion.
- The root node is the maximum element in the tree.
Trees:
Binary Heaps:
Key Operations
- Insert
- ExtractMin
or - ExtractMax
Trees:
Binary Heaps:
Insert Operation
- Insert new node at the bottom of the tree, in the rightmost position. This keeps the tree “complete”
- Move the node to it’s proper position by swapping it with it’s parent node until parent < current (Min Heap) or it is the root
Takes O(log n) time
Trees:
Binary Heaps:
Extract Minimum(or Max) Element
In a Min Heap, the minimum element is always at the root.
The trick is removing it and retaining the correct order.
- Swap the root node with the last element in the heap (bottom, right-most node). Save the old root.
- Fix the tree by “bubbling down” the new root; swap it with whichever of it’s children is the smallest. It should end up near the bottom of the heap
- Return the old root
This takes O(log n) time
Tries:
What is a Trie?
- A variant of an n-ary tree in which characters are stored at each node.
- Each node can have as many children as there are symbols in the alphabet being used
- Each path down the tree represents a complete word or sequence
- Uses either a “null node” or an internal flag in a regular node to indicate the end of a word
- Also called a “Prefix Tree”
Tries:
Uses of a Trie
Used to store entire languages for quick prefix lookups
Very useful for optimizing problems involving lists of “valid” words.
Can check if a word is valid in O(K) time, where K is the length of the string in question
Tries:
Validating a word:
Hashtable vs Trie
A hashtable is able to store a dictionary of words and check if a word is valid, but it can’t tell if a string is a PREFIX of any valid words.
A hashtable will have a similar lookup time of O(K), where K is the length of the string.
Graphs:
What is a graph?
A graph is a collection of nodes with connections(called edges) between some of them.
Graphs:
Relationship between Trees and Graphs
A Tree is simply one type of graph:
A connected graph that does not contain cycles.
Graphs:
Edges
Edges are the connections between nodes on a graph.
An edge can be:
- Directed: one-way connection between nodes
- Undirected: two-way connection between nodes
Graphs:
Directed Graph
A graph in which all edges are directed (one way)
Graphs:
Undirected Graph
A graph that contains undirected edges
Graphs:
Connected Graph
A Graph where a path exists between every pair of vertices(nodes)
Ex: A Tree is a type of Connected graph.
Graphs:
Cycle
A cycle is a set of nodes and edges where it is possible to revisit the same nodes over and over.
Graphs:
Acyclic Graph
A Graph that does NOT contain any cycles
Graphs:
Two common ways to represent graphs
- Adjacency List
- Adjacency Matrix
Graphs:
Adjacency List
The most common way to represent a graph.
Every vertex(or node) stores a list of pointers to adjacent vertices.
- An undirected edge (a, b) would be stored twice: once in node a, once in node b
Can be implemented with a Graph class and a Node class,
or
Can be implemented with an array or hashtable of lists, each entry
storing an adjacency list for a single node.
Implementing with Node classes is typically preferred.
Graphs:
Adjacency Matrix
An NxN boolean matrix (N = number of nodes)
(May also represent with integers instead of booleans)
- A true value at matrix[ i ][ j ] indicates an edge from node i to node j
- In an undirected graph, an adjacency matrix will be symmetric
(matrix[ i ][ j] == matrix[ j ][ i ]
Graphs:
Adjacency List
vs
Adjacency Matrix
- The same graph algorithms used on adjacency lists (Breadth First Search, etc) CAN be performed with adjacency matrices, but may be less efficient.
- An Adjacency List makes it easy to iterate through a node’s neighbors
- To identify neighbors in an Adjacency Matrix, you must iterate through all the nodes
Graph Search:
Two most common ways to search a graph
- Depth-First Search (DFS)
- Breadth-First Search (BFS)
Graph Search:
Depth First Search (DFS)
Basic idea
- Start at the “root” (or another arbitrarily selected node)
- Explore each branch COMPLETELY before moving on to the next branch.
- We go “deep” first, before we go “wide”
- Often preferred when wanting to visit every node in the graph
- A bit simpler than BFS
- Easy to implement recursively
- in a cyclic graph, must keep track of nodes visited to avoid getting stuck in a cycle
Graph Search:
Breadth First Search
Basic Idea
- Start at the “root” (or another arbitrary selected node)
- Explore each neighbor before going on to any of their children
- We go “wide” first, before we go “deep”
- Generally better for finding the shortest path between two nodes
- A bit more complicated than DFS
- Is NOT recursive
- Key Data Structure: Queue of nodes to visit
Graph Search:
Depth First Search
vs
Breadth First Search
DFS:
* simpler
* often preferred when visiting all nodes
BFS:
* more complex
* better at finding a path between two nodes
Graph Search:
Depth First Search
Pseudocode Steps
DepthFirstSearch(Node node){
if(node == null) return;
visit(node);
node.visited = true;
for each( Node n in node.adjacent) {
if(n.visited == false) DepthFirstSearch(n)
} }
DepthFirstSearch(root);
Graph Search:
Depth First Search:
What is the visitation order of this graph:
Graph Search:
Breadth First Search:
What is the visitation order of this graph?
Graph Search:
Breadth First Search Pseudocode
Graph Search:
Bidirectional Search
- Used to find the shortest path between two nodes
- Essentially, runs two simultaneous breadth-first searches, one from each node.
- When the searches collide, we have found a path
Graph Search:
Bidirectional Search compared to
Breadth First Search
Consider a graph where every node has 0 to k adjacent nodes
* the shortest path from node s to node t has a length of d
BFS:
* Search up to k nodes in first “level” of the search
* Search up to k^2 nodes in second level
* takes O(k^d) time to reach a path of length d
Bidirectional Search:
* Two searches collide after about d/2 “levels” ( at the midpoint of the path)
* Takes O(k^d/2) for each search, or O(2k^d/2)
Bidirectional Search is faster by a factor of k^d/2
Trees and Graphs:
Additional Topics related to this chapter
- Topological Sort
- Dijkstra’s Algorithm
- AVL Trees
- Red-Black Trees
