2
$\begingroup$

The question is not related to the homework

I was working on a homework, and the specification was to generate a random tree with n elements(n being in the thousands for the assignment) and asked me how many of the trees generated were RBT. I have been iterating to the millions now, so I began to wonder what was the probability of this happening, that a tree with lets say 1000 randomly inserted elements, that have randomly generated colors(red or black) is a Red-Black Tree.

$\endgroup$
  • $\begingroup$ What do you mean by "a tree is RBT"? A tree doesn't come with colors on the nodes. Also, note that there are several ways to generate a random binary tree. You are generating a binary tree from a random permutation. $\endgroup$ – Yuval Filmus Jun 5 '17 at 17:46
  • $\begingroup$ Sorry, a tree is a Red-Black Tree. I generated the colors randomly and inserted the value(integer, color) in an array without using any order, straight up like this: (123,'black') and placed that in the array so it wont follow conventional insertion rules. How can I calculate the probability of inserting the values in that way such that it follows all the Red-Black Tree rules(black root, red children's must be black, leaves black and black depth) $\endgroup$ – Daniel Rodríguez Jun 5 '17 at 17:51
  • $\begingroup$ It sounds pretty difficult. $\endgroup$ – Yuval Filmus Jun 5 '17 at 17:55
  • $\begingroup$ @YuvalFilmus I tried starting with small cases but the permutations are just way too much because of the given rules for a binary tree being Red-Black $\endgroup$ – Daniel Rodríguez Jun 5 '17 at 18:00
  • $\begingroup$ I don't know if this helps, because it depends on the actual nature of the problem, but the red-black colouring of nodes is just a way to construct an isomorphism between completely balanced (all leaves are at exactly the same depth) 2-3-4 trees and a subset of binary trees. There's an obvious recursion which can be used to count balance 2-3-4 trees, which might be slightly easier than the recursion to count balanced R-B trees, although they will turn out to be very similar. $\endgroup$ – rici Jun 5 '17 at 23:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.