Handbook of Data Structures and Applications, 2nd Edition

11

Balanced Binary Search Trees*

Arne Andersson

Uppsala University

Rolf Fagerberg

University of Southern Denmark

Kim S. Larsen

University of Southern Denmark

11.1Introduction

11.2Basic Definitions

Trees•Binary Trees as Dictionaries•Implementation of Binary Search Trees

11.3Generic Discussion of Balancing

Balance Definitions•Rebalancing Algorithms•Complexity Results

11.4Classic Balancing Schemes

AVL-Trees•Weight-Balanced Trees•Balanced Binary Trees Based on Multi-Way Trees

11.5Rebalancing a Tree to Perfect Balance

11.6Schemes with no Balance Information

Implicit Representation of Balance Information•General Balanced Trees•Application to Multi-Dimensional Search Trees

11.7Low Height Schemes

11.8Relaxed Balance

Red-Black Trees•AVL-Trees•Multi-Way ...