Introducing
Your new presentation assistant.
Refine, enhance, and tailor your content, source relevant images, and edit visuals quicker than ever before.
Trending searches
Scapegoat Trees
6
Scapegoat Trees
Remove
Worst-case: O(n)
Average: O(logn) amortized
- Remove as in standard BST.
- Keep track of LastNodeCount and NodeCount with class variables.
- LastNodeCount is the node count of the tree when the last rebuilding operation occurred.
- If NodeCount <= a * LastNodeCount, rebuild must occur.
- We rebuild the entire tree from the root.
Finding Scapegoat
- The scapegoat is any ancestor of the inserted node that is not a-weight-balanced.
- We choose the scapegoat closest to the inserted node.
- Recurse from inserted node to root.
- Check a-balance at each node.
- Return first node unbalanced node
Rebuilding Tree
If begin != end
{
mid = (begin + end)/2
cRoot = array[mid]
rebuild(cRoot->left , begin, mid)
rebuild(cRoot->right, mid + 1, end)
}
- No rotations like AVL tree
- Traverse tree in-order, storing nodes in array.
- Root for balanced tree will be at median (begin + end)/2.
- Recursively build tree from array.
Advantages/Disadvantages
Insert
Worst-case: O(n)
Average: O(logn) amortized
- Insert node into tree as with standard BST.
- Keep track of depth of node to be inserted.
- Check weight balance
- a-weight-balance implies a-height-balance
- tree height <= log1/a(# of nodes in tree)
- If depth violates height balance, find scapegoat and rebuild tree rooted at scapegoat.
Advantages:
- Low node overhead
- Fast runtime:
- O(logn) lookup
- O(logn) amortized insert/remove
- Flexible: you choose alpha.
- Simple implementation
Disadvantages:
- Overhead for rebuild can be high
What is a scapegoat tree?
- Self-balancing binary search tree
- alpha-weight-balanced
- balance depends on ratio called alpha, a.
- 0.5 <= a < 1
- Tree is balanced when:
# nodes in child subtree <= a * # nodes in parent tree
- Once balance is exceeded, we find a scapegoat.
- Subtree where balance is violated.
- Rebuild tree rooted at scapegoat.