For Discussion 3, you should post one original initial post discussion a topic from the unit and post two response posts during the response period. No late submissions will be accepted. Post early to not lose the preferred topic and give the other students enough time to respond.

Don't use plagiarized sources. Get Your Custom Essay on

top answer: For Discussion 3, you should post one original initial post discussion a topic from the unit and po

Just from $10/Page

The initial post should summarize a subtopic/section from Chapter 25, 26, 27, 28 and 29 . Create a new thread containing the name of the topic/subtopic, the Chapter, location/page/section number in course textbook, and location/slide number/page in the Chapter presentation PDF in the thread title and minimum 300 words. The post should be original and should not cover any previously posted topics. You are not going to earn any credit for duplicated topics.

The response posts should add more information about the topic, ask questions, politely debate statements from the initial posts, respond to questions. Reply inside the thread and quote the original post you respond to.

You need to follow the class netiquette. You will loose point for breaking the netiquette.

Do not share solutions to assignments or other evaluations.

Read the Discussions Instructions below for details instructions and example for your posts.

Unit Discussions

Dr. Adriana Badulescu

Unit Discussions

▪ For discussions, you need to submit/post one original

initial post discussing a topic from the unit and

submit/post four response posts during the response

period.

▪ You need to follow the class netiquette. You will lose

points for breaking the netiquette.

▪ Do not share solutions to assignments or other

evaluations in your posts. You are going to lose points.

▪ No late submissions will be accepted.

▪ Post early to not lose the preferred topic and give the

other students enough time to respond.

Dr. Adriana Badulescu COSC2436 Programming Fundamentals III 2

Unit Discussions

Discussion Unit Chapters/Topics

Discussion 1 Chapters 18, 20, and 21

Discussion 2 Chapters 22, 23, and 24

Discussion 3 Chapters 25, 25, 27, 28, and 29

Dr. Adriana Badulescu COSC2436 Programming Fundamentals III 3

Initial Posts

▪ The initial post should summarize a subtopic/section from the Unit

Chapters

▪ Create a new thread containing the name of the topic/subtopic,

the Chapter, location/page/section number in course textbook,

and location/slide number/page in the Chapter presentation PDF

in the thread subject/title

▪ The post body/message should have a minimum 300 words.

▪ The post should be original and should not cover any previously

posted topics. You are not going to earn any credit for duplicated

topics.

Dr. Adriana Badulescu COSC2436 Programming Fundamentals III 4

Initial Posts

▪ To find the topic in the Textbook:

▪ Go to the course eCampus Textbook and Software

menu to IncludEd Textbook

Dr. Adriana Badulescu COSC2436 Programming Fundamentals III 5

Initial Posts

▪ Go to the Chapter and open the Read section to find

the subtopic in the book or open the eBook, go to the

Chapter and find your subtopics

Dr. Adriana Badulescu COSC2436 Programming Fundamentals III 6

Initial Posts

▪ For example, if I want to talk about the first subtopic in the book

which is about using recursion for computing factorials, in the

textbook, I am going to go to the Chapter 18 and find the

subtopic, which is in section “18.2 Case Study: Computing

Factorials“.

Dr. Adriana Badulescu COSC2436 Programming Fundamentals III 7

▪ Chapter is Chapter

18

▪ Section is 18.2

▪ Name is “Case Study:

Computing Factorials“

▪ Page is 721

Initial Posts

▪ To find the topic in the chapter presentation

PDF:

▪ Open the Unit, find the Reading Assignment and

Practice Exercise for the Unit and open the

ChapterX.pdf where X is the chapter number

▪ Find your subtopic

Dr. Adriana Badulescu COSC2436 Programming Fundamentals III 8

Initial Posts

▪ For the example, I am going to go to eCampus and

open the Chapter18.pdf presentation under Unit 1,

and the subtopic is on slide 4.

Dr. Adriana Badulescu COSC2436 Programming Fundamentals III 9

Initial Posts

▪ Thus, for the example, I am going to name the Initial Post:

“Case Study: Computing Factorials- Chapter 18 -Textbook

Section 18-2 – Page 721 – Presentation Slide 3”

