COSC 3B

California	39512223
Texas	28995881
Florida	21477737
New York	19453561
Pennsylvania	12801989
Illinois	12671821
Ohio	11689100
Georgia	10617423
North Carolina	10488084
Michigan	9986857
New Jersey	8882190
Virginia	8535519
Washington	7614893
Arizona	7278717
Massachusetts	6892503
Tennessee	6829174
Indiana	6732219
Missouri	6137428
Maryland	6045680
Wisconsin	5822434
Colorado	5758736
Minnesota	5639632
South Carolina	5148714
Alabama	4903185
Louisiana	4648794
Kentucky	4467673
Oregon	4217737
Oklahoma	3956971
Connecticut	3565287
Utah	3205958
Puerto Rico	3193694
Iowa	3155070
Nevada	3080156
Arkansas	3017804
Mississippi	2976149
Kansas	2913314
New Mexico	2096829
Nebraska	1934408
West Virginia	1792147
Idaho	1787065
Hawaii	1415872
New Hampshire	1359711
Maine	1344212
Montana	1068778
Rhode Island	1059361
Delaware	973764
South Dakota	884659
North Dakota	762062
Alaska	731545
District of Columbia	705749
Vermont	623989
Wyoming	578759
Guam	168485
U.S. Virgin Islands	106235
Northern Mariana Islands	51433
American Samoa	49437

ASSIGNMENT 3B

Assignment 3B tests your knowledge of hashing structures (hash maps and hash sets). You can and should start
with the examples from the textbook/presentation and adapt them to the assignment at hand and use the
appropriate names and add the additional code and requirements bellow.

Design a program/project/driver class YourNameAssignment3B and the following classes (with exact1 names,
replace YourName with your actual first name or the name you go by):

Class Description
YourNameMap Program the complete version of the user-defined MyMap from Chapter 27.
YourNameHashMap Program the complete version of the user-defined HashMap from Chapter 27. Add

an additional more user-friendly YourNameOutput method that outputs the hash
map and uses the YourNameMap instead of the MyMap.

YourNameHashSet Program a complete version of the user-defined MyHashSet from Chapter 27. Add
an additional more user-friendly YourNameOutput method that outputs the hash
set.

YourNameAssignment3B
driver class main method

Read the data from the Assignment3BData.txt attached file (containing for each
line a name – representing the name of a US state/territory – and a number –
representing the state/territory’s 2019 estimated population) and build instances
of the user-defined YourNameHashMap from the names (states/territories) and
numbers (population) and YourNameHashSet from the names (states/territories)
and test/demonstrate ALL functionality/methods for both (including the
additional YourNameOutput methods)

Create a Microsoft Word screenshots document called YourNameAssignment3B-Screenshot x (replace
YourName with your actual name) that contains screenshots of the entire JAVA source code in the editor
window (for all the JAVA classes) and the entire output window (from the driver class). If the entire class JAVA
source code or the output does not fit in one screenshot or it is not easily readable, create multiple screenshots
and add them to the document.

Submit YourNameAssignment3B.java, YourNameMap.java, YourNameHashMap.java, and
YourNameHashSet.java Java source code files and YourNameAssignment3B-Screenshots x screenshots
document on eCampus under Assignment 3B. Do not archive the files (no ZIP, no RAR, etc.) or submit other file
formats. You are not going to earn any credit if the files are not named as requested.

1 Use the exact names (spelling, caps), parameters, returned values, functionality, and do not add or remove fields or methods. Yes, you may find
examples in the textbook with different names and cases and with other methods, but you will need to adapt them to have this exact names and
cases, to earn credit for the assignment.

Chapter28:

Graph

s and Applications

Dr. Adriana Badulescu

Objectives
▪ To model real-world problems using graphs and explain the Seven Bridges of

Königsberg problem (§28.1).

▪ To describe the graph terminologies: vertices, edges, simple graphs,

