www.delorie.com/gnu/docs/avl/libavl_toc.html

search

	Buy GNU books!

GNU libavl 2.0.1

Table of Contents

Preface

1.0 Acknowledgements
1.1 Contacting the Author

2. Introduction

2.1 Audience
2.2 Reading the Code
2.3 Code Conventions
2.4 License

3. The Table ADT

3.1 Informal Definition
3.2 Identifiers
3.3 Comparison Function
3.4 Item and Copy Functions
3.5 Memory Allocation
3.6 Creation and Destruction
3.7 Count
3.8 Insertion and Deletion
3.9 Assertions
3.10 Traversers

3.10.1 Constructors
3.10.2 Manipulators

3.11 Table Headers
3.12 Additional Exercises

4. Search Algorithms

4.1 Sequential Search
4.2 Sequential Search with Sentinel
4.3 Sequential Search of Ordered Array
4.4 Sequential Search of Ordered Array with Sentinel
4.5 Binary Search of Ordered Array
4.6 Binary Search Tree in Array
4.7 Dynamic Lists

5. Binary Search Trees

5.1 Vocabulary

5.1.1 Aside: Differing Definitions

5.2 Data Types

5.2.1 Node Structure
5.2.2 Tree Structure
5.2.3 Maximum Height

5.3 Rotations
5.4 Operations
5.5 Creation
5.6 Search
5.7 Insertion

5.7.1 Aside: Root Insertion

5.8 Deletion

5.8.1 Aside: Deletion by Merging

5.9 Traversal

5.9.1 Traversal by Recursion
5.9.2 Traversal by Iteration

5.9.2.1 Improving Convenience

5.9.3 Better Iterative Traversal

5.9.3.1 Starting at the Null Node
5.9.3.2 Starting at the First Node
5.9.3.3 Starting at the Last Node
5.9.3.4 Starting at a Found Node
5.9.3.5 Starting at an Inserted Node
5.9.3.6 Initialization by Copying
5.9.3.7 Advancing to the Next Node
5.9.3.8 Backing Up to the Previous Node
5.9.3.9 Getting the Current Item
5.9.3.10 Replacing the Current Item

5.10 Copying

5.10.1 Recursive Copying
5.10.2 Iterative Copying
5.10.3 Error Handling

5.11 Destruction

5.11.1 Destruction by Rotation
5.11.2 Aside: Recursive Destruction
5.11.3 Aside: Iterative Destruction

5.12 Balance

5.12.1 From Tree to Vine
5.12.2 From Vine to Balanced Tree

5.12.2.1 General Trees
5.12.2.2 Implementation
5.12.2.3 Implementing Compression

5.13 Aside: Joining BSTs
5.14 Testing

5.14.1 Testing BSTs

5.14.1.1 BST Verification
5.14.1.2 Displaying BST Structures

5.14.2 Test Set Generation
5.14.3 Testing Overflow
5.14.4 Memory Manager
5.14.5 User Interaction
5.14.6 Utility Functions
5.14.7 Main Program

5.15 Additional Exercises

6. AVL Trees

6.1 Balancing Rule

6.1.1 Analysis

6.2 Data Types
6.3 Operations
6.4 Insertion

6.4.1 Step 1: Search
6.4.2 Step 2: Insert
6.4.3 Step 3: Update Balance Factors
6.4.4 Step 4: Rebalance
6.4.5 Symmetric Case
6.4.6 Example
6.4.7 Aside: Recursive Insertion

6.5 Deletion

6.5.1 Step 1: Search
6.5.2 Step 2: Delete
6.5.3 Step 3: Update Balance Factors
6.5.4 Step 4: Rebalance
6.5.5 Step 5: Finish Up
6.5.6 Symmetric Case

6.6 Traversal
6.7 Copying
6.8 Testing

7. Red-Black Trees

7.1 Balancing Rule

7.1.1 Analysis

7.2 Data Types
7.3 Operations
7.4 Insertion

7.4.1 Step 1: Search
7.4.2 Step 2: Insert
7.4.3 Step 3: Rebalance
7.4.4 Symmetric Case
7.4.5 Aside: Initial Black Insertion

7.4.5.1 Symmetric Case

7.5 Deletion

7.5.1 Step 2: Delete
7.5.2 Step 3: Rebalance
7.5.3 Step 4: Finish Up
7.5.4 Symmetric Case

7.6 Testing

8. Threaded Binary Search Trees

8.1 Threads
8.2 Data Types
8.3 Operations
8.4 Creation
8.5 Search
8.6 Insertion
8.7 Deletion
8.8 Traversal

8.8.1 Starting at the Null Node
8.8.2 Starting at the First Node
8.8.3 Starting at the Last Node
8.8.4 Starting at a Found Node
8.8.5 Starting at an Inserted Node
8.8.6 Initialization by Copying
8.8.7 Advancing to the Next Node
8.8.8 Backing Up to the Previous Node

8.9 Copying
8.10 Destruction
8.11 Balance

