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.
- All the elements must have a key and it must be ...