weighted/unweighted graphs, and directed/undirected graphs (§28.2).

▪ To represent vertices and edges using lists, edge arrays, edge objects, adjacency

matrices, and adjacency lists (§28.3).

▪ To model graphs using the Graph interface, the AbstractGraph class, and the

UnweightedGraph class (§28.4).

▪ To display graphs visually (§28.5).

▪ To represent the traversal of a graph using the AbstractGraph.Tree class (§28.6).

▪ To design and implement depth-first search (§28.7).

▪ To solve the connected-circle problem using depth-first search (§28.8).

▪ To design and implement breadth-first search (§28.9).

▪ To solve the nine-tail problem using breadth-first search (§28.10).

Modeling Using Graphs

Graph Animation

https://liveexample.pearsoncmg.com/dsanimation/GraphLearningTooleBook.html

Seven Bridges of Königsberg

Basic Graph Terminologies

What is a graph? G=(V, E)

Define a graph

Directed vs. undirected graphs

Weighted vs. unweighted graphs

Adjacent vertices

Incident

Degree

Neighbor

loop

Directed vs Undirected Graph

Peter

Cindy

Wendy

Mark

Jane

Basic Graph Terminologies
Parallel edge

Simple graph

Complete graph

Spanning tree

Representing Graphs

Representing Vertices

Representing Edges: Edge Array

Representing Edges: Edge Objects

Representing Edges: Adjacency Matrices

Representing Edges: Adjacency Lists

Representing Vertices

Representing Edges: Edge Array

int[][] edges = {{0, 1

}

, {0, 3} {0, 5}, {1, 0}, {1, 2}, … };

Representing Edges: Edge Object

Representing Edges: Adjacency Matrix

Representing Edges: Adjacency Vertex List

Representing Edges: Adjacency Edge List

Representing Adjacency Edge List Using ArrayList

Modeling Graphs

Graph WeightedGraph UnweightedGraph

«interface»
Graph

+getSize(): int

+getVertices(): List

+getVertex(index: int): V

+getIndex(v: V): int

+getNeighbors(index: int):

List

+getDegree(index: int): int

+printEdges(): void

+clear(): void

+addVertex(v: V): boolean

+addEdge(u: int, v: int): boolean

+addEdge(e: Edge): boolean

+remove(v: V): boolean

+remove(u: int, v: int): boolean

+dfs(v: int): UnWeightedGraph.SearchTree

+bfs(v: int): UnWeightedGraph.SearchTree

Returns the number of vertices in

the graph.

Returns the vertices in the graph.

Returns the vertex object for the specified vertex index.

Returns the index for the specified vertex.

Returns the neighbors of vertex with the specified index.

Returns the degree for a specified vertex index.

Prints the edges.

Clears the graph.

Returns true if v is added to the graph. Returns false if v

is already in the graph.

Adds an edge from u to v to the graph throws
IllegalArgumentException if u or v is invalid. Returns

true if the edge is added and false if (u, v) is already in

the graph.

Adds an edge into the adjacency edge list.

Removes a vertex from the graph.

Removes an edge from the graph.

Obtains a depth-first search tree starting from v.

Obtains a breadth-first search tree starting from v.

.

UnweightedGraph

#vertices: List

#neighbors: List>

+UnweightedGraph()

+UnweightedGraph(vertices: V[], edges:

int[][])

+UnweightedGraph(vertices: List,

edges: List)

+UnweightedGraph(edges: int[][],

numberOfVertices: int)

+UnweightedGraph(edges: List,

numberOfVertices: int)

Vertices in the graph.

Neighbors for each vertex in the graph.

Constructs an empty graph.

Constructs a graph with the specified edges and vertices

stored in arrays.

Constructs a graph with the specified edges and vertices

stored in lists.

Constructs a graph with the specified edges in an array

and the integer vertices 1, 2, ….

Constructs a graph with the specified edges in a list and

