Binary Search Tree

#Binary #Search #treedatastructure
#insert
#delete

A Binary Search Tree (BST) is a specialized data structure used in computer science to store sorted data, enabling efficient search, insertion, and deletion operations. BSTs follow a specific set of rules that keep the data sorted:

1. Node Structure:
• Each node in a BST has a value, a left child, and a right child.
• The left child node has a value less than the node’s value.
• The right child node has a value greater than the node’s value.
2. Basic Operations:
• Search: Start at the root and recursively navigate left if the target is smaller than the current node or right if it’s larger, until the target is found or a leaf is reached.
• Insertion: Follow the same path as search to locate the appropriate position, then insert the new node as a leaf.
• Deletion:
• If the node is a leaf, simply remove it.
• If it has one child, remove the node and link its child to the node’s parent.
• If it has two children, find the node’s in-order successor (smallest node in the right subtree) or in-order predecessor (largest in the left subtree) and replace the node’s value with this successor/predecessor, then delete the successor/predecessor node.
3. Efficiency:
• Time Complexity:
• Search, Insert, Delete: O(h), where h is the height of the tree.
• In a balanced BST, h is O(\log n), where n is the number of nodes.
• Space Complexity: Typically O(n) for storage.
4. Balanced vs. Unbalanced:
• If a BST is unbalanced (like a linked list where nodes only have right children), the search, insert, and delete operations degrade to O(n).
• Techniques like AVL trees or Red-Black trees help maintain balance, keeping operations efficient.
5. Applications:
• BSTs are used in applications that require dynamic data that can be updated quickly, such as databases, file systems, and caches.