CS计算机代考程序代写 Java AVL algorithm Tree Traversal

Tree Traversal
• Many different algorithms for manipulating trees exist, but these algorithms have in common that they systematically visit all the nodes in the tree.
• There are essentially two methods for visiting all nodes in a tree:
• Depth-first traversal,
• Breadth-first traversal.
373
© Dr Markus Lumpe, 2021

Depth-first Traversal
• Pre-order traversal:
• Visit the root first; and then
• Do a preorder traversal of each of the subtrees of the root one-by-one in the order given (from left to right).
• Post-order traversal:
• Do a postorder traversal of each of the subtrees of the root one-by-one in the
order given (from left to right); and then
• Visit the root.
• In-order traversal:
• Traverse the left subtree; and then
• Visit the root; and then
• Traverse the right subtree.
374
© Dr Markus Lumpe, 2021

Breadth-first Traversal
• Breadth-first traversal visits the nodes of a tree in the order of their depth (from left to right).
375
© Dr Markus Lumpe, 2021

Pre-order Traversal Example
1
2E 4F
3H5G7
Depth = 0: Depth = 1:
Depth = 2: Depth = 3:
D
D-E-H-F-G-I-J-K-L
J
6 I
8 K
9 L
© Dr Markus Lumpe, 2021
376

Post-order Traversal Example
9
2E 8F
1H4G7
Depth = 0: Depth = 1:
Depth = 2: Depth = 3:
D
H-E-I-G-K-L-J-F-D
J
3 I
5 K
6 L
© Dr Markus Lumpe, 2021
377

In-order Traversal Example
3
2E 6F
1H5G8
Depth = 0: Depth = 1:
Depth = 2: Depth = 3:
D
H-E-D-I-G-F-K-J-L
J
4 I
7 K
9 L
© Dr Markus Lumpe, 2021
378

Breadth-first Traversal Example
1
2E 3F
4H5G6
Depth = 0: Depth = 1:
Depth = 2: Depth = 3:
D
D-E-F-H-G-J-I-K-L
J
7 I
8 K
9 L
© Dr Markus Lumpe, 2021
379

The Visitor Pattern
• Intent:
• Represent an operation to be performed on the elements of an object structure. Visitor lets one define a new operation without changing the classes of the elements on which it operates.
• Collaborations:
• A client that uses the Visitor pattern must create a ConcreteVisitor object and then traverse the object structure, visiting each element with the visitor.
• When an element is visited, it calls the Visitor operation that corresponds to its class. The element supplies itself as an argument to this operation to let the visitor access its state, if necessary.
380
© Dr Markus Lumpe, 2021

Structure of Visitor
Client ObjectStructure
Visitor
VisitElementA(A)
VisitElementB(B)
Element
Accept( Visitor)
ConcreteVisitor2
VisitElementA(A)
VisitElementB(B)
ConcreteVisitor1
VisitElementA(A)
VisitElementB(B)
ElementB
Accept( Visitor)
OperationB()
© Dr Markus Lumpe, 2
ElementA
Accept( Visitor)
OperationA()
381
021

A Tree Visitor
382
© Dr Markus Lumpe, 2021

PreOrderVisitor
383
© Dr Markus Lumpe, 2021

PostOrderVisitor
384
© Dr Markus Lumpe, 2021

InOrderVisitor
385
© Dr Markus Lumpe, 2021

Depth-first Traversal for BTree
386
© Dr Markus Lumpe, 2021

387
© Dr Markus Lumpe, 2021

Breadth-first Traversal Implementation
D
EF G
Traversal Queue
D FE
HFE JGH F JGH IJG LKI J LK
L
D
H
I
J KL
I K L
D-E-F-H-G-J-I-K-L
388
© Dr Markus Lumpe, 2021

Breadth-first Traversal for BTree
389
© Dr Markus Lumpe, 2021

M-way Search Tree
• An M-ary search tree T is a finite set of nodes with one of the following properties:
• either the set is empty, T = ∅, or
• for 2 ≤ n ≤ M, the set consists of n M-ary subtrees T1, T2, …, Tn-1, Tn and
n-1 keys k1, k2, …, kn-1.
and the keys and nodes satisfy the data ordering properties:
• The keys in each node are distinct and ordered, i.e., ki < ki+1, for 1 ≤ i ≤ n-1. • All the keys contained in subtree Ti-1 are less than ki, i.e., ∀k ∈ Ti-1: k < ki, for 1 ≤ i ≤ n-1. The tree Ti-1 is called left subtree with respect the key ki. • All the keys contained in subtree Ti are greater than ki, i.e., ∀k ∈ Ti: k > ki, for 1 ≤ i ≤ n-1. The tree Ti is called right subtree with respect the key ki.
391
© Dr Markus Lumpe, 2021

2-way Search Tree
• A 2-ary (binary) search tree T is a finite set of nodes with one of the following properties:
• either the set is empty, T = ∅, or
• the set consists of one key, r, and exactly 2 binary subtrees TL and TR such that following properties are satisfied:
All the keys in the left subtree, TL, are less than r, i.e., ∀k All the keys contained in the right subtree, TR, are
•
∈ TL: k < r. • greater than r, i.e., ∀k ∈ TR: k > r.
393
© Dr Markus Lumpe, 2021

Traversing a Binary Search Tree
• Binary Tree Search:
Traverse the left subtree, and then Visit the root, and then
Traverse the right subtree.
• We use in-order traversal to search for a given key in an M-ary search tree.
• • •
395
© Dr Markus Lumpe, 2021

Binary Search Tree Operations
25 Insert 8 25
10 37 10 37
15 30 65
8 15 30 65
! The predecessor of 25 37
Delete 25
15 10
396
© Dr Markus Lumpe, 2021
30
65

Insert 8:
< 25 10 37 8 15 30 65 1. 8 < 25 10 37 8 25 15 30 65 10 37 15 30 65 2. 397 © Dr Markus Lumpe, 2021 findMax() == 15 1. 15 2.10 37 15 15 30 65 10==15 37 15 30 65 15 10 25 ==25 37 15 30 65 15 37 30 65 4. © Dr Markus Lumpe, 2021 10 3. Delete 25: 15 10 == 15 398 30 37 65 We define the representation of a binary search tree in class BNode. 399 © Dr Markus Lumpe, 2021 400 © Dr Markus Lumpe, 2021 Remove and Depth-first Traversal • The class BSTree defines an adapter for BSTNode. • The operation insert can be defined as a simple while-loop over BSTNodes from the root node. • The operations remove and traverseDepthFirst use recursion to explore BSTNodes. In the beginning, both start with the root node. 401 © Dr Markus Lumpe, 2021 402 © Dr Markus Lumpe, 2021 Binary Search Tree Test 403 © Dr Markus Lumpe, 2021 Other Tree Variants • Rose Trees (directories) • Expression Trees (internal program representation) • Multi-rooted trees (C++: multiple inheritance) • Red-Black Trees (directories in compound documents, java.util.TreeMap) • AVL Trees (Adelson-Velskii & Landis balanced BTrees) 404 © Dr Markus Lumpe, 2021 AVL vs. Red-Black Trees • Both AVL trees and Red-Black trees are self-balancing binary search trees. However, the operations to balance the trees are different. • AVL and Red-Black trees have different height limits. For a tree of size n: • An AVL tree's height is limited to 1.44log2(n). • A Red-Black tree's height is limited to 2log2(n). • The AVL tree is more rigidly balanced than Red-Black trees, leading to slower insertion and removal but faster retrieval. 405 © Dr Markus Lumpe, 2021

Related Posts