the integer vertices 1, 2, ….

The generic type V is the type for vertices.

Test

Graph

UnweightedGraph

Graph
Graph

https://liveexample.pearsoncmg.com/html/TestGraph.html

https://liveexample.pearsoncmg.com/html/UnweightedGraph.html

https://liveexample.pearsoncmg.com/html/Graph.html

Graph Visualization

DisplayUSMapGraphView Displayable

https://liveexample.pearsoncmg.com/html/DisplayUSMap.html

https://liveexample.pearsoncmg.com/html/GraphView.html

https://liveexample.pearsoncmg.com/html/Displayable.html

Graph Traversals
Depth-first search and breadth-first search
Both traversals result in a spanning tree, which can be
modeled using a class.

UnweightedGraph.SearchTree

-root: int

-parent: int[]

-searchOrder: List

+SearchTree(root: int, parent:

int[], searchOrder: List)

+getRoot(): int

+getSearchOrder(): List

+getParent(index: int): int

+getNumberOfVerticesFound(): int

+getPath(index: int): List

+printPath(index: int): void

+printTree(): void

The root of the tree.

The parents of the vertices.

The orders for traversing the vertices.

Constructs a tree with the specified root, parent, and

searchOrder.

Returns the root of the tree.

Returns the order of vertices searched.

Returns the parent for the specified vertex index.

Returns the number of vertices searched.

Returns a list of vertices from the specified vertex index

to the root.

Displays a path from the root to the specified vertex.

Displays tree with the root and all edges.

Depth-First Search
The depth-first search of a graph is like the depth-first search of a
tree discussed in §25.2.3, “Tree Traversal.” In the case of a tree, the
search starts from the root. In a graph, the search can start from any
vertex.

Input: G = (V, E) and a starting vertex v

Output: a DFS tree rooted at v

Tree dfs(vertex v) {

visit v;

for each neighbor w of v

if (w has not been visited) {

set v as the parent for w;

dfs(w);

}

}

Depth-First Search Example

Depth-First Search Example

Applications of the DFS
▪ Detecting whether a graph is connected. Search the graph starting from

any vertex. If the number of vertices searched is the same as the
number of vertices in the graph, the graph is connected. Otherwise, the
graph is not connected.

▪ Detecting whether there is a path between two vertices.
▪ Finding a path between two vertices.
▪ Finding all connected components. A connected component is a

maximal connected subgraph in which every pair of vertices are
connected by a path.

▪ Detecting whether there is a cycle in the graph.
▪ Finding a cycle in the graph.

The Connected Circles Problem

ConnectedCircles

http://www.cs.armstrong.edu/liang/intro11e/html/ConnectedCircles.html

Breadth-First Search

The breadth-first traversal of a graph is like the breadth-
first traversal of a tree discussed in §25.2.3, “Tree
Traversal.” With breadth-first traversal of a tree, the
nodes are visited level by level. First the root is visited,
then all the children of the root, then the grandchildren
of the root from left to right, and so on.

Breadth-First Search Algorithm
Input: G = (V, E) and a starting vertex v
Output: a BFS tree rooted at v

bfs(vertex v) {

create an empty queue for storing vertices to be visited;

add v into the queue;

mark v visited;

while the queue is not empty {

dequeue a vertex, say u, from the queue

process u;

for each neighbor w of u

if w has not been visited {

add w into the queue;

set u as the parent for w;

mark w visited;

}
}
}

Breadth-First Search Example

Breadth-First Search Example

TestBFS

https://liveexample.pearsoncmg.com/html/TestBFS.html

Applications of the BFS

▪ Detecting whether a graph is connected. A graph is connected if there is a path
between any two vertices in the graph.

▪ Detecting whether there is a path between two vertices.
▪ Finding a shortest path between two vertices. You can prove that the path

between the root and any node in the BFS tree is the shortest path between the
root and the node.