8.11.1 From Tree to Vine
8.11.2 From Vine to Balanced Tree

8.12 Testing

9. Threaded AVL Trees

9.1 Data Types
9.2 Rotations
9.3 Operations
9.4 Insertion

9.4.1 Steps 1 and 2: Search and Insert
9.4.2 Step 4: Rebalance
9.4.3 Symmetric Case

9.5 Deletion

9.5.1 Step 1: Search
9.5.2 Step 2: Delete
9.5.3 Step 3: Update Balance Factors
9.5.4 Step 4: Rebalance
9.5.5 Symmetric Case
9.5.6 Finding the Parent of a Node

9.6 Copying
9.7 Testing

10. Threaded Red-Black Trees

10.1 Data Types
10.2 Operations
10.3 Insertion

10.3.1 Steps 1 and 2: Search and Insert
10.3.2 Step 3: Rebalance
10.3.3 Symmetric Case

10.4 Deletion

10.4.1 Step 1: Search
10.4.2 Step 2: Delete
10.4.3 Step 3: Rebalance
10.4.4 Step 4: Finish Up
10.4.5 Symmetric Case

10.5 Testing

11. Right-Threaded Binary Search Trees

11.1 Data Types
11.2 Operations
11.3 Search
11.4 Insertion
11.5 Deletion

11.5.1 Right-Looking Deletion
11.5.2 Left-Looking Deletion
11.5.3 Aside: Comparison of Deletion Algorithms

11.6 Traversal

11.6.1 Starting at the First Node
11.6.2 Starting at the Last Node
11.6.3 Starting at a Found Node
11.6.4 Advancing to the Next Node
11.6.5 Backing Up to the Previous Node

11.7 Copying
11.8 Destruction
11.9 Balance
11.10 Testing

12. Right-Threaded AVL Trees

12.1 Data Types
12.2 Operations
12.3 Rotations
12.4 Insertion

12.4.1 Steps 1--2: Search and Insert
12.4.2 Step 4: Rebalance

12.5 Deletion

12.5.1 Step 1: Search
12.5.2 Step 2: Delete
12.5.3 Step 3: Update Balance Factors
12.5.4 Step 4: Rebalance

12.6 Copying
12.7 Testing

13. Right-Threaded Red-Black Trees

13.1 Data Types
13.2 Operations
13.3 Insertion

13.3.1 Steps 1 and 2: Search and Insert
13.3.2 Step 3: Rebalance

13.4 Deletion

13.4.1 Step 2: Delete
13.4.2 Step 3: Rebalance
13.4.3 Step 4: Finish Up

13.5 Testing

14. BSTs with Parent Pointers

14.1 Data Types
14.2 Operations
14.3 Insertion
14.4 Deletion
14.5 Traversal

14.5.1 Starting at the First Node
14.5.2 Starting at the Last Node
14.5.3 Starting at a Found Node
14.5.4 Starting at an Inserted Node
14.5.5 Advancing to the Next Node
14.5.6 Backing Up to the Previous Node

14.6 Copying
14.7 Balance
14.8 Testing

15. AVL Trees with Parent Pointers

15.1 Data Types
15.2 Rotations
15.3 Operations
15.4 Insertion

15.4.1 Steps 1 and 2: Search and Insert
15.4.2 Step 3: Update Balance Factors
15.4.3 Step 4: Rebalance
15.4.4 Symmetric Case

15.5 Deletion

15.5.1 Step 2: Delete
15.5.2 Step 3: Update Balance Factors
15.5.3 Step 4: Rebalance
15.5.4 Symmetric Case

15.6 Traversal
15.7 Copying
15.8 Testing

16. Red-Black Trees with Parent Pointers

16.1 Data Types
16.2 Operations
16.3 Insertion

16.3.1 Step 2: Insert
16.3.2 Step 3: Rebalance
16.3.3 Symmetric Case

16.4 Deletion

16.4.1 Step 2: Delete
16.4.2 Step 3: Rebalance
16.4.3 Step 4: Finish Up
16.4.4 Symmetric Case

16.5 Testing

A. References
B. Supplementary Code

B.1 Option Parser
B.2 Command-Line Parser

C. Glossary
D. Answers to All the Exercises

Chapter 2
Chapter 3
Chapter 4
Chapter 5
Chapter 6
Chapter 7
Chapter 8
Chapter 9
Chapter 10
Chapter 11
Chapter 13
Chapter 14

E. Catalogue of Algorithms

Binary Search Tree Algorithms
AVL Tree Algorithms
Red-Black Tree Algorithms
Threaded Binary Search Tree Algorithms
Threaded AVL Tree Algorithms
Threaded Red-Black Tree Algorithms
Right-Threaded Binary Search Tree Algorithms
Right-Threaded AVL Tree Algorithms
Right-Threaded Red-Black Tree Algorithms
Binary Search Tree with Parent Pointers Algorithms
AVL Tree with Parent Pointers Algorithms
Red-Black Tree with Parent Pointers Algorithms

F. Index