Prove that a red-black tree remains valid after turning a set S of red nodes blackNumber of Nodes with Specific Black-Height in Red-Red-Black treesCan every valid red-black tree exist?Inserting into Augmented Red Black TreeChildren in a red / black tree?Red Black Tree contains too many black nodes and too few red nodesCan a red node have just 1 black child in a red-black tree?Null child in Red-black tree JavaRed-Black Tree ProofRed Black Trees: Kahrs versionVerify a red black tree
As an international instructor, should I openly talk about my accent?
A Note on N!
Two field separators (colon and space) in awk
Like totally amazing interchangeable sister outfits II: The Revenge
Extension of 2-adic valuation to the real numbers
Philosophical question on logistic regression: why isn't the optimal threshold value trained?
Mistake in years of experience in resume?
On The Origin of Dissonant Chords
Why must Chinese maps be obfuscated?
Does tea made with boiling water cool faster than tea made with boiled (but still hot) water?
What are the steps to solving this definite integral?
Aligning equation numbers vertically
Pulling the rope with one hand is as heavy as with two hands?
Can we say “you can pay when the order gets ready”?
Implications of cigar-shaped bodies having rings?
What's the polite way to say "I need to urinate"?
Which big number is bigger?
How to not starve gigantic beasts
What does ゆーか mean?
What happened to Captain America in Endgame?
Why does nature favour the Laplacian?
Pre-plastic human skin alternative
Elements other than carbon that can form many different compounds by bonding to themselves?
Function pointer with named arguments?
Prove that a red-black tree remains valid after turning a set S of red nodes black
Number of Nodes with Specific Black-Height in Red-Red-Black treesCan every valid red-black tree exist?Inserting into Augmented Red Black TreeChildren in a red / black tree?Red Black Tree contains too many black nodes and too few red nodesCan a red node have just 1 black child in a red-black tree?Null child in Red-black tree JavaRed-Black Tree ProofRed Black Trees: Kahrs versionVerify a red black tree
.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty height:90px;width:728px;box-sizing:border-box;
I'm currently cracking my brain over the following question:
Prove that, in a red-black tree T, if every path from the root to a leaf contains
at least one red node, then we can select a set of red nodes in T to color black such that T remains a valid red-black tree and the black-height increases by one.
Anyone has any tips on how to tackle this, I'm lost even starting
data-structures binary-tree red-black-tree
asked Mar 22 at 17:13
Tim DTim D
31
add a comment |
I'm currently cracking my brain over the following question:
Prove that, in a red-black tree T, if every path from the root to a leaf contains
at least one red node, then we can select a set of red nodes in T to color black such that T remains a valid red-black tree and the black-height increases by one.
Anyone has any tips on how to tackle this, I'm lost even starting
data-structures binary-tree red-black-tree
asked Mar 22 at 17:13
Tim DTim D
31
add a comment |
I'm currently cracking my brain over the following question:
Prove that, in a red-black tree T, if every path from the root to a leaf contains
at least one red node, then we can select a set of red nodes in T to color black such that T remains a valid red-black tree and the black-height increases by one.
Anyone has any tips on how to tackle this, I'm lost even starting
data-structures binary-tree red-black-tree
asked Mar 22 at 17:13
Tim DTim D
31
I'm currently cracking my brain over the following question:
Prove that, in a red-black tree T, if every path from the root to a leaf contains
at least one red node, then we can select a set of red nodes in T to color black such that T remains a valid red-black tree and the black-height increases by one.
Anyone has any tips on how to tackle this, I'm lost even starting
data-structures binary-tree red-black-tree
data-structures binary-tree red-black-tree
asked Mar 22 at 17:13
Tim DTim D
31
asked Mar 22 at 17:13
Tim DTim D
31
asked Mar 22 at 17:13
Tim DTim D
31
asked Mar 22 at 17:13
Tim DTim D
31
asked Mar 22 at 17:13
Tim DTim D
31
31
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
The easy way to think of it is by pushing red nodes up a tree and then turning the root black again.
Imagine a tree like the following:
B
R B
B B R B
B B B B B B R R
If there is a red node on every path then there will be at least one black node with two red children. If you push the red node up the tree at every position where this occurs, starting from the bottom eventually you will push the red node to the tree root at which point you can flip the color and the tree height has grown by one.
Also, if you ever reach a configuration where an entire level is red all the nodes at that level can be flipped without altering the tree properties and again the height has grown by one.
It is somewhat trickier if some paths have more than one red node, in that case you will want to work from the top-most red node in that path and push a red node from the other branch to match it.
answered Mar 23 at 3:32
SoronelHaetirSoronelHaetir
7,2711514
Thank you, "If there is a red node on every path then there will be at least one black node with two red children. "was an eyeopener
– Tim D
Mar 23 at 15:20
add a comment |
Your Answer
StackExchange.ifUsing("editor", function ()
StackExchange.using("externalEditor", function ()
StackExchange.using("snippets", function ()
StackExchange.snippets.init();
);
);
, "code-snippets");
StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "1"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);
else
createEditor();
);
function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);
);
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f55304714%2fprove-that-a-red-black-tree-remains-valid-after-turning-a-set-s-of-red-nodes-bla%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
The easy way to think of it is by pushing red nodes up a tree and then turning the root black again.
Imagine a tree like the following:
B
R B
B B R B
B B B B B B R R
If there is a red node on every path then there will be at least one black node with two red children. If you push the red node up the tree at every position where this occurs, starting from the bottom eventually you will push the red node to the tree root at which point you can flip the color and the tree height has grown by one.
Also, if you ever reach a configuration where an entire level is red all the nodes at that level can be flipped without altering the tree properties and again the height has grown by one.
It is somewhat trickier if some paths have more than one red node, in that case you will want to work from the top-most red node in that path and push a red node from the other branch to match it.
answered Mar 23 at 3:32
SoronelHaetirSoronelHaetir
7,2711514
Thank you, "If there is a red node on every path then there will be at least one black node with two red children. "was an eyeopener
– Tim D
Mar 23 at 15:20
add a comment |
The easy way to think of it is by pushing red nodes up a tree and then turning the root black again.
Imagine a tree like the following:
B
R B
B B R B
B B B B B B R R
If there is a red node on every path then there will be at least one black node with two red children. If you push the red node up the tree at every position where this occurs, starting from the bottom eventually you will push the red node to the tree root at which point you can flip the color and the tree height has grown by one.
Also, if you ever reach a configuration where an entire level is red all the nodes at that level can be flipped without altering the tree properties and again the height has grown by one.
It is somewhat trickier if some paths have more than one red node, in that case you will want to work from the top-most red node in that path and push a red node from the other branch to match it.
answered Mar 23 at 3:32
SoronelHaetirSoronelHaetir
7,2711514
Thank you, "If there is a red node on every path then there will be at least one black node with two red children. "was an eyeopener
– Tim D
Mar 23 at 15:20
add a comment |
The easy way to think of it is by pushing red nodes up a tree and then turning the root black again.
Imagine a tree like the following:
B
R B
B B R B
B B B B B B R R
If there is a red node on every path then there will be at least one black node with two red children. If you push the red node up the tree at every position where this occurs, starting from the bottom eventually you will push the red node to the tree root at which point you can flip the color and the tree height has grown by one.
Also, if you ever reach a configuration where an entire level is red all the nodes at that level can be flipped without altering the tree properties and again the height has grown by one.
It is somewhat trickier if some paths have more than one red node, in that case you will want to work from the top-most red node in that path and push a red node from the other branch to match it.
answered Mar 23 at 3:32
SoronelHaetirSoronelHaetir
7,2711514
The easy way to think of it is by pushing red nodes up a tree and then turning the root black again.
Imagine a tree like the following:
B
R B
B B R B
B B B B B B R R
If there is a red node on every path then there will be at least one black node with two red children. If you push the red node up the tree at every position where this occurs, starting from the bottom eventually you will push the red node to the tree root at which point you can flip the color and the tree height has grown by one.
Also, if you ever reach a configuration where an entire level is red all the nodes at that level can be flipped without altering the tree properties and again the height has grown by one.
It is somewhat trickier if some paths have more than one red node, in that case you will want to work from the top-most red node in that path and push a red node from the other branch to match it.
answered Mar 23 at 3:32
SoronelHaetirSoronelHaetir
7,2711514
edited Mar 23 at 5:24
answered Mar 23 at 3:32
SoronelHaetirSoronelHaetir
7,2711514
answered Mar 23 at 3:32
SoronelHaetirSoronelHaetir
7,2711514
answered Mar 23 at 3:32
SoronelHaetirSoronelHaetir
7,2711514
7,2711514
Thank you, "If there is a red node on every path then there will be at least one black node with two red children. "was an eyeopener
– Tim D
Mar 23 at 15:20
add a comment |
Thank you, "If there is a red node on every path then there will be at least one black node with two red children. "was an eyeopener
– Tim D
Mar 23 at 15:20
Thank you, "If there is a red node on every path then there will be at least one black node with two red children. "was an eyeopener
– Tim D
Mar 23 at 15:20
Thank you, "If there is a red node on every path then there will be at least one black node with two red children. "was an eyeopener
– Tim D
Mar 23 at 15:20
add a comment |
Thanks for contributing an answer to Stack Overflow!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f55304714%2fprove-that-a-red-black-tree-remains-valid-after-turning-a-set-s-of-red-nodes-bla%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