▪ Finding all connected components. A connected component is a maximal
connected subgraph in which every pair of vertices are connected by a path.

▪ Detecting whether there is a cycle in the graph.
▪ Finding a cycle in the graph.
▪ Testing whether a graph is bipartite. A graph is bipartite if the vertices of the

graph can be divided into two disjoint sets such that no edges exist between
vertices in the same set.

The Nine Tail Problem
The problem is stated as follows. Nine coins are placed in a
three by three matrix with some face up and some face
down. A legal move is to take any coin that is face up and
reverse it, together with the coins adjacent to it (this does
not include coins that are diagonally adjacent). Your task is
to find the minimum number of the moves that lead to all
coins face down.

Representing Nine Coins

Model the Nine Tail Problem

NineTailModel

NineTailModel

#tree: AbstractGraph.Tree

+NineTailModel()

+getShortestPath(nodeIndex: int):

List

-getEdges():

List

+getNode(index: int): char[]

+getIndex(node: char[]): int

+getFlippedNode(node: char[],

position: int): int

+flipACell(node: char[], row: int,

column: int): void

+printNode(node: char[]): void

A tree rooted at node 511.

Constructs a model for the nine tails problem and obtains the tree.

Returns a path from the specified node to the root. The path returned

consists of the node labels in a list.

Returns a list of Edge objects for the graph.

Returns a node consisting of nine characters of Hs and Ts.

Returns the index of the specified node.

Flips the node at the specified position and returns the index of the

flipped node.

Flips the node at the specified row and column.

Displays the node on the console.

NineTailNineTailModel

https://liveexample.pearsoncmg.com/html/NineTail.html

https://liveexample.pearsoncmg.com/html/NineTailModel.html

Chapter 25: Binary Search

Tree

s

Chapter 26: AVL Trees

Dr. Adriana Badulescu

Chapter 25 Objectives
▪ To design and implement a binary search tree (§25.2).

▪ To represent binary trees using linked data structures (§25.2.1).

▪ To search an element in binary search tree (§25.2.2).

▪ To insert an element into a binary search tree (§25.2.3).

▪ To traverse elements in a binary tree (§25.2.4).

▪ To delete elements from a binary search tree (§25.3).

▪ To display binary tree graphically (§25.4).

▪ To create iterators for traversing a binary tree (§25.5).

▪ To implement Huffman coding for compressing data using a

binary tree (§25.6).

Binary Trees

A list, stack, or queue is a linear structure that consists of a
sequence of elements. A binary tree is a hierarchical
structure. It is either empty or consists of an element,
called the root, and two distinct binary trees, called the
left subtree and right subtree

.

6

0

55 100

57 67 107 45

G

F R

M T A

(A) (B)

See How a Binary Search Tree Works

https://liveexample.pearsoncmg.com/dsanimation/

BST

eBook.html

Binary Tree Terms
The root of left (right) subtree of a node is called a left
(right) child of the node. A node without children is called
a leaf. A special type of binary tree called a binary searc

h

tree is often useful. A binary search tree (with no
duplicate elements) has the property that for every

node

in the tree the value of any node in its left subtree is less
than the value of the node and the value of any node in
its right subtree is greater than the value of the node. The
binary trees in Figure 25.1 are all binary search trees. This
section is concerned with binary search trees.

Representing Binary Trees
A binary tree can be represented using a set of linked
nodes. Each node contains a value and two links named
left and right that reference the left child and right child,
respectively, as shown in Figure 25.2.

Searching an Element in a Binary Search Tree

Inserting an Element to a Binary Search Tree

If a binary tree is empty, create a root node with the new
element. Otherwise, locate the parent node for the new
element node. If the new element is less than the

parent

element, the node for the new element becomes the left
child of the parent. If the new element is greater than the
parent element, the node for the new element becomes
the right child of the parent. Here is the algorithm:

Inserting an Element to a Binary Tree

Trace Inserting 101 into the following tree

