Explore the English language on a new scale using AI-powered English language navigator.

Binary search tree

First of all, binary search tree (BST) is a dynamic data structure, which means, that its size is only limited by amount of free memory in the operating system and number of elements may vary during the program run. Main advantage of binary search trees is rapid search, while addition is quite cheap. Let us see more formal definition of BST.

Binary search tree is a data structure, which meets the following requirements:

it is a binary tree;
each node contains a value;
a total order is defined on these values (every two values can be compared with each other);
left subtree of a node contains only values lesser, than the node's value;
right subtree of a node contains only values greater, than the node's value.

Notice, that definition above doesn't allow duplicates.

Example of a binary search tree

binary search tree (BST) example

What for binary search trees are used?

Binary search tree is used to construct map data structure. In practice, data can be often associated with some unique key. For instance, in the phone book such a key is a telephone number. Storing such a data in binary search tree allows to look up for the record by key faster, than if it was stored in unordered list. Also, BST can be utilized to construct set data structure, which allows to store an unordered collection of unique values and make operations with such collections.

Performance of a binary search tree depends of its height. In order to keep tree balanced and minimize its height, the idea of binary search trees was advanced in balanced search trees (AVL trees, Red-Black trees, Splay trees). Here we will discuss the basic ideas, laying in the foundation of binary search trees.