CS计算机代考程序代写 data structure AVL algorithm COMP20007 Design of Algorithms

COMP20007 Design of Algorithms
Binary Search Trees and their Extensions
Daniel Beck
Lecture 14
Semester 1, 2020
1

Dictionaries
2

Dictionaries
• Abstract Data Structure
2

Dictionaries
• Abstract Data Structure
• Collection of (key, value) pairs
2

Dictionaries
• Abstract Data Structure
• Collection of (key, value) pairs
• Values are usually records, such as my videogames or the Unimelb students.
2

Dictionaries
• Abstract Data Structure
• Collection of (key, value) pairs
• Values are usually records, such as my videogames or the Unimelb students.
• Keys are (unique) identifiers, such as the name of a game or the student ID.
• Required operations:
• Search for a value (given a key)
• Insert a new pair
• Delete an existent pair (given a key)
2

Dictionaries – Implementations
3

Dictionaries – Implementations
Unsorted array / Linked list
• Search: Θ(n) comparisons;
3

Dictionaries – Implementations
Unsorted array / Linked list
• Search: Θ(n) comparisons;
Sorted array
• Search: Θ(log n) comparisons;
3

Dictionaries – Implementations
Unsorted array / Linked list
• Search: Θ(n) comparisons;
Sorted array
• Search: Θ(log n) comparisons;
• Insert/Delete: Θ(n) record swaps;
3

Dictionaries – Implementations
Unsorted array / Linked list
• Search: Θ(n) comparisons;
Sorted array
• Search: Θ(log n) comparisons;
• Insert/Delete: Θ(n) record swaps; This lecture: a better data structure
3

Binary Search Tree
10
5 20
3 7 12 25
4

Binary Search Tree – Worst Case
25 20
12 10
7 5
3
5

BST – How to avoid degeneracy?
Two options:
6

BST – How to avoid degeneracy?
Two options:
• Self-balancing
• AVL trees
• Red-black trees • Splay trees
6

BST – How to avoid degeneracy?
Two options:
• Self-balancing
• AVL trees
• Red-black trees • Splay trees
• Change the representation
• 2-3 trees • 2-3-4 trees • B-trees
6

AVL trees
7

AVL trees
• Named after Adelson-Velsky and Landis.
7

AVL trees
• Named after Adelson-Velsky and Landis.
• A BST where each node has a balance factor: the difference in height between the left and right subtrees.
7

AVL trees
• Named after Adelson-Velsky and Landis.
• A BST where each node has a balance factor: the difference in height between the left and right subtrees.
• When the balance factor becomes 2 or -2, rotate the tree to adjust them.
7

AVL Trees: Examples and Counter-Examples
Which of these are AVL trees?
10 10 10
5 20 5 20 520
3 7 12 25 3 7 12 2108 2
5 20 3 7 25
24 8 29
3 7
8

AVL Trees – Rotations
• Search is done as in BSTs.
9

AVL Trees – Rotations
• Search is done as in BSTs.
• Insertion and Deletion also done as in BSTs, with additional steps at the end.
9

AVL Trees – Rotations
• Search is done as in BSTs.
• Insertion and Deletion also done as in BSTs, with additional steps at the end.
• Update balance factors.
• If the tree becomes unbalanced, perform rotations to
rebalance it.
9

AVL Trees: R-Rotation
2
3 1
2 0
1
10

AVL Trees: R-Rotation
20
32 1⇒00 213
0 1
10

AVL Trees: L-Rotation
-2 1
-1 2
0 3
11

AVL Trees: L-Rotation
-2 0 12
-1 ⇒0 0 213
0 3
11

AVL Trees: LR-Rotation
2
3 -1
1
0
2
12

AVL Trees: LR-Rotation
20
32
-1 ⇒0 0 113
0 2
12

AVL Trees: RL-Rotation
-2 1
1
3 0
2
13

AVL Trees: RL-Rotation
-2 0 12
1⇒00
313 0
2
13

AVL Trees: Where to Perform the Rotation
Along an unbalanced path, we may have several
nodes with balance factor 2 (or -2): 21
44 20⇒00 3525
100
213 0
1
It is always the lowest unbalanced subtree that is re-balanced.
14

AVL Trees: The Single Rotation, Generally
20 rc
10 c􏰛􏰛r
T3 ⇒ T1
􏰛􏰛 􏰛􏰛
T1 T2 T2 T3
This shows an R-rotation; an L-rotation is similar.
15

AVL Trees: The Double Rotation, Generally
20
g
-1 10 c􏰛 cr
r -1
􏰛g􏰛􏰛􏰛􏰛
T4 􏰛􏰛
⇒
T2 T3 T1TTT1 T4
23
This shows an LR-rotation; an RL-rotation is similar.
16

Properties of AVL Trees
• Rotations ensure that an AVL tree is always balanced.
17

Properties of AVL Trees
• Rotations ensure that an AVL tree is always balanced. • An AVL tree with n nodes has depth Θ(log n).
17

Properties of AVL Trees
• Rotations ensure that an AVL tree is always balanced. • An AVL tree with n nodes has depth Θ(log n).
• This ensures all three operations are Θ(log n).
17

Red-black Trees
• A red-black tree is another self-balancing BST. • Its nodes are coloured red or black, so that:
1. No red node has a red child.
12
9 15
6 10
A worst-case red-black tree (the longest path is twice as long as the shortest path).
2. Every path from the root to the leaves has the same number of black nodes.
4
18