Trace Inserting 101 into the following tree, cont.

Trace Inserting 101 into the following tree, cont.

Trace Inserting 101 into the following tree, cont.

Trace Inserting 101 into the following tree, cont.

Trace Inserting 101 into the following tree, cont.

Trace Inserting 101 into the following tree, cont.

Trace Inserting 101 into the following tree, cont.

Trace Inserting 101 into the following tree, cont.

Trace Inserting 101 into the following tree, cont.

Trace Inserting 101 into the following tree, cont.

Trace Inserting 101 into the following tree, cont.

Trace Inserting 101 into the following tree, cont.

Trace Inserting 101 into the following tree, cont.

Trace Inserting 101 into the following tree, cont.

Trace Inserting 101 into the following tree, cont.

Trace Inserting 101 into the following tree, cont.

Trace Inserting 101 into the following tree, cont.

Trace Inserting 101 into the following tree, cont.

Trace Inserting 101 into the following tree, cont.

Inserting 59 into the Tree

Tree Traversal
Tree traversal is the process of visiting each node in the
tree exactly once. There are several ways to traverse a tree.
This section presents inorder, preorder, postorder, depth-
first, and breadth-first traversals.

The inorder traversal is to visit the left subtree of the
current node first recursively, then the current node itself,
and finally the right subtree of the current node recursively.

The postorder traversal is to visit the left subtree of the
current node first, then the right subtree of the

current

node, and finally the current node itself.

Tree Traversal, cont.

The preorder traversal is to visit the current node first, then

the left subtree of the current node recursively, and finally
the right subtree of the current node recursively.

Tree Traversal, cont.

The breadth-first traversal is to visit the nodes level by
level. First visit the root, then all children of the root from
left to right, then grandchildren of the root from left to
right, and so on.

For example, in the tree in Figure 25.2, the inorder is 45 55
57 59 60 67 100 101 107. The postorder is 45 59 57 55 67
101 107 100 60. The preorder is 60 55 45 57 59 100 67 107
101. The breadth-first traversal is 60 55 100 45 57 67 107
59 101.

The Tree Interface

The Tree interface defines common
operations for trees.

«interface»

Tree

+search(e: E): boolean

+insert(e: E): boolean

+delete(e: E): boolean

+inorder(): void

+preorder(): void

+postorder(): void

+getSize(): int

+isEmpty(): boolean

+clear(): void

Override the add, isEmpty, remove,

containsAll, addAll, removeAll,

retainAll, toArray(), and toArray(T[])

methods defined in Collection using

default methods.

Returns true if the specified element is

in the tree.

Returns true if the element is added successfully.

Returns true if the element is removed from the tree

successfully.

Prints the nodes in inorder traversal.

Prints the nodes in preorder traversal.

Prints the nodes in postorder traversal.

Returns the number of elements in the tree.

Returns true if the tree is empty.

Removes all elements from the tree.

«interface»

java.lang.Collection

Tree

https://liveexample.pearsoncmg.com/html/Tree.html

The BST Class

Let’s define the binary tree class, named BST with A
concrete BST class can be defined to extend AbstractTree.

BST>

#root: TreeNode

#size: int

+BST()

+BST(objects: E[])

+path(e: E):
java.util.List>

1

m
TreeNode

Link

0

The root of the tree.

The number of nodes in the tree.

Creates a default BST.

Creates a BST from an array of elements.

Returns the path of nodes from the root leading to the

node for the specified element. The element may not be

in the tree.

«interface»
Tree

BST

https://liveexample.pearsoncmg.com/html/BST.html

Example: Using Binary Trees

Write a program that creates a binary tree using BST. Add
strings into the binary tree and traverse the tree in inorder,
postorder, and preorder.

TestBST

https://liveexample.pearsoncmg.com/html/TestBST.html

Tree After Insertions

Deleting Elements in a Binary Search Tree

