Binary Search Tree (BST)¶
A Binary Search Tree is a special type of binary tree where the value stored in node u is greater than or equal to all values in its left child's subtree, and greater than or equal to all values in its right child's subtree. A BST allows us to add, delete, or search for a value more efficiently. Searching, insertion, and deletion form the fundamental operations of a BST.
1class Node:
2 def __init__(self, key):
3 self.left = None # Bache chap
4 self.right = None # Bache rast
5 self.val = key # Meghdar
Search¶
The search operation for a value x proceeds as follows:
First, we examine the value at the root. If it is greater than x, we recursively repeat this step on the left subtree. If smaller, we proceed with the right subtree.
We continue this until either the target child subtree does not exist for further traversal, or the examined node's value equals x.
Insertion¶
The insertion operation for a value x proceeds as follows:
First, we examine the root's value. If it is greater than or equal to x, we recursively repeat this step on the left subtree. If smaller, we proceed with the right subtree.
We continue until the target child subtree does not exist, then add a new child node with value x in that position.
Deletion¶
After locating the target node using search, three cases may occur:
Leaf node (no children): Immediate deletion.
Single child: Replace the node with its child.
Two children: Two deletion methods exist. Let u be the node to delete.
Method 1 (Successor replacement): 1. Find node v - the smallest value in u's right subtree. 2. Replace u's value with v's value. 3. Delete v (which can only have 0 or 1 children, as v is the minimum).
Method 2 (Predecessor replacement): - Similar to Method 1, but using the largest value in u's left subtree.
This book is made by The Shaazzz contributors.
It is publicly available with cc-by-sa license.
Last updated at آوریل 19, 2025.
Rendered by Sphinx (4.3.2) and Minoo theme (Beta 0.9.7).