Self-balancing trees – In practice
AVL trees vs. red-black trees
19

Self-balancing trees – In practice
AVL trees vs. red-black trees
• AVL trees are “more balanced” but require more frequent rotations.
• Better if searches are more frequent than insertions/deletions.
• Red-black trees are “less balanced” but require less rotations.
• Better if insertions/deletions are more frequent than searches.
19

Representational Changes
20

Representational Changes
• Goal is the same: keep the tree balanced.
20

Representational Changes
• Goal is the same: keep the tree balanced.
• But instead of relying on rotations, we will allow multiple elements per node and multiple children per node.
20

Representational Changes
• Goal is the same: keep the tree balanced.
• But instead of relying on rotations, we will allow multiple elements per node and multiple children per node.
• 2–3 trees: contains only 2-nodes and 3-nodes.
• A 2-node contains one element and at most two children (as in BSTs)
• A 3-node contains two elements and at most three children.
20

2-Nodes and 3-Nodes
21

2-Nodes and 3-Nodes
2-node
n
􏰛􏰛
greater than n than n
smaller
21

2-Nodes and 3-Nodes
2-node 3-node
n m,n 􏰛􏰛􏰛􏰛􏰛
smaller greater smaller between greater than n than n than m m and n than n
21

Insertion in a 2–3 Tree
22

Insertion in a 2–3 Tree
• As in a BST, pretend that we are searching for k.
22

Insertion in a 2–3 Tree
• As in a BST, pretend that we are searching for k.
• If the leaf node is a 2-node, insert k, becoming a 3-node.
22

Insertion in a 2–3 Tree
• As in a BST, pretend that we are searching for k.
• If the leaf node is a 2-node, insert k, becoming a 3-node. • Otherwise, momentarily form a node with three elements:
• In sorted order, call them k1, k2, and k3.
• Split the node, so that k1 and k3 form their own
individual 2-nodes, and k2 is promoted to the parent node.
22

Example: Build a 2–3 Tree from 9, 5, 8, 3, 2, 4, 7
9
23

Example: Build a 2–3 Tree from 9, 5, 8, 3, 2, 4, 7
9 ⇒ 5,9
23

Example: Build a 2–3 Tree from 9, 5, 8, 3, 2, 4, 7
9 ⇒ 5,9 ⇒ 5,8,9
23

Example: Build a 2–3 Tree from 9, 5, 8, 3, 2, 4, 7
9 ⇒ 5,9 ⇒ 5,8,9 ⇒
8
59
23

Example: Build a 2–3 Tree from 9, 5, 8, 3, 2, 4, 7
88 9 ⇒ 5,9 ⇒ 5,8,9 ⇒ ⇒
5 9 3,5 9
23

Example: Build a 2–3 Tree from 9, 5, 8, 3, 2, 4, 7
9 ⇒ 5,9 ⇒ 5,8,9 ⇒
88
⇒ ⇒
5 9 3,5 9
8
2,3,5
9
23

Example: Build a 2–3 Tree from 9, 5, 8, 3, 2, 4, 7
88
9 ⇒ 5,9 ⇒ 5,8,9 ⇒ ⇒ ⇒
5 9 3,5 9
8 ⇒ 3,8
2,3,5 9 2 5 9
23

Example: Build a 2–3 Tree from 9, 5, 8, 3, 2, 4, 7
88
9 ⇒ 5,9 ⇒ 5,8,9 ⇒ ⇒ ⇒
5 9 3,5 9
8 ⇒ 3,8 ⇒ 3,8
2,3,5 9 2 5 9 2 4,5 9
23

Example: Build a 2–3 Tree from 9, 5, 8, 3, 2, 4, 7
2
88
9 ⇒ 5,9 ⇒ 5,8,9 ⇒ ⇒ ⇒
5 9 3,5 9
8 ⇒ 3,8 ⇒ 3,8 ⇒ 2,3,5 9 2 5 9 2 4,5 9
3,8
4,5,7 9
23

Example: Build a 2–3 Tree from 9, 5, 8, 3, 2, 4, 7
88
9 ⇒ 5,9 ⇒ 5,8,9 ⇒ ⇒ ⇒
5 9 3,5 9
8 ⇒ 3,8 ⇒ 3,8 ⇒ 2,3,5 9 2 5 9 2 4,5 9
3,8
⇒
3,5,8
2 4,5,7 92 4 7 9
23

Example: Build a 2–3 Tree from 9, 5, 8, 3, 2, 4, 7
88
9 ⇒ 5,9 ⇒ 5,8,9 ⇒ ⇒ ⇒
5 9 3,5 9
8 ⇒ 3,8 ⇒ 3,8 ⇒ 2,3,5 9 2 5 9 2 4,5 9
5
38
2479
3,8 3,5,8
⇒⇒
2 4,5,7 92 4 7 9
23

Exercise: 2–3 Tree Construction
Build the 2–3 tree that results from inserting these keys, in the given order, into an initially empty tree:
C, O, M, P, U, T, I, N, G
24

Extensions
• 2–3–4 trees: includes 4-nodes.
25

Extensions
• 2–3–4 trees: includes 4-nodes.
• B-trees: a generalisation. (2–3 trees are B-trees of order 3)
25

Extensions
• 2–3–4 trees: includes 4-nodes.
• B-trees: a generalisation. (2–3 trees are B-trees of order 3)
• B+-trees: internal nodes only contain keys, values are all in the leaves (plus a bunch of optimisations)
25

Related Posts