To delete an element from a binary tree, you need
to first locate the node that contains the element
and also its parent node. Let current point to the
node that contains the element in the binary tree
and parent point to the parent of the current
node. The current node may be a left child or a
right child of the parent node. There are two cases
to consider:

Deleting Elements in a Binary Search Tree

Case 1: The current node does not have a left child, as
shown in this figure (a). Simply connect the parent with the
right child of the current node, as shown in this figure (b).

parent
current

No left child

Subtree

parent

Subtree

current may be a left or

right child of parent

Subtree may be a left or

right subtree of parent

current points the node

to be deleted

Deleting Elements in a Binary Search Tree
For example, to delete node 10 in Figure 25.9a. Connect the parent of
node 10 with the right child of node 10, as shown in Figure 25.9b.

20

10

40

30 80

root

50

16

27

20
40
30 80
root
50
16

27

Deleting Elements in a Binary Search Tree

Case 2: The current node has a left child. Let rightMost
point to the node that contains the largest element in the
left subtree of the current node and parentOfRightMost
point to the parent node of the rightMost node, as shown
in Figure 25.10a. Note that the rightMost node cannot
have a right child, but may have a left child. Replace the
element value in the current node with the one in the
rightMost node, connect the parentOfRightMost node with
the left child of the rightMost node, and delete the
rightMost node, as shown in Figure 25.10b.

Deleting Elements in a Binary Search Tree
Case 2 diagram

parent
current

.
.
.

rightMost

parentOfRightMost

parent

.
.
.

parentOfRightMost

Content copied to

current and the node

deleted

Right subtree Right subtree

current
current may be a left or
right child of parent
current points the node

to be deleted

The content of the current node is

replaced by content by the content of

the right-most node. The right-most

node is deleted.

leftChildOfRightMost leftChildOfRightMost

Deleting Elements in a Binary Search Tree
Case 2 example, delete 20

rightMost
20

10 40

30 80
root
50
16
27
16
10 40
30 80
root

50 27 14 14

Examples

Delete this

node
George

Adam

Michael

Daniel

Jones

Tom

Peter

Daniel

Adam Michael
Jones Tom

Peter

Examples

Daniel
Adam Michael
Jones Tom
Peter
Delete this
node

Daniel

Michael
Jones Tom
Peter

Examples

Daniel
Michael
Jones Tom
Peter
Delete this
node

Daniel

Jones

Tom
Peter

TestBSTDelete

https://liveexample.pearsoncmg.com/html/TestBSTDelete.html

Binary Tree Time Complexity

It is obvious that the time complexity for the
inorder, preorder, and postorder is O(n), since
each node is traversed only once. The time
complexity for search, insertion and deletion is
the height of the tree. In the worst case, the
height of the tree is O(n).

Tree Visualization

BTView

https://liveexample.pearsoncmg.com/html/BSTAnimation.html

https://liveexample.pearsoncmg.com/html/BTView.html

Iterators

An iterator is an object that provides a
uniform way for traversing the elements in a
container such as a set, list, binary tree, etc.

TestBSTWithIterator

https://liveexample.pearsoncmg.com/html/TestBSTWithIterator.html

Data Compression: Huffman Coding
In ASCII, every character is encoded in 8 bits. Huffman
coding compresses data by using fewer bits to encode
more frequently occurring characters. The codes for
characters are constructed based on the occurrence of
characters in the text using a binary tree, called the
Huffman coding tree.

Mississippi

Constructing Huffman Tree

▪ To construct a Huffman coding tree, use a greedy

algorithm as follows:

▪ Begin with a forest of trees. Each tree contains a node
for a character. The weight of the node is the
frequency of the character in the text.

▪ Repeat this step until there is only one tree:

Choose two trees with the smallest weight and create
a new node as their parent. The weight of the new
tree is the sum of the weight of the subtrees.

Constructing Huffman Tree

HuffmanCode

