Binary Search Tree Basics

Binary Search Tree (BST)

• Definition:

  • A binary search tree is a data structure that maintains sorted order, allowing for efficient searching, insertion, and deletion of elements.

• Properties:

  • Each node has at most two children.
  • The left child contains values less than the parent node.
  • The right child contains values greater than the parent node.
  • The left and right subtrees are also binary search trees.

• Basic Operations:

  1. Searching:

     • Start at the root.
     • Compare the target value with the current node’s value.
     • Move left if the target is smaller, right if larger.
     • Repeat until the target is found or a leaf node is reached.

  2. Insertion:

     • Start at the root and find the appropriate null position where the new value can be placed.
     • Follow the same logic as searching to find the correct location.

  3. Deletion:

     • Three cases to consider:
       • Leaf Node: Simply remove the node.
       • One Child: Remove the node and replace it with its child.
       • Two Children: Find the in-order predecessor (max of left subtree) or in-order successor (min of right subtree), replace the node with it, and delete the predecessor/successor.

• Traversal Methods:

  1. In-order (Left, Node, Right): Yields sorted order of elements.
  2. Pre-order (Node, Left, Right): Useful for copying the tree.
  3. Post-order (Left, Right, Node): Useful for deleting the tree.

• Time Complexity:

  • Average case for search, insertion, and deletion: O(log n).
  • Worst case (unbalanced tree): O(n).

• Balancing:

  • To maintain O(log n) performance, consider self-balancing BSTs like AVL trees or Red-Black trees.

• Applications:

  • Database indexing, memory management, and maintaining a dynamic list of sorted data.

Definition

• A binary search tree (BST) is a data structure that maintains sorted order for efficient searching, insertion, and deletion of elements.

Properties

• Nodes in a BST can have up to two children.
• The left child contains values less than its parent node.
• The right child contains values greater than its parent node.
• Both left and right subtrees must also be binary search trees.

Basic Operations

• Searching:

  • Begin at the root and compare the target value with the current node.
  • Move left if the target is smaller, or right if larger.
  • Continue until the target is found or a leaf node is reached.

• Insertion:

  • Initiate at the root and locate the correct null position for the new value.
  • Employ the same logic as searching to determine where to insert.

• Deletion:

  • Leaf Node: Remove the node directly.
  • One Child: Remove the node and connect its child directly to its parent.
  • Two Children: Replace the node with its in-order predecessor (maximum of the left subtree) or in-order successor (minimum of the right subtree), then delete the predecessor/successor.

Traversal Methods

• In-order (Left, Node, Right): Produces sorted order of elements.
• Pre-order (Node, Left, Right): Useful for creating a copy of the tree.
• Post-order (Left, Right, Node): Effective for deleting the entire tree.

Time Complexity

• Average time complexity for searching, insertion, and deletion is O(log n).
• In the worst-case scenario with an unbalanced tree, time complexity escalates to O(n).

Balancing

• To ensure O(log n) performance, self-balancing BSTs like AVL trees or Red-Black trees are recommended.

Applications

• Commonly used in database indexing.
• Plays a role in memory management.
• Helps maintain a dynamic list of sorted data.