Binary Search Tree
Introduction
A binary search tree (BST) is a type of data structure that holds an ordered set of values. It is a tree-like model of data, where each node has a maximum of two children, referred to as the left child and the right child.
Structure
The structure of a binary search tree is such that for every node, all elements in its left subtree are less than the node, and all elements in its right subtree are greater than the node. This property is also known as the binary-search-tree property.
Node
Each node in a binary search tree contains a key, a pointer to its left child, and a pointer to its right child. The key is a unique identifier for the node and is used to arrange the nodes in the tree.
Root
The root of a binary search tree is the node from where the tree originates. It is the only node in the tree that has no parent.
Subtree
A subtree is a portion of a binary search tree that is itself a binary search tree. Every node in a binary search tree has two subtrees: a left subtree and a right subtree.
Operations
Binary search trees support several operations, including search, insert, delete, minimum, maximum, predecessor, and successor.
Search
The search operation in a binary search tree begins at the root and traverses down the tree. It compares the key of the node with the key being searched. If the keys match, the search is successful. If the key being searched is less than the node's key, the search continues on the left subtree. If the key being searched is greater than the node's key, the search continues on the right subtree.
Insert
The insert operation in a binary search tree adds a new node to the tree. It starts at the root and traverses down the tree to find the appropriate location for the new node. The new node is always inserted as a leaf.
Delete
The delete operation in a binary search tree removes a node from the tree. There are three cases to consider when deleting a node: deleting a node with no children, deleting a node with one child, and deleting a node with two children.
Minimum and Maximum
The minimum operation in a binary search tree finds the node with the smallest key. It starts at the root and follows the left child pointers until it reaches a node with no left child. The maximum operation finds the node with the largest key by following the right child pointers.
Predecessor and Successor
The predecessor of a node in a binary search tree is the node with the largest key that is smaller than the node's key. The successor is the node with the smallest key that is larger than the node's key.
Properties
Binary search trees have several properties that make them useful as data structures.
Ordered
Binary search trees are ordered, or sorted, data structures. This means that they maintain their elements in a specific order, which allows for efficient search and sort operations.
Balanced
In a balanced binary search tree, the left and right subtrees of every node differ in height by at most one. Balanced binary search trees are optimal in terms of search time.
Complete
A complete binary search tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.
Variants
There are several variants of binary search trees, including the AVL tree, red-black tree, splay tree, and B-tree. These variants add additional properties or operations to the basic binary search tree to improve performance or functionality.
Applications
Binary search trees are used in many areas of computer science, including database systems, graphics, and network algorithms. They are particularly useful in applications that require frequent search and sort operations.