https://liveexample.pearsoncmg.com/html/HuffmanCode.html

Chapter 26 Objectives

▪ To know what an AVL tree is (§26.1).
▪ To understand how to rebalance a tree using the LL

rotation, LR rotation, RR rotation, and RL rotation (§26.2).
▪ To know how to design the

AVLTree

class (§26.3).
▪ To insert elements into an AVL tree (§26.4).
▪ To implement node rebalancing (§26.5).
▪ To delete elements from an AVL tree (§26.6).
▪ To implement the AVLTree class (§26.7).
▪ To test the AVLTree class (§26.8).
▪ To analyze the complexity of search, insert, and delete

operations in AVL trees (§26.9).

Why AVL Tree?
The search, insertion, and deletion time for a binary

tree is dependent on the height of the tree. In the

worst case, the height is O(n). If a tree is perfectly

balanced, i.e., a complete binary tree, its height is .

Can we maintain a perfectly balanced tree? Yes.

But it will be costly to do so. The compromise is to

maintain a well-balanced tree, i.e., the heights of

two subtrees for every node are about the same.

What is an AVL Tree?

AVL trees are well-balanced. AVL trees were

invented by two Russian computer scientists G. M.

Adelson-Velsky and E. M. Landis in 1962. In an

AVL tree, the difference between the heights of two

subtrees for every node is 0 or 1. It can be shown

that the maximum height of an AVL tree is O(logn).

AVL Tree Animation

https://liveexample.pearsoncmg.com/dsanimation/AVLTree.html

Balance Factor/Left-Heavy/Right-Heavy
The process for inserting or deleting an element in an AVL

tree is the same as in a regular binary search tree. The

difference is that you may have to rebalance the tree after

an insertion or deletion operation. The balance factor of a

node is the height of its right subtree minus the height of

its left subtree. A node is said to be balanced if its balance

factor is -1, 0, or 1. A node is said to be left-heavy if its

balance factor is -1. A node is said to be right-heavy if its

balance factor is +1.

Balancing Trees
If a node is not balanced after an insertion or deletion

operation, you need to rebalance it. The process of

rebalancing a node is called a rotation. There are four

possible rotations.

LL imbalance and LL rotation
LL Rotation: An LL imbalance occurs at a node A such that A has a

balance factor -2 and a left child B with a balance factor -1 or 0. This

type of imbalance can be fixed by performing a single right rotation

at A.

A -2

B -1 or 0

T2

T3

T1

h+1

h

h

T2’s height is h or

h+1

A 0 or -1

B 0 or 1

T2 T3

T1 h+1

h h

RR imbalance and RR rotation
RR Rotation: An RR imbalance occurs at a node A such that A has a

balance factor +2 and a right child B with a balance factor +1 or 0.

This type of imbalance can be fixed by performing a single left

rotation at A.

A +2

B +1 or 0

T2
T3

T1

h+1

h
h

T2’s height is

h or h+1

A 0 or +1

B 0 or -1

T2 T3
T1
h+1

h
h

LR imbalance and LR rotation
LR Rotation: An LR imbalance occurs at a node A such that A has a

balance factor -2 and a left child B with a balance factor +1. Assume

B’s right child is C. This type of imbalance can be fixed by

performing a double rotation (first a single left rotation at B and then

a single right rotation at A).

A -2

C
-1, 0,

or 1

T3

T4

T2 h h

h

B +1

T1 h

T2 and T3 may have

different height, but

at least one’ must

have height of h.

C 0

A 0 or 1

T3 T4 T2 h
h h

B 0 or -1

T1 h

RL imbalance and RL rotation
RL Rotation: An RL imbalance occurs at a node A such that A has a

balance factor +2 and a right child B with a balance factor -1.

Assume B’s left child is C. This type of imbalance can be fixed by

performing a double rotation (first a single right rotation at B and

then a single left rotation at A).

A +2

C 0, -1,

