Chapter 12

Binary Search Trees and AVL Trees

Chapter 9 discussed about trees and binary trees. Binary search trees and AVL trees which belong to the category of binary trees provide retrievals in an efficient manner. This chapter elaborates operations on binary search trees along with the definition. Listing the drawbacks of binary search trees, AVL trees which provide the remedy, are defined. Operations on AVL trees are explained. This chapter also includes applications and implementation of both the trees.

12.1 BINARY SEARCH TREES

A binary search tree (BST) is a binary tree. An empty binary tree is a binary search tree. A non-empty binary search tree should satisfy the following properties.

  1. All the elements must have a key and it must be ...

Get Data Structures and Algorithms Using C++ now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.