Transcript Chapter 2: Using Objects

RAIK 283: Data Structures & Algorithms
Transform and Conquer
Dr. Ying Lu
[email protected]
Design and Analysis of Algorithms – Chapter 6
1
RAIK 283: Data Structures & Algorithms
 Giving credit where credit is due:
• Most of the lecture notes are based on the slides from
the Textbook’s companion website
– http://www.aw-bc.com/info/levitin
• Some examples and slides are based on lecture notes
created by Dr. Ben Choi, Louisiana Technical University
and Dr. Chuck Cusack, Hope College and Dr. Ellen
Walker from Hiram College
• I have modified many of their slides and added new
slides.
Design and Analysis of Algorithms – Chapter 6
2
An example problem

Checking element uniqueness in an array
Algorithm UniqueElements(A[0..n-1])
for m = 0 to n-2 do
for k = m+1 to n-1 do
if A[m] = A[k] return false
return true

Can we come up with a better algorithm?
Design and Analysis of Algorithms – Chapter 6
3
Transform and Conquer
Solve problem by transforming it into:

a more convenient instance of the same problem (instance simplification)
• presorting
• Gaussian elimination
 a different representation of the same instance (representation change)
• balanced search trees
• heaps and heapsort
• polynomial evaluation by Horner’s rule

a different problem altogether (problem reduction)
• compute lcm(m, n) = m*n/gcd(m,n)
• reductions to graph problems
• linear programming
Design and Analysis of Algorithms – Chapter 6
4
Binary Search Trees (BSTs)

Binary Search Tree property
• A binary tree in which the key of an internal node is
greater than the keys in its left subtree and less than or
equal to the keys in its right subtree.
Design and Analysis of Algorithms – Chapter 5
5
Analysis of BST Operations
All of the BST operations have time complexity (h),
where h is the height of the tree
 However, in the worst-case, the height may be (n)
where n is the number of internal nodes

• For example, a long chain tree structure
For a tree as balanced as possible, O(log2 n)
 The objective is to make the tree as balanced as
possible

• Technique: Binary Tree Rotations

Balanced search tree: AVL tree and 2-3 tree
Design and Analysis of Algorithms – Chapter 5
6
Left- and Right-Rotations

The BST property still holds after a rotation.
Design and Analysis of Algorithms – Chapter 6
7
Binary Tree Rotations

Left Rotation on (15, 25)
Design and Analysis of Algorithms – Chapter 6
8
Balanced trees: AVL trees

For every node, difference in height between left and right
subtrees is at most 1

AVL property is maintained through rotations, each time
the tree becomes unbalanced

lg n ≤ h ≤ 1.4404 lg (n + 2) - 1.3277
average: 1.01 lg n + 0.1 for large n

A similar idea: red-black trees (height of subtrees is
allowed to differ by up to a factor of 2)
Design and Analysis of Algorithms – Chapter 6
9
Balance factor

Algorithm maintains balance factor (difference in height between
a node’s left and right subtrees) for each node. For example:
Design and Analysis of Algorithms – Chapter 6
10
In-class exercise

Page 225: Exercise 6.3.1
Design and Analysis of Algorithms – Chapter 6
11
General case: single R-rotation
Design and Analysis of Algorithms – Chapter 6
12
When single L-rotation?
Design and Analysis of Algorithms – Chapter 6
13
Single L-Rotation
Design and Analysis of Algorithms – Chapter 6
14
Double LR-rotation
Design and Analysis of Algorithms – Chapter 6
15
When double RL-rotation?
Design and Analysis of Algorithms – Chapter 6
16
Double RL-rotation
Design and Analysis of Algorithms – Chapter 6
17
AVL tree rotations

Small examples:
•
•
•
•

1, 2, 3
3, 2, 1
1, 3, 2
3, 1, 2
Large example: 5, 6, 8, 3, 2, 4, 7
Design and Analysis of Algorithms – Chapter 6
18
In-class exercise

Construct an AVL tree for the list: 4, 5, 7, 2, 1, 3, 6
by successive insertions.

Page 226: Exercise 6.3.4
• For each of the following lists, construct an AVL tree by
inserting their elements successively, starting with the
empty tree.
– A) 1, 2, 3, 4, 5, 6
– B) 6, 5, 4, 3, 2, 1
– C) 3, 6, 5, 1, 2, 4
Design and Analysis of Algorithms – Chapter 6
19
Balanced trees: AVL trees

For every node, difference in height between left
and right subtrees is at most 1

AVL property is maintained through rotations,
each time the tree becomes unbalanced

lg n ≤ h ≤ 1.4404 lg (n + 2) - 1.3277
average: 1.01 lg n + 0.1 for large n

Disadvantage: needs extra storage for maintaining
node balance
Design and Analysis of Algorithms – Chapter 6
20
2-3 Trees
Relax constraint that a node has 2 children
 Allow 2-child nodes and 3-child nodes

• With bigger nodes, tree is shorter & branchier
• 2-node is just like before (one item, two children)
• 3-node has two values and 3 children (left, middle, right)

All leaves are in the same level
< x , y>
<=x
>x and <=y
>y
Design and Analysis of Algorithms – Chapter 6
21
Why 2-3 tree

Faster searching?
• Actually, no. 2-3 tree is about as fast as an “equally
balanced” binary tree, because you sometimes have to
make 2 comparisons to get past a 3-node

Easier to keep balanced?
• Yes, definitely.
• Insertion can split 3-nodes into 2-nodes, or promote 2nodes to 3-nodes to keep tree balanced!
Design and Analysis of Algorithms – Chapter 6
22
Inserting into 2-3 Tree




As for binary tree, start by searching for the item
If you don’t find it, and you stop at a 2-node, upgrade the
2-node to a 3-node.
If you don’t find it, and you stop at a 3-node, you can’t just
add another value. So, replace the 3-node by 2 2-nodes and
push the middle value up to the parent node
Repeat recursively until you upgrade a 2-node or create a
new root.
Design and Analysis of Algorithms – Chapter 6
23
An example

Construction of a 2-3 tree for
• the list 9, 5, 8, 3, 2, 4, 7
Design and Analysis of Algorithms – Chapter 6
24
2-3 trees
 When
is a new root created?
 What
is the height of a 2-3 tree?
Design and Analysis of Algorithms – Chapter 6
25
2-3 trees

When is a new root created?
 What
is the height of a 2-3 tree?
• (logn) (refer to Page 224-225)
Design and Analysis of Algorithms – Chapter 6
26
Why is this better?

Intuitively, you unbalance a binary tree when you add
height to one path significantly more than other
possible paths.

With the 2-3 tree insertion algorithm, you can only add
height to the tree when you create a new root, and this
adds one unit of height to all paths simultaneously.
Design and Analysis of Algorithms – Chapter 6
27
In-Class Exercise
31
Solution
Design and Analysis of Algorithms – Chapter 6
28
After-class exercise

How to delete a node from a 2-3 Tree?
Design and Analysis of Algorithms – Chapter 6
29
In-Class Exercises (II)

Design “transform and conquer” algorithms
• 6.1.7
• 6.1.8
Design and Analysis of Algorithms – Chapter 6
30
Priority Queue Implementation?

A priority queue is the abstract data type (ADT) of
an ordered set with the operations:
• find element with highest priority
• delete element with highest priority
• insert element with assigned priority

What data structure should we use to implement a
priority queue efficiently?
Design and Analysis of Algorithms – Chapter 6
31