or 1
T3
T4
T2 h h
h

B -1

T1 h
T2 and T3 may have
different height, but
at least one’ must
have height of h.

C 0

B 0 or 1

T3 T4 T2 h
h h
A 0 or -1
T1 h

Designing Classes for AVL Trees
▪ An AVL tree is a binary tree. So you can define the

AVLTree class to extend the BST class.

TestAVLTree

AVLTree

https://liveexample.pearsoncmg.com/html/TestAVLTree.html

https://liveexample.pearsoncmg.com/html/AVLTree.html

Chapter 27:

Hashing

Dr. Adriana Badulescu

Objectives

▪ To know what hashing is for (§27.3).

▪ To obtain the hash code for an object and design the hash
function to map a key to an index (§27.4).

▪ To handle collisions using open addressing (§27.5).

▪ To know the differences among linear probing, quadratic
probing, and double hashing (§27.5).

▪ To handle collisions using separate chaining (§27.6).

▪ To understand the load factor and the need for rehashing
(§27.7).

▪ To implement MyHashMap using hashing (§27.8).

Why Hashing?

The preceding chapters introduced search trees. An element can be

found in O(logn) time in a well-balanced search tree. Is there a more

efficient way to search for an element in a container? This chapter

introduces a technique called hashing. You can use hashing to

implement a map or a set to search, insert, and delete an element in

O(1) time.

Map
A map is a data structure that stores entries. Each entry contains two

parts: key and value. The key is also called a search key, which is

used to search for the corresponding value. For example, a

dictionary can be stored in a map, where the words are the keys and

the definitions of the words are the values.

A map is also called a dictionary, a hash table, or an associative

array. The new trend is to use the term map.

What is Hashing?
If you know the index of an element in the array, you can retrieve the

element using the index in O(1) time. So, can we store the values

in an array and use the key as the index to find the value? The

answer is yes if you can map a key to an index.

The array that stores the values is called a hash table. The function

that maps a key to an index in the hash table is called a hash

function.

Hashing is a technique that retrieves the value using the index

obtained from key without performing a search.

Hash Function and Hash Codes
A typical hash function first converts a search key to an integer value

called a hash code, and then compresses the hash code into an

index to the hash table.

Linear Probing Animation

Linear Probing Animation

https://liveexample.pearsoncmg.com/dsanimation/LinearProbingeBook.html

Quadratic Probing
Quadratic probing can avoid the clustering problem in linear

probing. Linear probing looks at the consecutive cells beginning

at index k. Quadratic probing increases the index by j^2 for j = 1,

2, 3, … The actual index searched are k, k + 1, k + 4, …

https://liveexample.pearsoncmg.com/dsanimation/QuadraticProbingeBook.html

Double Hashing
Double hashing uses a secondary hash function on the keys to

determine the increments to avoid the clustering problem.

h’(k) = 7 – k % 7;

https://liveexample.pearsoncmg.com/dsanimation/DoubleHashingeBook.html

Handling Collisions Using Separate Chaining
The separate chaining scheme places all entries with the same hash

index into the same location, rather than finding new locations.

Each location in the separate chaining scheme is called a bucket.

A bucket is a container that holds multiple entries.

Separate Chaining Animation

https://liveexample.pearsoncmg.com/dsanimation/SeparateChainingeBook.html

Implementing Map Using Hashing

MyMap

MyHashMap

TestMyHashMap

https://liveexample.pearsoncmg.com/html/MyMap.html

https://liveexample.pearsoncmg.com/html/MyHashMap.html

https://liveexample.pearsoncmg.com/html/TestMyHashMap.html

Implementing Set Using Hashing

MySet

MyHashSet

TestMyHashSet

https://liveexample.pearsoncmg.com/html/MySet.html

https://liveexample.pearsoncmg.com/html/MyHashSet.html

https://liveexample.pearsoncmg.com/html/TestMyHashSet.html