BINARY TREES PT2

Node Predecessor and Successor

• Predecessor: In a binary search tree, the predecessor of a node is found by going to the left subtree and then continuing to the rightmost node.

  • Example: For node 70, there is no predecessor since it has no left subtree.

• Successor: The successor of a node is found by going to the right subtree and then continuing to the leftmost node.

  • Example: To find the successor of node 50, go to the right subtree, resulting in 70 being the successor. For node 40, the successor is 45 since there is no left subtree to explore further.

Deletion in a Binary Search Tree

Deletion Process

• Different methods to delete a node can vary; this class focuses on deletion by copying.

• Scenarios for deletion depend on the number of child nodes:

Scenario 1: Leaf Node (No Children)

• A leaf node can be directly removed since it has no dependencies.

• This operation is straightforward: cut off the node from the tree, similar to deleting the tail in a linked list.

Scenario 2: Node with One Child

• If a node has only one child, promote that child to take the place of the deleted node.

• Example: To delete node 40 with the right child 45, 45 becomes the new right child of 30 (the grandparent).

Scenario 3: Node with Two Children

• Involves deletion by copying: replace the value of the node to be deleted with the value of its successor, then delete the original successor node.

• The process can result in further scenarios:

  • If the successor node has no children, it becomes a scenario 1 deletion.

  • If it has one child, it fits scenario 2.

• Example: Deleting node 30:

  • Locate the successor (e.g., node 35), copy its value to 30, and then delete the original node 35.

Searching and Inserting Operations

• Both search and insertion operations start from the root and traverse the tree based on the binary search property.

• As you traverse, maintain a trailing pointer to remember the parent node for future pointer updates.

• Insertions involve dynamically creating new nodes and deciding their position based on the values compared.

Time Complexity

• Worst Case: O(n) when the tree degenerates into a linked list (e.g., all nodes have only a right child).

• Average Case: O(log n) when the tree maintains a balanced structure.

  • This occurs because nodes are likely distributed between left and right children evenly, minimizing tree height.

Conclusion and Final Notes

• The insertion and deletion operations preserve binary search tree properties and can significantly impact tree structure.

• Trees that deviate too far from balance may lose their efficiency, resembling linear structures instead of hierarchical ones.

• Emphasis on understanding the hierarchical nature and constraints of binary search trees is crucial for mastering these operations.