Questions tagged [red-black-tree]
A red-black tree is a type of self-balancing binary search tree, a data structure used in computing science, typically used to implement associative arrays.
525
questions
1
vote
0answers
24 views
Red Black Tree - How to handle first items inserted
So, i have written the following code for red black trees using Nodes. I am having trouble with the first inserts, because in order to rotate or relolor the so that the red items will always have ...
0
votes
2answers
56 views
How to overloading operator= in red-black tree? C++
I have a red-black tree that needs to be overloaded with an assignment operator. I kind of overloaded the operator= of a binary tree whose nodes don't know their parents. But how do I do this for a ...
0
votes
0answers
75 views
how to implement a gui to my redBlack Tree for (insertion - deletion - print - clear)
I am in third year in cs department and i want to create a gui that shows the status of the red-black-tree like cs.usfca.edu web site i build the tree but i can't do the gui anyhelp please ?
here is ...
1
vote
2answers
70 views
Red Black Tree, and condition for coloring
Recently I think about BST converting to RB Tree by coloring.
I means what is the sufficient and necessary condition that we can convert BST to RB Tree just by coloring without any other change in ...
2
votes
1answer
31 views
Red Black Tree and Height Property of BST
consider we want just convert BST to red black tree just with coloring without any other change.
Why a Binary search tree with height of 2*log n not always convert to red-black tree using above facts, ...
0
votes
1answer
28 views
Is this an AVL or Red-Black Tree?
I have a simple question, mainly due to my brain quitting on me. Could this be considered an AVL tree? Also could this be considered a Red-Black tree?
I believe that this would not be an AVL tree ...
0
votes
1answer
75 views
Augmenting red-black tree for minDiff
So I have the following question:
You have of set of numbers, S, that you are storing in a red-black tree. You are trying to add minDiff to the red-black tree which gives you the absolute difference ...
1
vote
2answers
100 views
Red-Black Tree - Deletion method in JavaScript
See original Red-Black Tree below:
42B
/ \
10R 64B
/ \ / \
7B 29B 50R 83R
/
5R
I am having trouble when trying to the delete 29. Since trying to delete ...
0
votes
0answers
34 views
Retrieve the ith element of a std::map in O(logn) time [duplicate]
My question pertains to the std::map class in the STL of c++. My understanding is that it is implemented using red black trees to allow for O(logn) insertions, deletions, and lookups while maintaining ...
1
vote
0answers
39 views
In Java HashMap, how many nodes can a red-black-tree node have at most before untreeify because it's too small in deletion?
Java doc of the method removeTreeNode of TreeNode in Java HashMap says
If the current tree appears to have too few nodes, the bin is converted back to a plain bin. (The test triggers somewhere ...
0
votes
1answer
58 views
Why do we need to store a parent pointer for every node in red-black tree?
A red-black tree is an efficient data structure to maintain an ordered set. However, all the implementations I see (such as c++ STL, or the book "Introduction to Algorithms") seem to store a ...
0
votes
1answer
41 views
Deletion of the left-leaning Red Black tree and its invariant
I have difficulty understanding the statement from this paper
To do so, we maintain the in-variant that the current node or its
left child is red. We can do so by moving to the left unless the ...
0
votes
0answers
40 views
Resolving lifetime conflicts in red-black tree implementation
I've been playing around with implementing red-black trees from CLRS in Rust. The code (as it currently stands) is as follows:
use std::cmp::PartialOrd;
use std::fmt::Display;
struct RedBlackNode<'...
0
votes
2answers
22 views
Is RBT always full?
As I understand, binary trees do not have to be full. However, it seems that RBTs have to be full (sometimes children are NIL). Is that true, or am I missing something?
0
votes
0answers
73 views
Constructing a Red Black Tree which takes string as input
i have searched internet to find the way to create a red black tree which takes string as input,
but till now there is no luck so far...
is it possible to construct such a red black tree..
if yes can ...
0
votes
1answer
65 views
Red Black Tree - return all the values greater than X in sorted order
I really need this feature in my project. Namely, I have a Red Black Tree and I need to write a function to return all the values higher than X in the sorted order.
Example:
Given the following RBT
...
0
votes
0answers
40 views
Is it possible to connect a dependent type variable to an attribute of that data type in Idris
I'm working on a red black tree implementation in Idris. In this implementation, the node, in addition to carrying information about its value and colour, also carries information about its black ...
1
vote
1answer
20 views
What benefit does a balanced search tree provide over a sorted key-value pair array?
public class Entry{
int key;
String value;
}
If you have an array of Entry.
Entry[]
You can do a binary search on this array to find, Insert or remove an Entry all in O(Log(n)). I can also do a ...
1
vote
1answer
30 views
CLRS Red-Black Tree deletion
I copied pseudocode from CLRS chapter on red-black trees, also based on this implementation. My copied code doesn't properly work when deleting root nodes (root node doesn't change before fixup, which ...
0
votes
1answer
47 views
Idris returning dependent type signature error with if statement in type definition
I'm working on a red black tree implementation in Idris. In this implementation, the node, in addition to carrying information about its value and colour, also carries information about its black ...
0
votes
0answers
28 views
How to combine a tree ADT which will either be a BST or an RBT depending on the an enumerated type which gets passed to tree_new()?
Ive written code for both RBTs and BSTs, however i am unsure how to combine them together into one data structure?
How would I go about combining these into one data structure?
struct rbtnode{ ...
0
votes
0answers
34 views
Idris function getting pattern matching error on red black tree implementation
I'm working on a red black tree implementation in Idris. In this implementation, the node, in addition to carrying information about its value and colour, also carries information about its black ...
0
votes
0answers
18 views
Red-Black tree insertion not assigning right colors
I have implemented the Red-Black tree in Python, here is my code:
class node:
def __init__(self,value,p,dx,sx):
self.key = value
self.p = p
self.right = dx
self....
0
votes
1answer
51 views
Why is std::map::erase(iterator it) amortized constant?
See https://en.cppreference.com/w/cpp/container/map/erase for reference.
How is erasing a single iterator able to be done in amortized constant time? This seems to imply that the rebalancing of the ...
0
votes
0answers
22 views
Minimum number of nodes to form a red-black tree of height h [duplicate]
Edit: This is a similar question link suggested to me by a user
What is the formula for minimum number of nodes required for a red-black tree of height h
but according to that answer the minimum ...
0
votes
1answer
35 views
Splitting a red-black tree destructively?
I would like to implement a priority queue using a red-black tree. Using a binary heap is O(log n) worst case for deletion, and I will be removing many keys from the queue at once, so I want O(log n) ...
1
vote
1answer
129 views
Is the LL Rotation a single left Rotation or a single right Rotation?
As this for example,
In this post, it says the LL Rotation is a single left Rotation.
https://www.freecodecamp.org/news/avl-tree-insertion-rotation-and-balance-factor/
However, from the wiki of tree ...
-3
votes
1answer
82 views
Red Black tree deletion behaviour [closed]
I have a red black tree as follows:
8B
/ \
4R 10B
/ \ / \
2B 6B 9B 11B
/ \ / \
1B 3B ...
0
votes
1answer
40 views
Error in implementing a Red black Tree using a sentinel object, in Java
So, I am trying to implement insertion for a red black tree, using sentinels as described in the "Introduction to Algorithms".
I've created a Generic class for a red black node, which has ...
-2
votes
1answer
36 views
How many red nodes does a red-black-tree with black height bh(t) have(at most)?
How many red nodes does a red-black-tree with black height bh(t) have(at most)?
bh(t) = It is the number of black nodes on any simple path
A red black tree in our lecture is a binary search tree with
...
0
votes
0answers
37 views
Getting the wrong output after constructing a Red-Black tree from csv file
I'm tasked with opening a csv file, reading from the two columns, and mapping the values (name, number) to a red-black tree. We are to test adding the first 5 elements and performing a traversal to ...
0
votes
0answers
77 views
Iterator for red-black binary search tree in C
I need to find a point from red-black BST that is closest to a given point. To do so I have considered inorder traversal for which I need to keep track of minimum distance and nearest point at every ...
0
votes
0answers
15 views
Red-black tree in data structures
we know AVL trees are better for searching and red-black trees are better for insertion and deletion because they require lesser rotations, but what is the need for colouring the nodes?
0
votes
1answer
22 views
What kind of decisions to consider while choosing the type of a self-balanced BST?
For instance I know the concept and ideas of 2-3 tree and Red-black tree, but could you give me some situations where one of them is better then the other? What questions should I be asking to myself?
...
2
votes
1answer
86 views
Why does this code run for VS but not gcc/g++?
I'm trying to implement a Red Black Tree using VS 2019 as my IDE. It seems to work in VS but when I try to compile and run using anything else, it results in a seg fault whenever my insert function ...
1
vote
0answers
69 views
how to insert nodes in red black tree node?
I had found this implementation in [github][1], i made some changes like adding a 2nd value to the node, and using each left and right node as a pointer Node the problem with the tree it is and ...
0
votes
0answers
76 views
Is there difference between using successor and predecessor in RBT?
Hey I'm a junior student major in computer science, I want to ask is the final tree will be the same when you are using successor or predecessor when deleting in red-black tree? Thanks.
-1
votes
1answer
16 views
Insert elements into a red/black tree that just require color changes and no rotations?
How can I find a sequence of elements that, if inserted into a red/black tree, would be balanced purely by changing colors rather than performing rotations?
1
vote
1answer
198 views
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) ...
0
votes
0answers
38 views
RedBlackTree delete using insert-method (StackOverFlowError)
I somehow get a StackOverFlowError when testing my following method. The tests and helper functions are 100% correct. I'm trying to implement a delete-method for a BinarySearchTree using the insert-...
1
vote
0answers
30 views
Red-Black-Tree delete-Method
This delete method doesn't work:
public void delete(TreeNode toDelete) {
TreeNode z = _nil;
TreeNode x, y;
z = toDelete.p;
y = toDelete;
NodeColor prevColor = y.color;
if (z....
0
votes
1answer
70 views
deleteMin Left Leaning Red Black Tree needs more explanation
I'm reading Left Leaning Red Black Tree in algorithms 4th edition, by Robert Sedgewick. I spent several days trying to understand the deleteMin as a warmup to understanding delete and this is my final ...
3
votes
3answers
339 views
Free List Allocator with Red Black Tree
I'm trying to implement a free list allocator using Red Black Tree for optimize O(LogN) best fit search.
My strategy is that when a block is allocated, it's allocated with a Header where
struct ...
0
votes
1answer
37 views
Issue with the Red Black Delete algorithm mentioned in Introduction to Algorithms,CLRS 3rd edition
RB-DELETE(T, z)
1 y = z
2 y-original-color = y.color
3 if z.left == T.nil
4 x = z.right
5 RB-TRANSPLANT(T, z, z.right)
6 elif z.right == T.nil
7 x = z.left
8 RB-TRANSPLANT(T, z,...
0
votes
0answers
43 views
Drawbacks of having a large Branching factor in a B-tree
In this paper by Demain, et al: a new data structure is proposed where a tree of B-trees is implemented to achieve dynamic optimality. In the entire paper, it is assumed that the B = (logN)^O(1).
...
0
votes
0answers
255 views
Red Black Tree Deletion in C Language
Please Help Me, When I Insert in order :
80,30,90,20,50,40,70,75,72,77,78,76
The Result of the Insert correct, but When I delete 90, The result must be :
50(Black)
30(Black)
77(Black)
20(Black)
40(...
0
votes
0answers
27 views
concurrent read black tree with fine-grained locks
I want to implement the pseudocode in the link, which is about building a concurrent binary search tree.
https://wiki.eecs.yorku.ca/course_archive/2015-16/F/6490A/_media/public:myassignment1.pdf
...
-1
votes
1answer
95 views
how many bits per node
This question comes from an exercise of Algorithm 4.
I paste it here as follows:
3.3.19 With 1 bit per node for color, we can represent 2-, 3-, and 4-nodes. How many
bits per node would we need to ...
0
votes
2answers
97 views
Red Black Tree insertion operation keeps on crashing
I was trying to implement Red Black Tree but was unable to code it myself so I was searching for it's code written in C and found the below code on github I analyzed it and it was pretty straight ...
0
votes
1answer
45 views
Why a Red Black Tree only rotated when the uncle of the inserted node is black? can someone explain the logic behind it's properties?
So lately I've been analyzing the Red black tree and it's properties and trying to reason behind why they are like that, I understand that these constraints are used to keep the tree balanced and ...