▪ Then make a minimum 300 words post in which I summarize

in my own words what is factorial, what is recursion, why

should I use recursion for factorial, how would the code

would look like, explain how would it work, why using

recursion is better/worse that other methods.

Dr. Adriana Badulescu COSC2436 Programming Fundamentals III 10

Initial Posts

▪ To post the discussion initial post

▪ Open the discussion

▪ Read the current thread subjects and make sure the subtopic

was not posted already

▪ Click Create Thread to create a new thread for your post

Dr. Adriana Badulescu COSC2436 Programming Fundamentals III 11

Initial Posts

▪ Enter the Thread Subject/Title, Thread Message/Body

and click Submit to submit your post

Dr. Adriana Badulescu COSC2436 Programming Fundamentals III 12

Initial Posts

▪ After you submit your post, you are going to

see your post on top of the Discussion

▪ If you see a post with the same topic below

(posted before you), you need to post a new

topic

Dr. Adriana Badulescu COSC2436 Programming Fundamentals III 13

Response Posts

▪ The response posts should add more

information about the topic, ask questions,

politely debate statements from the initial

posts, respond to questions.

▪ Reply inside the thread and quote the original

post you respond to.

Dr. Adriana Badulescu COSC2436 Programming Fundamentals III 14

Response Posts

▪ Click on the Initial Post thread to respond

▪ This will open the original thread

Dr. Adriana Badulescu COSC2436 Programming Fundamentals III 15

Response Posts

Dr. Adriana Badulescu COSC2436 Programming Fundamentals III 16

▪ When you hover/move the mouse over the button

Reply, you are going to see the Quote button

▪ Click on Quote button to start your response

▪ Note: If you need to edit your own post, this is where

you can find the Edit option

Response Posts

▪ Enter your response in the Thread Message/Body and

click Submit to post your response

Dr. Adriana Badulescu COSC2436 Programming Fundamentals III 17

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

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, …

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;

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

Implementing Map Using Hashing

MyMap

MyHashMap

TestMyHashMap

Implementing Set Using Hashing

MySet

MyHashSet

TestMyHashSet

Chapter 28: Graphs 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

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<V>

+getSize(): int

+getVertices(): List<V>

+getVertex(index: int): V

+getIndex(v: V): int

+getNeighbors(index: int): List<Integer>

+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<V>.SearchTree

+bfs(v: int): UnWeightedGraph<V>.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<V>

#vertices: List<V>

#neighbors: List<List<Edge>>

+UnweightedGraph()

+UnweightedGraph(vertices: V[], edges:

int[][])

+UnweightedGraph(vertices: List<V>,

edges: List<Edge>)

+UnweightedGraph(edges: int[][],

numberOfVertices: int)

+UnweightedGraph(edges: List<Edge>,

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.

TestGraph

UnweightedGraph

Graph

Graph

Graph Visualization

DisplayUSMapGraphView Displayable

Graph Traversals

Depth-first search and breadth-first search

Both traversals result in a spanning tree, which can be

modeled using a class.

UnweightedGraph<V>.SearchTree

-root: int

-parent: int[]

-searchOrder: List<Integer>

+SearchTree(root: int, parent:

int[], searchOrder: List<Integer>)

+getRoot(): int

+getSearchOrder(): List<Integer>

+getParent(index: int): int

+getNumberOfVerticesFound(): int

+getPath(index: int): List<V>

+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

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

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<Integer>.Tree

+NineTailModel()

+getShortestPath(nodeIndex: int):

List<Integer>

-getEdges():

List<AbstractGraph.Edge>

+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

Chapter 25: Binary Search Trees

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.

60

55 100

57 67 107 45

G

F R

M T A

(A) (B)

See How a Binary Search Tree Works

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 search

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<E>

+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<E>

Tree

The BST Class

Let’s define the binary tree class, named BST with A

concrete BST class can be defined to extend AbstractTree.

BST<E extends Comparable<E>>

#root: TreeNode<E>

#size: int

+BST()

+BST(objects: E[])

+path(e: E):

java.util.List<TreeNode<E>>

1

m

TreeNode<E>

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<E>

BST

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

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

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

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

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.

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

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

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