   A tough one: how many red black trees ?
  Hello !Thats gonna be a tough question I think, and I'm not even sure it has a definite answer at all.Given a subset of N integer number (with no duplicated), how many possible ways are there to arrange them in a red-black tree fashion (depending on N)This is no homework of course, I was just wondering if there could be a best solution for arranging my resources ID in a red black tree. If I should add them as they come or reorder them while I can (at load time). Though, please not this is not my point, I'm just interested in the first question, if some math freaks out there know something about this (or how many binary trees would be fine as well)thank you ! :)You can even play itJanta.   
Number of possible Binary trees over n items: eg, n=5, S={1,2,3,4,5}Choose an index from the first n-1 possible values>> in the range [0,3], i=2Replace that element and the next with a pair of those two>> {1,2,3,4,5} becomes {1,2,{3,4},5}Now the parent set has n-1 elements, repeat with n = n-1 until n-1 == 1So the number of possible binary trees over n items is (n-1)!The constraint on a red black tree is that the longest path cannot be longer than twice the length of the shortest path. It is not clear to me, at first glance, how to extend my explanation to solve for RB trees. I'll think about it some more.There is little sense in preordering the loading of your resources for an RB tree, they are an extremely efficient BBST. Just the act of reordering your input would probably cost more than the sort that the tree carries out.   ;  In fact youre right there is no point in my question, if not curiosity :)   ;Quote:Original post by jantaIn fact youre right there is no point in my question, if not curiosity :)Curiosity leads to enlightenment, and I encourage it!   ;  It might be interesting to approach this from a different path.How many RB trees of height exactly N are there?How many RB trees of height between N and M are there?