Member Avatar for NICEGUY123

I need some help with a problem. I am attempting to insert numbers into a binary tree, then converted it to a rbtree, just curious on how i can change it over i know that
10 (black), 4(red), 5(black), 6(red), 11(red), 12(black), 13(red) as my input.

int a[] ={10, 4, 5, 6, 11, 12, 13}

the pseudo code that i got from the web is below for a tree-insert. Thanks in advance for any advice or code you can help with.

TREE-INSERT(T, z)	
y = nil	
x = T.root	
while (x == 0) 				
	y = x	;				

if (z.key < y.key) 				
x = x.left;		
else
 x = x.right;	
z.parent = y;	
if (y == 0)					
T.root = z;		
if (z.key < y.key) 			
y.left = z;		
else			
y.right = z;
  • 3 Contributors
  • 4 Replies
  • 115 Views
  • 22 Hours Discussion Span
  • Latest Post Latest Post by Tom Gunn

Dani AI

Generated

A few practical points tied to the existing replies: is correct that a red‑black tree (RBT) is more than a BST with colored nodes — it enforces invariants (root black, no red parent/child, equal black‑height on all root→leaf paths). ’s suggestion to use a visualizer is useful for debugging. If there is a required “premade” tree shape and colors to start with, that complicates matters; if not, the simplest, safest route is to build a proper RBT from the keys and then insert additional keys using the RBT insertion routine.

Recommended, reliable options

  • Easiest and robust: collect the keys from whatever source (original insertion order if you want the same shape, or any order if shape doesn’t matter), start with an empty RBT, and call a standard RBT insert for each key. This guarantees the RBT invariants and is straightforward to test. Complexity is O(n log n) to build from n keys.
  • If you must convert an arbitrary BST with ad‑hoc colors into a valid RBT while preserving as much shape as possible, there is no simple constant‑time fix: you will need rotations/recolors effectively equivalent to running the standard RBT insert/fix routines (or rebuild the tree).

Minimal code sketch (pointer style; sentinel/nil handling omitted for clarity):

enum Color { RED, BLACK };
struct Node { int key; Color color; Node *left, *right, *parent; };

void leftRotate(Node *&root, Node *x) {
    Node *y = x->right;
    x->right = y->left;
    if (y->left) y->left->parent = x;
    y->parent = x->parent;
    if (!x->parent) root = y;
    else if (x == x->parent->left) x->parent->left = y;
    else x->parent->right = y;
    y->left = x; x->parent = y;
}

void rbInsertFixup(Node *&root, Node *z) {
    while (z->parent && z->parent->color == RED) {
        // handle left / right cases (mirror each other),
        // perform recolor or rotate+recolor as in standard RBT algorithm
    }
    root->color = BLACK;
}

Testing and tips

  • After any operation validate: root is black, no red node has a red child, and every root→null path has same black count.
  • Use a visualizer (for example Visualgo or the David Galles red‑black visualizer) while stepping through insert/fixup to see rotations and recolors.
  • For references and full pseudocode, consult the Red‑Black Tree article and standard algorithm descriptions (CLRS / GeeksforGeeks).

Recommended Answers

All 4 Replies

Member Avatar for Tom Gunn

A red black tree is more than just a binary search tree with nodes marked red and black. The structure also has to be balanced according to the red black rules. Why not do a red black insert in the first place instead of trying to convert between a simple binary search tree and a balanced red black tree?

Member Avatar for NICEGUY123

A red black tree is more than just a binary search tree with nodes marked red and black. The structure also has to be balanced according to the red black rules. Why not do a red black insert in the first place instead of trying to convert between a simple binary search tree and a balanced red black tree?

I have to start with a premade tree with the following parameters.

10 (black)
4(red)
5(black)
6(red)
11(red)
12(black)
13(red)
Then insert nodes like 9 15 18 into this tree. So i thought create the tree in a binary tree it would be easier to handle. But do you have any suggestions on how to do this.

Member Avatar for Tom Gunn

So i thought create the tree in a binary tree it would be easier to handle.

I disagree. You can manually create the tree easily since it is small and the rules for red black insertion are simple. But if this is a school exercise, I can guarantee that adding the next three nodes will require rotations. So you will be writing a red black insertion function anyway. It is easier to create the tree using that algorithm from the start.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.