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

+bfs(v: int): UnWeightedGraph

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

-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

+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

The price is based on these factors:

Academic level

Number of pages

Urgency

Basic features

- Free title page and bibliography
- Unlimited revisions
- Plagiarism-free guarantee
- Money-back guarantee
- 24/7 support

On-demand options

- Writer’s samples
- Part-by-part delivery
- Overnight delivery
- Copies of used sources
- Expert Proofreading

Paper format

- 275 words per page
- 12 pt Arial/Times New Roman
- Double line spacing
- Any citation style (APA, MLA, Chicago/Turabian, Harvard)

Delivering a high-quality product at a reasonable price is not enough anymore.

That’s why we have developed 5 beneficial guarantees that will make your experience with our service enjoyable, easy, and safe.

You have to be 100% sure of the quality of your product to give a money-back guarantee. This describes us perfectly. Make sure that this guarantee is totally transparent.

Read moreEach paper is composed from scratch, according to your instructions. It is then checked by our plagiarism-detection software. There is no gap where plagiarism could squeeze in.

Read moreThanks to our free revisions, there is no way for you to be unsatisfied. We will work on your paper until you are completely happy with the result.

Read moreYour email is safe, as we store it according to international data protection rules. Your bank details are secure, as we use only reliable payment systems.

Read moreBy sending us your money, you buy the service we provide. Check out our terms and conditions if you prefer business talks to be laid out in official language.

Read more