GMT Algorithm Analysis: Binary Search Trees & Data Structures
Elementary maths for GMT
Algorithm analysis
Trees
Part I: Binary Search Trees
•
Analyzing data structures
•
Example: binary search trees
•
Overview
–
Definition
–
Properties
–
Operations
•
Analyzing properties and running times of operations
3
Goal
•
Array
–
fast searching, slow insertion
•
Linked list
–
slow searching, fast insertion
Storing and modifying data
5
Data structures for maintaining sets
6
Trees
•
Every node has only 2 children
–
children can be
dummies
7
Binary trees
8
Binary search trees
9
Tree property - Height
6
4
3
3
8
0
2
8
8
8
4
2
7
7
3
7
9
7
4
1
7
5
10
Binary tree property - Height
min
max
11
Searching for an element
6
4
8
1
5
6
9
12
Inserting an element
6
4
8
1
5
6
9
7
13
In-order tree traversal
x
LC
RC
•
Example when storing
value x in-between
visiting the children
–
{1, 4, 5, 6, 6, 8, 9}•
Example in a binary search tree: removing 7
–
First search for the value 7
–
If node has at least one dummy node as a child, delete node and
attach other child to parent
14
Removing an element (1 / 3)
6
4
8
1
5
7
9
•
Example in a binary search tree: removing 8
–
Search for 8
–
If left (resp. right) child is a dummy node, attach right (resp. left)
child to parent
15
Removing an element (2 / 3)
4
1
5
8
6
9
16
Removing an element (3 / 3)
4
5
6
8
1
6
9
5
17
Summary on binary search trees
Part II: AVL trees
•
A
n
A
V
L
t
r
e
e
(
A
d
e
l
s
o
n
-
V
e
l
s
k
i
i
L
a
n
d
i
s
)
i
s
a
b
i
n
a
r
y
s
e
a
r
c
h
t
r
e
e
w
h
e
r
e
f
o
r
e
v
e
r
y
i
n
t
e
r
n
a
l
n
o
d
e
v
,
t
h
e
h
e
i
g
h
t
s
o
f
t
h
e
c
h
i
l
d
r
e
n
o
f
v
c
a
n
d
i
f
f
e
r
a
t
m
o
s
t
b
y
1
•
Example where the heights are shown next to the nodes
19
AVL tree: a balanced binary tree
6
4
1
1
5
8
1
4
7
9
0
1
3
0
0
0
1
2
20
Height of an AVL tree
•
Insertion is as in a binary search tree: always done by
expanding a node
•
Example: insert 10 in the following AVL tree
21
Insertion in an AVL tree
unbalanced
!
•
L
e
t
w
b
e
t
h
e
i
n
s
e
r
t
e
d
n
o
d
e
(
h
e
r
e
1
0
)
•
L
e
t
z
b
e
t
h
e
f
i
r
s
t
u
n
b
a
l
a
n
c
e
d
a
n
c
e
s
t
o
r
o
f
w
(
h
e
r
e
1
1
)
•
L
e
t
y
b
e
t
h
e
c
h
i
l
d
o
f
z
w
i
t
h
h
i
g
h
e
r
h
e
i
g
h
t
(
m
u
s
t
b
e
a
n
a
n
c
e
s
t
o
r
o
f
w
)
(
h
e
r
e
8
)
•
L
e
t
x
b
e
t
h
e
c
h
i
l
d
o
f
y
w
i
t
h
h
i
g
h
e
r
h
e
i
g
h
t
(
m
u
s
t
b
e
a
n
a
n
c
e
s
t
o
r
o
f
w
,
o
r
w
i
t
s
e
l
f
)
(
h
e
r
e
9
)
22
Unbalanced after insertion
w
z
y
x
•
Case 1: single rotation
•
P
e
r
f
o
r
m
t
h
e
r
o
t
a
t
i
o
n
s
n
e
e
d
e
d
t
o
m
a
k
e
y
t
h
e
t
o
p
m
o
s
t
n
o
d
e
o
f
t
h
e
z
-
y
-
x
s
u
b
-
t
r
e
e
23
Tri-node restructuring
•
Symmetric case
24
Tri-node restructuring
•
Case 2: double rotation
25
Tri-node restructuring
•
Symmetric case
26
Tri-node restructuring
27
Tri-node restructuring - Summary
•
Removal begins as in a binary search tree, which means
the node removed will become an
empty
node
•
Example: remove 5 in the following AVL tree
28
Removal in an AVL tree
unbalanced
!
•
L
e
t
w
b
e
t
h
e
p
a
r
e
n
t
o
f
t
h
e
r
e
m
o
v
e
d
n
o
d
e
(
h
e
r
e
4
)
•
L
e
t
z
b
e
t
h
e
f
i
r
s
t
u
n
b
a
l
a
n
c
e
d
a
n
c
e
s
t
o
r
o
f
w
(
h
e
r
e
6
)
•
L
e
t
y
b
e
t
h
e
c
h
i
l
d
o
f
z
w
i
t
h
h
i
g
h
e
r
h
e
i
g
h
t
(
i
s
n
o
w
n
o
t
a
n
a
n
c
e
s
t
o
r
o
f
w
)
(
h
e
r
e
1
1
)
•
L
e
t
x
b
e
–
t
h
e
c
h
i
l
d
o
f
y
w
i
t
h
h
i
g
h
e
r
h
e
i
g
h
t
i
f
h
e
i
g
h
t
s
a
r
e
d
i
f
f
e
r
e
n
t
,
o
r
–
t
h
e
c
h
i
l
d
o
f
y
o
n
t
h
e
s
a
m
e
s
i
d
e
a
s
y
i
f
h
e
i
g
h
t
s
a
r
e
e
q
u
a
l
(
h
e
r
e
1
4
)
29
Unbalanced after removal
w
z
y
x
•
P
e
r
f
o
r
m
s
r
o
t
a
t
i
o
n
s
t
o
m
a
k
e
y
t
h
e
t
o
p
m
o
s
t
o
f
t
h
e
z
-
y
-
x
t
r
e
e
•
As this restructuring may upset the balance of another
node higher in the tree, we must continue checking for
balance until the root is reached
30
Rebalancing after a removal
w
z
y
x
•
Example: remove 4
31
Repeated rebalancing
unbalanced
!
32
Repeated balancing
1
1
7
1
9
8
2
2
6
2
6
1
5
1
8
1
2
1
7
unbalanced
!
33
Running times for AVL trees
34
AVL trees vs. hash tables
35
Other trees
Dive into the world of elementary maths for GMT algorithm analysis, focusing on binary search trees, data structures, properties, operations, and more. Explore the fundamentals of storing and modifying data efficiently, as well as the significance of balanced search trees. Understand the key concepts of trees, accessing data, traversing links, binary trees, binary search trees, tree height property, and more.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Elementary maths for GMT Algorithm analysis Trees
Goal Analyzing data structures Example: binary search trees Overview Definition Properties Operations Analyzing properties and running times of operations 3 Elementary maths for GMT Algorithm analysis - Trees
Storing and modifying data Array fast searching, slow insertion 20 34 29 17 30 48 17 19 20 29 30 34 48 Linked list slow searching, fast insertion 20 34 29 17 30 48 17 20 29 30 34 48 19 Elementary maths for GMT Algorithm analysis - Trees
Data structures for maintaining sets Search Insert Unsorted array (?) (1) Sorted array (log?) (?) Unsorted list (?) (1) Sorted list (?) (?) Balanced search tree (log?) (log?) 5 Elementary maths for GMT Algorithm analysis - Trees
Trees Each of the n nodes contains data (number, object, etc.) pointers to its children (themselves trees) Primitives operations Accessing data: ?(1) time Traversing link: ?(1) time 16 80 2 41 18 99 23 53 7 22 6 Elementary maths for GMT Algorithm analysis - Trees
Binary trees Every node has only 2 children children can be dummies 16 80 41 18 99 23 22 7 Elementary maths for GMT Algorithm analysis - Trees
Binary search trees Binary trees with comparable values For a node with value x: Left sub-tree contains values < ? Right sub-tree contains values ? 6 4 8 1 5 6 9 8 Elementary maths for GMT Algorithm analysis - Trees
Tree property - Height The height h of a tree is the length of the longest path Property of the height: 0 ? 1 Example height = 4 64 80 33 75 28 42 77 88 97 37 41 9 Elementary maths for GMT Algorithm analysis - Trees
Binary tree property - Height min max 0 1 0 1 1 1 1 2 2 1 2 4 3 1 h 2h h 1 2log? ? 1 10 Elementary maths for GMT Algorithm analysis - Trees
Searching for an element Example in a binary search tree: searching for 7 Start at root At every node: Check if you found it Otherwise choose left or right child according to value in the current node Until you find the value or you are at a leaf node 6 4 8 1 5 6 9 Running time is ?( ) 11 Elementary maths for GMT Algorithm analysis - Trees
Inserting an element Example in a binary search tree: inserting 7 First search for the value 7 (previous slide) If already present, then nothing to do Else replace the dummy node 6 4 8 Running time is ?( ) 1 5 6 9 7 12 Elementary maths for GMT Algorithm analysis - Trees
In-order tree traversal Visit the nodes sequentially Running time ? ? 6 4 8 x 1 5 6 9 Example when storing value x in-between visiting the children {1, 4, 5, 6, 6, 8, 9} LC RC 13 Elementary maths for GMT Algorithm analysis - Trees
Removing an element (1 / 3) Example in a binary search tree: removing 7 First search for the value 7 If node has at least one dummy node as a child, delete node and attach other child to parent 6 4 8 1 5 7 9 14 Elementary maths for GMT Algorithm analysis - Trees
Removing an element (2 / 3) Example in a binary search tree: removing 8 Search for 8 If left (resp. right) child is a dummy node, attach right (resp. left) child to parent 6 4 9 8 1 5 9 15 Elementary maths for GMT Algorithm analysis - Trees
Removing an element (3 / 3) Example in a binary search tree: removing 4 Search for 4 Find in-order successor (here 5) it will always exists and its left child will always be a dummy node Replace the node to remove with the successor node Remove successor in the previously described way 6 4 5 8 1 6 9 5 Running time to find the in-order successor is ?( ) 16 Elementary maths for GMT Algorithm analysis - Trees
Summary on binary search trees Parameter / Operation Property / Time 2log? ? 1 Height h Accessing data, traversing a link ?(1) In-order traversal ?(?) Search, insertion and removal ?( ) 17 Elementary maths for GMT Algorithm analysis - Trees
AVL tree: a balanced binary tree An AVL tree (Adelson-Velskii Landis) is a binary search tree where for every internal node v, the heights of the children of v can differ at most by 1 Example where the heights are shown next to the nodes 3 6 1 2 4 11 0 1 0 14 8 5 0 0 7 9 19 Elementary maths for GMT Algorithm analysis - Trees
Height of an AVL tree Property: the height of an AVL tree storing n keys is ?(??? ?) Proof: let ?( ) be the minimum number of internal nodes of an AVL tree of height h ? 0 = 1 and ? 1 = 2 For > 1, an AVL tree of height h contains at least a root node, one AVL sub-tree of height h 1, and one AVL sub-tree of height h 2, so ? = 1 + ? 1 + ?( 2) Since ? 1 > ?( 2), we have ? > 2 ?( 2), and so ? > 2 ?( 2), ? > 4 ? 4 ,? > 8 ? 6 , So ? > 2??( 2?) 1 2 ? 2( 1 1 2 ? 1 = 2 +1 2 , If we choose ? = 1 then < 2log ?( ) 1 So the height of an AVL tree is ?(log?) 2: ? > 2 2) = 2 20 Elementary maths for GMT Algorithm analysis - Trees
Insertion in an AVL tree Insertion is as in a binary search tree: always done by expanding a node Example: insert 10 in the following AVL tree 6 6 4 4 11 11 unbalanced! 14 14 8 8 5 5 7 9 7 9 10 21 Elementary maths for GMT Algorithm analysis - Trees
Unbalanced after insertion Let w be the inserted node (here 10) Let z be the first unbalanced ancestor of w (here 11) Let y be the child of z with higher height (must be an ancestor of w) (here 8) Let x be the child of y with higher height (must be an ancestor of w, or w itself) (here 9) 6 z 4 11 14 y 8 5 x 7 9 10 w 22 Elementary maths for GMT Algorithm analysis - Trees
Tri-node restructuring Case 1: single rotation Perform the rotations needed to make y the top most node of the z-y-x sub-tree y z x z y T0 x T3 T1 T0 T2 T1 T2 T3 23 Elementary maths for GMT Algorithm analysis - Trees
Tri-node restructuring Symmetric case y z z x y T3 x T3 T1 T0 T2 T2 T1 T0 24 Elementary maths for GMT Algorithm analysis - Trees
Tri-node restructuring Case 2: double rotation x z y z y T0 x T3 T3 T1 T0 T2 T1 T2 25 Elementary maths for GMT Algorithm analysis - Trees
Tri-node restructuring Symmetric case x z z y y T3 x T0 T3 T1 T0 T2 T2 T1 26 Elementary maths for GMT Algorithm analysis - Trees
Tri-node restructuring - Summary 27 Elementary maths for GMT Algorithm analysis - Trees
Removal in an AVL tree Removal begins as in a binary search tree, which means the node removed will become an empty node Example: remove 5 in the following AVL tree 6 6 unbalanced! 4 11 4 11 14 8 5 14 8 17 17 7 9 7 9 28 Elementary maths for GMT Algorithm analysis - Trees
Unbalanced after removal Let w be the parent of the removed node (here 4) Let z be the first unbalanced ancestor of w (here 6) Let y be the child of z with higher height (is now not an ancestor of w) (here 11) Let x be the child of y with higher height if heights are different, or the child of y on the same side as y if heights are equal (here 14) z 6 y w 4 11 x 14 8 17 7 9 29 Elementary maths for GMT Algorithm analysis - Trees
Rebalancing after a removal Performs rotations to make y the top most of the z-y-x tree As this restructuring may upset the balance of another node higher in the tree, we must continue checking for balance until the root is reached z 11 6 y w 6 4 14 11 8 4 x 17 14 8 7 9 17 7 9 30 Elementary maths for GMT Algorithm analysis - Trees
Repeated rebalancing Example: remove 4 11 11 6 19 unbalanced! 6 19 8 22 15 4 8 22 15 7 26 7 26 12 18 12 18 17 17 31 Elementary maths for GMT Algorithm analysis - Trees
Repeated balancing unbalanced! 11 7 19 8 22 15 6 26 12 18 17 32 Elementary maths for GMT Algorithm analysis - Trees
Running times for AVL trees Finding a value takes ?(log?) time because height of a tree is always ?(log?) Traversal of the whole set takes ?(?) time Insertion takes ?(log?) time Initial find takes ?(log?) time 0 or 1 rebalancing of the tree, maintaining height takes ?(log?) time Removal takes ?(log?) time Initial find takes ?(log?) time 0 or more rebalancing of the tree, maintaining height takes ?(log?) time 33 Elementary maths for GMT Algorithm analysis - Trees
AVL trees vs. hash tables In an AVL tree, insert/delete/search is ?(log?) time, in a hash table they take ?(1) time in practice In an AVL tree, searching for the smallest value ? takes ?(log?) time, in a hash table it takes a linear time Enumerating the set in order takes ?(?) time in an AVL tree, in a hash table it cannot be done quickly: ?(?log?) Finding the number of values between given x and y takes ?(log?) time with a simple variation of an AVL tree, in a hash table it takes linear time An AVL tree is more versatile than a hash table 34 Elementary maths for GMT Algorithm analysis - Trees
Other trees BB[ ]-tree are not height-balanced but weight-balanced. Height is also ?(log?) Red-black trees are balanced with a different scheme and also have height ?(log?) For background storage, B-trees exist and have a degree higher than two (more than 2 children) For 2- and higher-dimensional data, various trees exist Kd-trees Quadtrees and octrees BSP-trees Range trees R-trees 35 Elementary maths for GMT Algorithm analysis - Trees
