A Binary Search Tree (BST) is a data structure in computer science used to organize and store data in a sorted order. It follows the properties of a binary tree, where for each node, the left subtree holds values smaller than the node, and the right subtree holds larger values. Each subtree must also be a binary search tree and there must not be any dubplicate nodes. This enables efficient searching, insertion, and deletion operations.
A Binary Search Tree (BST) supports various operations such as search, insert, delete, etc.. To minimize the height of the tree, self-balancing BSTs, such as AVL and Red-Black Trees, are used in practice. These self-balancing trees maintain a height of O(log n), which makes all the operations O(log n) as well. Additionally, BSTs allow for a sorted order traversal of the data in O(n) time. Self-balancing BSTs are useful for maintainging a sorted stream of data, such as tracking prices in real-time, and can efficiently handle queries like finding items below or above a certain cost. They also implement doubly-ended priority queses. BSTs are ideal for problems like counting smaller elements to the right and can be used to sort large datasets with efficient insertions and deletions in O(log n). Variants like B-Trees and B+ Trees are used in database indexing, and data structures like TreeMap and TreeSet in Java or set and map in C++ are based on self-balancing BSTs.
A new key is inserted at the leaf while maintaining the BST property. We start at the root and search until we reach a leaf node, then add the new node as its child. The steps for inserting a node into a BST are as follows: 1. Initialize the current node 2. Compare the key and current node 3. Move left if the key is less than the current node or right if the key is greater than the current node 4. Repeat 2 and 3 until the leaf node is reached 5. Add the key to the leaf node as the right or left child depending on the comparison of the values
To search for a node in a BST, treat it like a sorted array. You can then apply the Binary Search Algorithm to efficiently find the value in the BST. To search for a value X in a BST, start at the root and follow these steps: 1. Compare X with the root's value - If equal, X is found and return True - If X is smaller, move to the left subtree - If X is larger, move to the right subtree 2. Repeat the process until the X value is found or until no further traversal is possible 3. If X is found, return True, if no further traversal is possible and True has not been returned, X is not found and return False
Deleting a node in a BST can be broken down into three scenarios:
When deleting a leaf node, the rest of the tree is not impacted so node can simply be removed.
The desired node and its child should be rotated so that the desired node is now a leaf node. Now case 1 is applicable.
The desired node should be replaced with its in order successor so that it is a leaf node. Now case 1 is applicable.
There are three types of traversal; inorder, preorder, and postorder.
For the inorder traversal first traverse the left subtree, then visit the root, and then the right subtree. This gives the values in sorted order.
For the preorder traversal first visit the root, then traverse the left subtree, and then the right subtree.
For the postorder traversal first traverse the left subtree, then the right subtree, and then visit the root.