How many Red-Black trees?

Given $n$, how many red-black trees exist with $n$ nodes?

Can you give an algorithm to compute that value? Hopefully polynomial in $n$.

Note: I haven't tried solving this problem myself, so it is a little open ended and don't expect to see a solution!

[Possible Solution]

2n choose n

A quick one.

Show that the binomial coefficient $\binom{2n}{n}$  (i.e. $2n$ choose $n$) is divisible by $n+1$.

[Solution]

Keep winners, throw losers?

This is a hand from a team game on BBO, where people self alert their bids.

You are West and see the opponents get to 3NT.

IMPS N/S	North ♠ KJ4 ♥ KJ543 ♦ KJ85 ♣ 4
West ♠ 53 ♥ T7 ♦ A63 ♣ AK9862

W	N	E	S
		P	1NT1
2C2	X3	P	3NT4
P	P	P

1: 1NT = 13-15
2: 2C = single suited, 6+ cards.
3: X = Game forcing.
4: 3NT = 4-4 majors, maximum hand.

Note, these are self alerted bids and N/S had a misunderstanding about the 3NT bid.

You lead the AK and low club, partner following and declarer showing up with QJx (declarer throwing diamonds from dummy).

Now declarer proceeds to cash 4 spades (declarer has AQxx).

What will you discard on the two spades you cannot follow to? [Please think about it before reading on].



Declarer surely has the HA. If he has the HQ, there is nothing you can do.

So assume declarer has a hand like AQxx, Axxx, Qx QJx.

Now declarer needs to guess whether to go for the heart drop or take the finesse.

Now imagine what happens if you throw your diamond losers and hold on to your club winners.

Declarer will place you with the DA (the way you bid and defended points to that). So declarer will give you 6 clubs, 3+ diamonds (atleast A and the two you discarded), 2 spades and therefore 2 or fewer hearts!

So if you discard two diamonds, declarer will get it right.

In order to make declarer guess, you need to throw a diamond and a club, i.e. throw away a winner!

If you discard a club and a diamond, declarer might place you with xx, QTx, Ax, AKxxxx and take the finesse.

Is It a Red-Black Tree [Solution]

The problem was to give an algorithm to determine if a given binary tree can be coloured with red/black such that it satisfies the constraints of a red-black tree.


Solution

---

A Red black has this property:

For any node, the length of the shortest path (to a leaf node) is atleast half the length of the longest path (to a leaf node). In other words, for any sub-tree, the shortest height is at least half the height.

This condition is actually sufficient too, and can be proved via induction (I am feeling lazy and will leave that to you).

The usage of this condition gives us an $O(n)$ time algorithm to determine if a given binary tree is actually a red-black tree.

Equalize the buckets [Solution]

The problem was:

$(x,y)$ with $x \lt y$ is transformed to $(2x, y-x)$. This process is repeated. For what initial $x,y$ can we end up with equal numbers. $x,y$ are positive integers.

Solution

---

Notice that starting with $(x,y)$ is essentially starting with $(ax, ay)$ for any integer $a \ge 1$.

So assume that $x$ and $y$ have no common factor.

Now for the numbers to become eventually equal, $x+y$ must be even, as the sum of the two numbers never changes.

Thus after one step $(2x, y-x)$, both these numbers are even, and so we can divide out by $2$

Every time we divide out by $2$ the sum is halved.

Thus if $x+y = 2^M Q$, where $Q$ is odd greater than $1$, eventually we end up with an odd sum, and so cannot equalize.

Thus the condition is that if $x/y = p/q$ in lowest terms, then equalization occurs iff $p+q = 2^m$.

Don't be hasty

A quick one for the newer players.

In a teams event, you end up in 6H, after you overbid your hand.


LHO leads a low spade.

IMPS N/S	North ♠ T ♥ KQT982 ♦ K32 ♣ 543
	South ♠ KQJ72 ♥ A3 ♦ A54 ♣ AJ2

W	N	E	S
			2NT
P	3D	P	3H
P	4H	P	6H

RHO wins the spade A and plays back the spade nine.


Don't play the K (or Q/J)! LHO could have led a singleton. If you play the K (or Q/J), LHO will ruff and you will end up a trick short.

Play the 7 and ruff. Draw trumps (you have to hope they are 3-2, or J falls). Then you can cash your spade tricks in peace.

Is it a Red-Black tree?

Red-Black trees are commonly used self balancing binary trees. Another example of a self balancing binary trees is an AVL tree.

A common interview question is to determine if a given binary tree is an AVL tree, based on the height constraints an AVL tree has.

A red-black tree has colouring constraints (check the wiki page above), where each node is coloured either red or black and then there are some constraints based on the colours.

The puzzle here is to determine if a given binary tree of $n$ nodes can be coloured [i.e. each node coloured red or black] so as to satisfy the constraints of a red-black tree.

Can you give an algorithm which runs in $O(n)$ time?

[Solution]