Weight Balanced Binary Search Tree

Keeping:

• $O(\log n)$ insert
• $O(\log n)$ search
• $O(\log n)$ delete Requires some certain Weight Balance Factor. Can be used to implement Hashmap

Balance

Tree is balanced if $\frac{1}{3}\le \frac{size(n.left)+1}{size(n.right)+1}\le 3$ $\frac{1}{3}\le \frac{weight(n.left)}{weight(n.right)}\le 3$

Operations

• WBT Rotation
• WBT Union