I found this answer on Stack Overflow. The answer implies that the number of rotations, in worst-case, are constant for the Red-Black tree 'Delete' function and the number of Color Flips grows proportional to Log(N). I have also read the script attached to the answer. However, I cannot find any proof for this statement. Why is this statement true or not? Can it be proven by a practical example?
Why are the worst-case number of Rotations constant for the Red Black tree Delete function, but the Color Flips are not?
54 Views Asked by Niek Beijloos At
1
There are 1 best solutions below
Related Questions in DATA-STRUCTURES
- Why is the runtime for this O(n)?
- Purpose of last 2 while loops in the merge algorithm of merge sort sorting technique
- What is the problem in my "sumAtBis" code?
- Asking code suggestions about data structure and algorithm
- What would be the most efficient way to store multiple sets of fixed arrays (std::vector)?
- About Suffix Trees features
- Getting wrong answer in Binary Search solution
- Are there techniques to mathematically compute the amount of searching in greedy graph searching?
- AVL tree Nth largest operation - How to have all my tests pass? JAVA
- Why does the map size change?
- Complexity in Union of disjointed sets with lists
- Hash collisions in Golang map resolving
- C++ ordered map optimized with index access
- How to sort this list of strings along with the strings and output the result as expected?
- Why deleting an element in a linkedlist costs O(1)
Related Questions in TREE
- Python - how to make tree without any library
- how to get the full path of antd tree
- Python Quadtree won't insert values
- Top View Of Binary Tree Depth First Search Using TreeMap
- Select/filter tree structure in postgres
- PySimpleGUI tree doesn't Insert data into tree
- Is it possible to create a node-link diagram with ggplot?
- Represent a full, but not complete, binary tree with an array structure
- Redirecting stdout with execvp
- Prevent selected node to be unselect primevue Tree component
- Binary Search Tree (BST) - array representations
- Debugging AVL Tree Deletion: Unbalanced Node Not on Deletion Path
- How to shorten line length in react-d3-tree
- installed dm-tree vs imported tree
- Why the height of segment tree is O(logn)
Related Questions in BINARY-SEARCH-TREE
- C++: Program for Deleting a node and return its right child:
- I can't get the specific node of BST using recursion . i.e. every stack it erase
- Why is my traversing in BST not showing the results like the sample output?
- Binary Trees Changing Node vs Changing Value of Nodes
- BST Inorder to Preorder and Postorder
- Binary Search Tree - parent node method incorrect output
- Binary Search Tree - node count method with an incorrect output
- Binary Search Tree (BST) - array representations
- Return more than one int value
- Lowest Common Ancestor Of A Binary Search Tree failing at a long input case
- Removing final node in a BST causing fault
- i am performing deletion operation in BST as i am deleting node recursively and not
- Why output of my BST-validating function is false?
- What is the most efficient way to implement 2 data structures for iteration of different values
- Recurrence Relation for Full Binary Tree
Related Questions in RED-BLACK-TREE
- What is the maximum degree of imbalance in a red black tree ? Is it height/2?
- Why does Java HashMap treeify() compare hash values of nodes in the same bucket?
- Why are the worst-case number of Rotations constant for the Red Black tree Delete function, but the Color Flips are not?
- (*p)->left->prev means *p
- When to choose a Red-Black tree over an AVL tree?
- How do I fix my Red Black Tree from rotating unnecessarily?
- How to prove the time complexity of query in interval tree
- Radix Tree vs. Red-black Tree
- Pointer of a Pointer in C: How to use them in RB Trees?
- How does gcc std::set use stl_tree.h to store node keys?
- Doubts about the decrement function of the RB-Tree iterator
- Creating red and black tree from two BSTs
- The implementation of red-black trees gives problems inserting a duplicate number
- Delete large number of nodes from RedBlack Tree Causes Infinite Loop
- Red Black Tree Node Insertion Overwrites Previously Added Node
Trending Questions
- UIImageView Frame Doesn't Reflect Constraints
- Is it possible to use adb commands to click on a view by finding its ID?
- How to create a new web character symbol recognizable by html/javascript?
- Why isn't my CSS3 animation smooth in Google Chrome (but very smooth on other browsers)?
- Heap Gives Page Fault
- Connect ffmpeg to Visual Studio 2008
- Both Object- and ValueAnimator jumps when Duration is set above API LvL 24
- How to avoid default initialization of objects in std::vector?
- second argument of the command line arguments in a format other than char** argv or char* argv[]
- How to improve efficiency of algorithm which generates next lexicographic permutation?
- Navigating to the another actvity app getting crash in android
- How to read the particular message format in android and store in sqlite database?
- Resetting inventory status after order is cancelled
- Efficiently compute powers of X in SSE/AVX
- Insert into an external database using ajax and php : POST 500 (Internal Server Error)
Popular Questions
- How do I undo the most recent local commits in Git?
- How can I remove a specific item from an array in JavaScript?
- How do I delete a Git branch locally and remotely?
- Find all files containing a specific text (string) on Linux?
- How do I revert a Git repository to a previous commit?
- How do I create an HTML button that acts like a link?
- How do I check out a remote Git branch?
- How do I force "git pull" to overwrite local files?
- How do I list all files of a directory?
- How to check whether a string contains a substring in JavaScript?
- How do I redirect to another webpage?
- How can I iterate over rows in a Pandas DataFrame?
- How do I convert a String to an int in Java?
- Does Python have a string 'contains' substring method?
- How do I check if a string contains a specific word?
An example could never serve as proof for the limited number of rotations. If we were to provide an example where a deletion resulted in three rotations, what woud it prove? Certainly not that this is the maximum number of rotations for a single deletion. For that you need to look at all possibilities that influence the algorithm and the number of rotations, and draw conclusions from that.
I will refer to the algorithm described on Wikipedia. There distinction is made between simple cases and other cases. The cases where rotations may be involved, start (or are translated to, with a value-swap) with the deletion of a black leaf (i.e. with two NIL children).
The Wikipedia article then categorises this case into six subcategories, D1, D2, D3, D4, D5, and D6. It provides this summary table:
...where we have [P]arent, [S]ibling, [C]lose nephew and [D]istant nephew of the current black [N]ode.
Rotations
States D1 and D4 are end-states: no more rotations occur.
State D2 is a transitional state and may translate to any of the other states, or even a "simple" case (hence the question mark in the "Next" column of the above table)
State D3 involves a rotation. It then may transition to either D4, D5 or D6
State D5 involves a rotation and transitions to state D6
State D6 involves a rotation, and ends the process.
So a rotation only occurs in states D3, D5 and D6. From the above it is then clear that the deletion process can at the most have 3 rotations. This happens when from state D3 we get to state D5 and then (always) conclude with state D6.
Coloring
The state D2 involves coloring, and may lead to state D2 at the parent level. So this could continue all the way to the root.