Page 65 - Data Structures Interactive Book

7.3.1 Definition and Operations

The BST structure ensures that searching for a value can be done by repeatedly

comparing the target with the current node and moving left or right accordingly. This reduces

the search space by half at each step, like binary search in arrays. Operations supported by

BSTs include insertion, deletion, searching, and traversal. Each operation leverages the

ordering property to maintain efficiency.

7.3.2 Insertion and Deletion in BST

Insertion in a BST involves placing a new node in the correct position based on its

value. Starting from the root, the algorithm compares the new value with the current node

and moves left or right until it finds an empty spot. Deletion is more complex, with three
cases:

• Leaf node deletion: Simply remove the node.

• Node with one child: Replace the node with its child.
• Node with two children: Replace the node with its inorder successor (the smallest value

in the right subtree) or inorder predecessor (the largest value in the left subtree).

These rules ensure that the BST property is preserved after deletion.

7.3.3 Searching in BST

Searching in a BST is efficient because the tree structure guides the search. Starting

from the root, if the target value is smaller, the search moves to the left subtree; if larger, it

moves to the right subtree. This process continues until the value is found or the subtree is

empty. In balanced BSTs, this operation takes (log⁡ )time, but in skewed trees, it can

degrade to ( ).

7.4 Advanced Trees

While BSTs are powerful, they can become inefficient if not balanced. Advanced tree
structures were developed to overcome these limitations and provide guaranteed

performance.

65