Rebalancing Binary Search Trees: Insights from FUN 2024 Conference
Delve into the world of binary search trees with a focus on rebalancing techniques as discussed at the FUN 2024 Conference in Sardinia, Italy. Explore key concepts, challenges, and proposed solutions for enhancing tree performance.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Bottom-up Rebalancing Binary Search Trees by Flipping a Coin Gerth St lting Brodal Aarhus University 12th International Conference on Fun with Algorithms (FUN 2024), Island of La Maddalena, Sardinia, Italy, June 4-8, 2024
Review The paper considers an important problem The paper fails to solve the problem
Unbalanced binary search trees Insertions 4 1) Locate insertion point (empty leaf) 3 8 2) Create new leaf node 9 1 5 7
Unbalanced binary search trees Inserting 1 2 3 4 5 6 Inserting 3 5 2 4 1 6 random permutation gives expected logarithmic depth [Hilbard 1962] increasing sequence gives linear depth
Balanced binary search trees Structural invariants implying logarithmic depth Rebalance using rotations 60s 70s 80s 90s Treap AVL-tree Red-black tree Splay tree v 4 3 4 0.110 2 7 6 1 7 6 9 5 7 0.101 0.011 Always rotate accessed node to the root Elements random priority, stored using heap order No two adjacent red & root-to-leaf paths same #black |h(v.left) h(v.right)| 1
Balanced binary search tree insertions : rebalancing cost Reference [AVL62] [GS78] [B79] [ST85] [A89,GR93] Scapegoat [SA96] [MR98] [S09] Name AVL-trees Red-black trees Encoded 2-3 trees Splay trees Time OA(1) OA(1) O(lg n) OA(lg n) O(lg n) OE(1) OE(lg n) OE(lg2n) OE(1) Rotations Random bits Space pr node O(1) 0 O(1) 0 O(lg n) 0 OA(lg n) 0 O(lg n) 0 OE(1) OE(1) OE(1) OE(lg2n) OE(1) OE(lg3n) O(1) OE(1) 2 1 0 0 global O(lg n) OE(1) O(lg n) 0 0 Treaps Randomized BST Seidel Open problem random BST
Question asked in this paper Does there exists a randomized rebalancing scheme satisfying 1. 2. 3. 4. 5. 6. 7. No balance information stored Worst-case O(1) rotations Most rotations near the insertion Local information only Expected O(1) time O(1) random bits per insertion Nodes expected depth O(lg n)
Algorithm RebalanceZig v 7 Fact 1 REBALANCEZIGtakes expected O(1) time and performs 1 rotation Theorem 1 REBALANCEZIGon increasing sequence each node expected depth O(lg n), for 0 < p < 1 (p = Pr[tail])
Algorithm RebalanceZigextreme probabilities v 7 Pr[tail] = 1 never performs rotation i.e. unbalanced binary search tree Pr[tail] = 0 always rotates up new leaf i.e. tree is always a path
Rotate onto path No rebalancing Theorem 1 Increasing is (lg n) for 0 < p < 1 Fair coin
Rotate onto path No rebalancing Theorem 2 Convering is (n) Theorem 3 Pairs is (n) for p Conjecture Pairs is ( n) for p = Fair coin
Why ReblanceZigis bad on convering Proof of Theorem 2 For each pair the depth of the insertion point increases by 1 with probability p(1-p) : If inserting urotates a (strict) ancestor of uup, and inserting v rotates v up, then depth of insertion point * increases by inserting the pair
Why ReblanceZigis bad on pairs Proof of Theorem 3 p < , odd numbers tend to be rotated on rightmost path, right path expected (n) nodes p > , rightmost path tends to contain O(1) nodes, left path expected (n) nodes
Find a randomized algorithm that handles coverging sequences
No rebalancing Theorem 4 Increasing is (lg n) for 0 < p < 1 Theorem 5 Converging is (lg n) for 0.62 < p < 1
Theorem 6 Pairs is (n) for 0 p 1
Bottom-up Rebalancing Binary Search Trees by Flipping a Coin
Bottom-up Rebalancing BalancedBinary Search Trees by Flipping a Coin ?
