Questions tagged [red-black-tree-insertion]
31 questions
4
votes
1 answer
Red-Black Tree in Rust, getting 'expected struct Node, found mutable reference'
I am trying to implement Red-Black Tree in Rust. After 2 days of battling with the compiler, I am ready to give up and am here asking for help.
This question helped me quite a bit: How do I handle/circumvent "Cannot assign to ... which is behind a &…
nurchi
- 770
- 11
- 24
3
votes
2 answers
Red-Black Tree rebalancing crashes on tree rotation
I am implementing a red-black tree. Currently stuck on tree rotations. When I rotate and assign the new left/right children, I crash and burn. The way I have learned to do left or right rotations on a binary tree is like so (in c++):
void…
mnestorov
- 4,116
- 2
- 14
- 24
3
votes
1 answer
Why use heap over red-black tree?
The clear difference is that a red-black tree can support O(logn) removal, compared to heap's O(n) removal.
However, it looks like all operations for a red-black tree are faster/equal tothose of a heap. So my question is, why do we ever use a heap…
Wonjoo Lee
- 99
- 3
- 8
2
votes
1 answer
Red-Black Tree Insertion Code
I'm attempting to write an implementation of a red-black tree for my own learning and I've been staring at this for a few days now.
Could anyone help me figure out how I can get the double rotation cases to work correctly? If you spot anything else…
user3902496
2
votes
1 answer
behavior of red-black tree insert operation for sorted values
I am new to data structures. I have gone through red-black tree insertion algorithm implementation. I am not able to understand, how algorithm takes care of insertion of sorted values.
Let me illustrate with data set [10, 5, 2].
So, Initial 10 will…
Mangu Singh Rajpurohit
- 10,806
- 4
- 68
- 97
1
vote
0 answers
Error: Cannot read field "color" because "u" is null RED BLACK TREE
Hello I have an assignment to implement a RBT tree and then as an application insert dictionary in it for more efficient insertion and searching operations.
When I insert the dictionary file it only reads the first word and 2nd word but doesn't fix…
blackraven
- 11
- 1
1
vote
1 answer
How is this RBT considered balanced?
I've been playing with a RBT visualizer and don't understand how the following is considered height-balanced. The wikipedia article claims that if the RBT properties are satisfied, then the height of the farthest leaf is no greater than twice the…
ilikemath3.14
- 39
- 6
1
vote
2 answers
Determine node colour in Red Black Tree
I was reading about Red Black Trees, and I understand that nodes can either be red or black. The rules say:
1) Every node has a color - either red or black.
2) Root of tree is always black.
3) There are no two adjacent red nodes (A red node cannot…
darKnight
- 5,651
- 13
- 47
- 87
1
vote
0 answers
C++, Red Black Tree, Color violation fixup after insertion doesn't work properly
I'm implementing a Red Black Tree in C++ and I'm stuck on fixing color violations after insertion.
My left and right rotations seem to work fine but the colors in right branches of the tree are never getting fixed correctly. I think I covered all…
greenbanzai
- 79
- 2
- 7
1
vote
1 answer
Explain why insertion (and the different cases) don't change black height of red black trees
red black tree - insertion - z's uncle is red
Why is black height of node γ(gamma, the top most node) is unchanged after the operation?
I know how to explain why black height of T1 - T4 is the same after operation. But for gamma, I have absolutely…
FabolousPotato
- 65
- 1
- 10
1
vote
1 answer
Segmentation Fault (core dumped) during Red-Black tree "correction" - C
Code is as follows:
#include
#include
#include
#include
#include
typedef struct node
{
unsigned long int val;
bool black;
struct node* parent;
struct node* lchild;
struct…
Βαγγέλης Μαργέτης
- 117
- 1
- 1
- 8
1
vote
1 answer
Red-black tree insertion task
I would like to ask in which order should I add elements: 1,2,3,4,5,6,7, so that tree would be fully balanced and children of root node should be red.
Mirjan Pecenko
- 101
- 1
- 7
0
votes
1 answer
What's causing infinite recursion in my Rust Red-Black Tree insertion code?
How do I stop infinite recursion on the following code? I am having a problem creating the parent link to a node being inserted. If you remove the 2 lines
node.parent = Some(parent.clone()); x2
The code works but with that line, it goes into an…
Frank
- 1
- 1
0
votes
0 answers
Trying to implement red black trees using python. In insertion fix-up, how can I combine the toNextBlackLevel and balancedTree function in endgame
This is my implementation of the two functions. How do I combine the toNextBlackLevel, balancedTree in endgame?
# Provided code to support Task 4:
def toNextBlackLevel(self, node):
# inspect subtree down to the next level of blacks
# and…
James Anderson
- 3
- 2
0
votes
1 answer
Is it possible to avoid duplicate values from being inserted in a Red Black Tree?
This is currently my code for insertion in a Red Black tree. How would I make it so that duplicate values are not added in so that the tree doesn't change?
public void insert(int i) {
Node x = this.root;
Node y = null;
Node z = new…
Tiffany
- 3
- 2