Study Notes on Binary Search Trees

A binary search tree (BST) is a data structure that enables fast data retrieval and efficient data storage.

BSTs allow quick searches through stored data as opposed to linked lists where locating specific elements requires traversing the entire list.
The efficiency of BSTs comes from their structure, which halves the search space at each step.

Properties of a BST:
  - Supports logarithmic search times under optimal conditions (balanced trees).
  - Organized structure with a root, subtrees, and relationship rules:
    - Tree grows from a root node downwards.
    - Each node has up to two children (left and right).
  - Nodes maintain order: values in the left subtree are lesser than the parent node, while values in the right subtree are greater.
Visualizing Trees:
- A BST can be visualized similarly to a genealogy tree with parents and children nodes.

Searching through a BST involves:
- Starting at the root, checking the value, determining whether to go left or right based on the value comparison, and halving the search area at each decision point.
- The search continues recursively until the value is found or a null (empty) node is reached.
Example Search Algorithms:
  - To find the value 100:
    - Start at root: if greater, move to right subtree. If not found, check the next node recursively.
  - For found 10, the result shows straightforward traversal.

Insertion Rule: The newly inserted value must maintain the properties of the BST.
  - Begin at the root:
    - If the current node is empty, insert the new node.
    - If the value is less than the current node, go left; greater, go right.
Example of Insertion:
- Insert 10, then 9 (go left), followed by 12 (go right).
Insertions must respect the node hierarchy to maintain efficiency.

Deletion procedures in BSTs are more complex than linked lists, involving several cases:
  - Case 1: If the node is a leaf (no children), simply remove it.
  - Case 2: If a node has one child, promote the child to replace the node.
  - Case 3: If the node has two children, replace it with the left-most node from its right subtree.
Example Deletion Steps:
  - Remove 5: it is a leaf.
  - Remove 15: promote 13 to replace 15 because 13 is the next node.
  - Remove 12: replace with 13 and manage children accordingly.

Nodes can be described with relational terms:
  - Root: The top node with no parent.
  - Child: Nodes directly below another node.
  - Leaf: Nodes without any children.
  - Ancestors/Descendants: Ancestors are nodes above, and descendants are those below a certain node in the tree.

Primary methods for traversing binary trees include:
  1. In-Order Traversal: Left subtree -> Node -> Right subtree; produces sorted output.
  2. Pre-Order Traversal: Node -> Left subtree -> Right subtree.
  3. Post-Order Traversal: Left subtree -> Right subtree -> Node; useful for deletions.
Benefits of Traversals:
  - In-order traversal guarantees sorted values in increasing order.
  - Pre-order can create exact copies of trees.
  - Post-order efficiently deletes by targeting leaf nodes first.

The recursive traversal is fluid, making it easier to apply operations as you visit nodes.
The traversal orders can be switched by adjusting the sequence of calls, allowing flexibility in processing the nodes.

In BSTs, search, insertion, and deletion operations render average time complexities typically around O(log n) under balanced conditions.
The worst-case scenario (linked list behavior) occurs when the tree becomes unbalanced.
Strategies like balancing trees (e.g., AVL trees, Red-Black trees) are essential for maintaining logarithmic performance.

BSTs can be implemented using programming languages such as Java, focusing on recursive functions to handle search, insertion, and deletion.
The assignment will involve building a card class linked to BST structures.

Code structure should be generic to allow for easy modifications later (e.g., adding different card types).
Function names are critical for automated testing; use clear and consistent naming conventions.
Building a logged card game, users should be mindful of the logic and operations expected in their implementations.

Binary Search Trees offer a vital organization of data that optimizes searching, inserting, and deleting operations.
Understanding tree properties will aid in efficient usage and implementation in programming tasks.

Encourage participants to ask questions or seek clarification on topics covered, ensuring comprehension of key concepts.