More Binary Trees

Inserting Elements in a Binary Search Tree (BST)

• When inserting n elements into an originally empty binary search tree (BST), the running time complexity can vary based on the order of insertion.

Worst Case Scenario

• Inserting elements in a sorted order (e.g., 1, 2, 3, ... n) leads to a worst-case time complexity of O(n²).

  • Reasoning: Each insertion requires traversing through all previously inserted nodes in the worst-case configuration (linear).

  • For the first insertion, there are 0 nodes passed.

  • For the second insertion, 1 node is passed, and for the third insertion, 2 nodes are passed, leading to a cumulative total described by the arithmetic series:

    • Total nodes passed: 0 + 1 + 2 + 3 + ... + (n-1)

    • The sum can be represented as (n-1)(n)/2, which simplifies to O(n²) when analyzing big O notation, focusing on the dominant term.

Average Case Scenario

• The average case time complexity when inserting n elements is O(n log n).

  • Average case for a BST depends on the height of the tree, which is logarithmic due to a balanced insertion.

  • The running time is given by summing the logarithm of each possible insertion:

    • Total nodes: Log(1) + Log(2) + Log(3) + ... + Log(n)

  • It can be approximated as n log n when evaluated through Stirling’s approximation.

Deletion Operations in a Binary Search Tree

• Deleting nodes from a BST can also vary in complexity based on the tree's structure.

Deletion Scenarios

1. Case 1 (No children): Simply remove the node, informing its parent that it is gone.

2. Case 2 (One child): Bypass the node being deleted, attaching its child directly to its parent.

3. Case 3 (Two children): Find the successor (or predecessor) node, copy its value to the node being deleted, and delete the successor.

• During deletion, operations also require navigating and potentially modifying the structure of the tree, much like insertions.

Balancing the Binary Search Tree

• Symptoms of an unbalanced tree can manifest either during insertion or deletion operations, leading to inefficient configurations resembling a line rather than a balanced structure.

• It’s important to maintain a balanced tree to minimize the height, which directly affects the efficiency of BST operations, ideally maintaining O(log n) time complexities.

Self-Balancing Trees

• Self-balancing trees ensure that every time a node is inserted or deleted, the tree checks its balance and restructures if necessary to prevent long lines.

• AVL trees (named after their inventors, Adelson-Velsky and Landis) are a type of self-balancing BST. They maintain balance by ensuring the heights of the left and right subtrees for any node differ by at most one.

Balance Factors

• The balance factor of a node is calculated as follows:

  • Balance Factor = Height of Left Subtree - Height of Right Subtree

  • Value must be -1, 0, or 1 for the tree to be classified as an AVL tree.

Height of Nodes

• The height of any node in a BST is calculated based on its deepest leaf, impacting efforts to assess balance efficiently.

Why Balance Matters

• A balanced BST leads to quicker search, insert, and delete operations compared to an unbalanced one.

• For nodes n, using the full height allows for better spatial memory utilization, avoiding linear time complexities.