Explanation:
- A **Scapegoat Tree** is a type of self-balancing binary search tree that uses an amortized **O(log n)** time complexity for insertion and deletion.
-
- Unlike AVL and Red-Black Trees, it does not maintain a strict balance at every node but ensures that the tree does not become unbalanced by periodically rebuilding subtrees.
-
-
Steps:
- Insertion: Insert elements as in a regular binary search tree. When a subtree becomes too unbalanced, a “scapegoat” node is found and the subtree is rebuilt to restore balance.
- Rebuilding: The tree periodically rebuilds a subtree when an insertion violates the balance property.
-
Time Complexity:
- Insertion: O(log n) amortized
- Rebuilding: O(n) for the worst case (rebuilding the tree)