Java Reference
In-Depth Information
Chapter
27
Balanced
Search Trees
Contents
AVL Trees
Single Rotations
Double Rotations
Implementation Details
2-3 Trees
Searching a 2-3 Tree
Adding Entries to a 2-3 Tree
Splitting Nodes During Addition
2-4 Trees
Adding Entries to a 2-4 Tree
Comparing AVL, 2-3, and 2-4 Trees
Red-Black Trees
Properties of a Red-Black Tree
Adding Entries to a Red-Black Tree
Java Class Library: The Class
TreeMap
B-Trees
Prerequisites
Chapter
23
Trees
Chapter
24
Tree Implementations
Chapter
25
A Binary Search Tree Implementation
Objectives
After studying this chapter, you should be able to
•
Perform a rotation to restore the balance of an AVL tree after an addition
•
Search for or add an entry to a 2-3 tree
•
Search for or add an entry to a 2-4 tree
•
Form a red-black tree from a given 2-4 tree
•
Search for or add an entry to a red-black tree
•
Describe the purpose of a B-tree
