程序代写代做代考 algorithm AVL data structure PowerPoint Presentation

PowerPoint Presentation

Balanced Search Trees
Chapter 19
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

Contents
Balanced Search Trees
2-3 Trees
2-3-4 Trees
Red-Black Trees
AVL Trees

Balanced Search Trees
Height of a binary search tree sensitive to order of insertions and removals

Minimum = log2 (n + 1)
Maximum = n
Various search trees can retain balance despite insertions and removals

Balanced Search Trees
FIGURE 19-1 (a) A binary search tree of maximum height; (b) a binary search tree of minimum height
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

2-3 Trees
FIGURE 19-2 A 2-3 tree of height 3
A 2-3 tree not a binary tree
A 2-3 tree never taller than a minimum-height binary tree

2-3 Trees
Placing data items in nodes of a 2-3 tree

A 2-node (has two children) must contain single data item greater than left child’s item(s) and less than right child’s item(s)
A 3-node (has three children) must contain two data items, S and L , such that
S is greater than left child’s item(s) and less than middle child’s item(s);
L is greater than middle child’s item(s) and less than right child’s item(s).
Leaf may contain either one or two data items.
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

2-3 Trees
FIGURE 19-3 Nodes in a 2-3 tree: (a) a 2-node;
(b) a 3-node
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013`

2-3 Trees
FIGURE 19-4 A 2-3 tree
View Header file for a class of nodes for a 2-3 tree, Listing 19-1
.htm code listing files must be in the same folder as the .ppt files for these links to work
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

Traversing a 2-3 Tree
Traverse 2-3 tree
in sorted order
by performing
analogue of
inorder traversal
on binary tree:

Searching a 2-3 Tree
Retrieval operation for 2-3 tree similar to retrieval operation for binary search tree

Searching a 2-3 Tree
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

Searching a 2-3 Tree
Possible to search 2-3 tree and shortest binary search tree with approximately same efficiency, because:

Binary search tree with n nodes cannot be shorter than log2 (n + 1)
2-3 tree with n nodes cannot be taller than
log2 (n + 1)
Node in a 2-3 tree has at most two items
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

Searching a 2-3 Tree
FIGURE 19-5 (a) A balanced binary search tree;
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

Searching a 2-3 Tree
FIGURE 19-5 (b) a 2-3 tree with the same entries
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

Searching
a 2-3 Tree
FIGURE 19-6 (a) The binary search tree of Figure 19-5a after inserting the sequence of values 32 through 39
(b) the 2-3 tree of Figure 19-5 b after the same insertions
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

Inserting Data into a 2-3 Tree
FIGURE 19-7 After inserting 39 into the
tree in Figure 19-5b
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

Inserting Data into a 2-3 Tree
FIGURE 19-8 The steps for inserting 38 into the tree in Figure 19-7: (a) The located node has no room;
(b) the node splits; (c) the resulting tree
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

Inserting Data into a 2-3 Tree
FIGURE 19-9 After inserting 37 into the tree
in Figure 19-8c
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

Inserting Data into a 2-3 Tree
FIGURE 19-10 (a), (b), (c) The steps for inserting
36 into the tree in Figure 19-9
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

Inserting Data into a 2-3 Tree
FIGURE 19-10 (d) the resulting tree
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

Inserting Data into a 2-3 Tree
FIGURE 19-11 The tree after the insertion of 35, 34, and 33 into the tree in Figure 19-10d
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

Inserting Data into a 2-3 Tree
FIGURE 19-12 Splitting a leaf in a 2-3 tree when the leaf is a (a) left child; (b) right child
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

Inserting Data into a 2-3 Tree
FIGURE 19-13 Splitting an internal node in a 2-3 tree when the node is a (a) left child; (b) right child
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

Inserting Data into a 2-3 Tree
FIGURE 19-14 Splitting the root of a 2-3 tree
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

Inserting Data into a 2-3 Tree
Summary of insertion strategy

Removing Data from a 2-3 Tree
FIGURE 19-15 (a) A 2-3 tree; (b), (c), (d), (e)
the steps for removing 70;
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

Removing Data from a 2-3 Tree
FIGURE 19-15 (f) the resulting tree;
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

Removing Data from a 2-3 Tree
FIGURE 19-16 (a), (b), (c) The steps for removing 100 from the tree in Figure 19-15f; (d) the resulting tree
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

Removing Data from a 2-3 Tree
FIGURE 19-17 The steps for removing 80 from
the tree in Figure 19-16d
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

Removing Data from a 2-3 Tree
FIGURE 19-18 Results of removing 70, 100, and 80 from (a) the 2-3 tree of Figure 19-15 a and (b) the binary search tree of Figure 19-5 a
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

Removing Data from a 2-3 Tree
Algorithm for removing data from a 2-3 tree

Removing Data from a 2-3 Tree
FIGURE 19-19 (a) Redistributing values;
(b) merging a leaf;
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

Removing Data from a 2-3 Tree
FIGURE 19-19 (c) redistributing values and
children; (d) merging internal nodes
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

Removing Data from a 2-3 Tree
FIGURE 19-19 (e) deleting the root
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

2-3-4 Trees
FIGURE 19-20 A 2-3-4 tree with the same data items as the 2-3 tree in Figure 19-6 b
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

2-3-4 Trees
Rules for placing data items in the nodes of a 2-3-4 tree

2-node (two children), must contain a single data item that satisfies relationships pictured in Figure 19-3 a.
3-node (three children), must contain a single data item that satisfies relationships pictured in Figure 19-3 b.
. . .
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

2-3-4 Trees
4-node (four children) must contain three data items S , M , and L that satisfy:
S is greater than left child’s item(s) and less than middle-left child’s item(s)
M is greater than middle-left child’s item(s) and less than middle-right child’s item(s);
L is greater than middle-right child’s item(s) and less than right child’s item(s).
A leaf may contain either one, two, or three data items
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

2-3-4 Trees
FIGURE 19-21 A 4-node in a 2-3-4 tree
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

2-3-4 Trees
Has more efficient insertion and removal operations than a 2-3 tree
Has greater storage requirements due to the additional data members in its 4-nodes

2-3-4 Trees
Searching and Traversing a 2-3-4 Tree

Simple extensions of the corresponding algorithms for a 2-3 tree
Inserting Data into a 2-3-4 Tree

Insertion algorithm splits a node by moving one of its items up to its parent node
Splits 4-nodes as soon as it encounters them on the way down the tree from the root to a leaf
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

2-3-4 Trees
FIGURE 19-22 Inserting 20 into a one-node 2-3-4 tree (a) the original tree; (b) after
splitting the node; (c) after inserting 20
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

2-3-4 Trees
FIGURE 19-23 After inserting 50 and 40
into the tree in Figure 19-22c
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

2-3-4 Trees
FIGURE 19-24 The steps for inserting 70 into the
tree in Figure 19-23: (a) after splitting the
4-node; (b) after inserting 70
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

2-3-4 Trees
FIGURE 19-25 After inserting 80 and 15
into the tree in Figure 19-24b
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

2-3-4 Trees
FIGURE 19-26 The steps for inserting 90
into the tree in Figure 19-25
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

2-3-4 Trees
FIGURE 19-27 The steps for inserting 100
into the tree in Figure 19-26b
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

2-3-4 Trees
FIGURE 19-28 Splitting a 4-node root
during insertion into a 2-3-4 tree
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

2-3-4 Trees
FIGURE 19-29 Splitting a 4-node whose parent is a
2-node during insertion into a 2-3-4 tree, when the
4-node is a (a) left child; (b) right child
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

2-3-4 Trees
FIGURE 19-30 Splitting a 4-node whose parent is a
3-node during insertion into a 2-3-4 tree, when the
4-node is a (a) left child
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

2-3-4 Trees
FIGURE 19-30 Splitting a 4-node whose parent is a
3-node during insertion into a 2-3-4 tree, when the
4-node is a (b) middle child
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

2-3-4 Trees
FIGURE 19-30 Splitting a 4-node whose parent is a
3-node during insertion into a 2-3-4 tree, when the
4-node is a (c) right child
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

2-3-4 Trees
Removing Data from a 2-3-4 Tree

Removal algorithm has same beginning as removal algorithm for a 2-3 tree
Locate the node n that contains the item I you want to remove
Find I ’s inorder successor and swap it with I so that the removal will always be at a leaf
If leaf is either a 3-node or a 4-node, remove I .
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

Red-Black Trees
Use a special binary search tree—a red-black tree —to represent a 2-3-4 tree
Retains advantages of a 2-3-4 tree without storage overhead
The idea is to represent each 3-node and 4-node in a 2-3-4 tree as an equivalent binary search tree

Red-Black Trees
FIGURE 19-31 Red-black representation of
(a) a 4-node; (b) a 3-node
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

Red-Black Trees
FIGURE 19-32 A red-black tree that represents
the 2-3-4 tree in Figure 19-20
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

Red-Black Trees
Searching and traversing

Red-black tree is a binary search tree, search and traverse it by using algorithms for binary search tree
Inserting, removing with a red-black tree

Adjust the 2-3-4 insertion algorithms to accommodate the red-black representation
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

Red-Black Trees
FIGURE 19-33 Splitting a red-black
representation of a 4-node that is the root
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

Red-Black Trees
FIGURE 19-34 Splitting a red-black representation
of a 4-node whose parent is a 2-node,
when the 4-node is a (a) left child
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

Red-Black Trees
FIGURE 19-34 Splitting a red-black representation
of a 4-node whose parent is a 2-node,
when the 4-node is a (b) right child
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

Red-Black
Trees
FIGURE 19-35 Splitting a red-black representation of a 4-node whose parent is a 2-node
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

AVL Trees
Named for inventors, Adel’son-Vel’skii and Landis
A balanced binary search tree

Maintains height close to the minimum
After insertion or deletion, check the tree is still AVL tree – determine whether any node in tree has left and right subtrees whose heights differ by more than 1
Can search AVL tree almost as efficiently as minimum-height binary search tree.

AVL Trees
FIGURE 19-36 (a) An unbalanced binary search tree;
(b) a balanced tree after rotation;
(c) a balanced tree after insertion
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

AVL Trees
FIGURE 19-37 (a) Before; (b) and after a single left rotation that decreases the tree’s height;
(c) the rotation in general
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

AVL Trees
FIGURE 19-38 (a) Before; (b) and after a single left rotation that does not affect the tree’s
height; (c) the rotation in general
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

AVL Trees
FIGURE 19-39 (d) the double rotation in general
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

Related Posts