rag/knowledge_base/binary_search_tree.txt

TOPIC: Binary Search Tree

DEFINITION: A Binary Search Tree (BST) is a data structure in which each node has at most two children (i.e., left child and right child) and each node represents a value. This structure allows for efficient storage and retrieval of data by ensuring that all values to the left of a node are less than the node's value, and all values to the right are greater. This property enables fast searching, inserting, and deleting of nodes.

TIME_COMPLEXITY: The time complexity of a Binary Search Tree is O(log n) for best and average cases, and O(n) for the worst case, which occurs when the tree becomes a skewed tree (essentially a linked list).

SPACE_COMPLEXITY: The space complexity of a Binary Search Tree is O(n), where n is the number of nodes in the tree, as each node requires a constant amount of space to store its value and references to its children.

USE_WHEN: Use a Binary Search Tree when you need to store and retrieve large amounts of data efficiently, and the data needs to be ordered or searchable. This is particularly useful in scenarios where data is constantly being inserted or deleted.

AVOID_WHEN: Avoid using a Binary Search Tree when the data is mostly static or when the tree may become heavily unbalanced, as this can lead to poor performance; in such cases, a self-balancing binary search tree like an AVL tree or a Red-Black tree may be more suitable.

EXAMPLE:
Suppose we have a BST with the following nodes:
      5
     / \
    3   7
   / \   \
  2   4   8
We want to insert the value 6. 
  First, we start at the root node (5) and compare it to the value we want to insert (6). 
  Since 6 is greater than 5, we move to the right child (7). 
  Then, we compare 6 to 7; since 6 is less than 7, we move to the left child (which doesn't exist), 
  so we create a new node with the value 6 as the left child of 7.
  The resulting tree is:
      5
     / \
    3   7
   / \ / \
  2   4 6  8 
  The insertion is successful 

REAL_WORLD_ANALOGY: A Binary Search Tree can be thought of as a phonebook where each entry is a person's name, and the names are arranged alphabetically; when you look up a name, you can quickly find it by comparing it to the names on either side of the current page.

SOURCE_NOTE: Concepts referenced from general knowledge of data structures and algorithms.