Improve the partition of a perfect binary tree

[Wu zhen hai]

If the height of a binary tree is h, and its node count is 2^(h+1)-1, then the binary tree is perfect.
For example, a perfect binary tree whose height is 1 has 3 nodes.

Now, there are 2 perfect binary trees and their heights are both h.

Please divide their nodes(from two trees) into (h+1) parts and the following are limits:
1) the absolute difference between node count in any two parts does not exceed 1
2) any two nodes(A, B) in any part: A is not the ancestor of B and B is not the ancestor of A.

I design an exhaustive search to solve it.

Actually, I know that the exhaustive search can not solve the problem perfectly. It should can solve the case when h = 9 in several minutes.

Who can improve the speed?

[lastchance]

Consider a case h = 3 (that's actually 4 rows, counting the head). The number of elements in each row is illustrated below.

A B
1 1
2 2
4 4
8 8

Do an INITIAL partitioning by taking first row of A with last row of B, second row of A with second-to last row of B. This will give h+1=4 partitions with no ancestry, but not balanced in number: there tends to be more at the ends.

A(1)+B(8) -> 9 elements
A(2)+B(4) -> 6 elements
A(4)+B(2) -> 6 elements
A(8)+B(1) -> 9 elements

Now we have to do some exchanges to get the imbalance in size minimised; each row should only have 7 or 8 elements. But we have to preserve no ancestry. So we can always swap two from a lower with one from a higher row, preserving no ancestry. Here that gives:

A(1)+B(6 from 4th row + 1 from 3rd row) -> 8 elements
A(2)+B(3 from 3rd row + 2 from 4th row) -> 7 elements
A(3 from 3rd row + 2 from 4th row)+B(2) -> 7 elements
A(6 from 4th row + 1 from 3rd row)+B(1) -> 8 elements

I think you can generalise this to more rows. Aim is to start with a partition with the no-ancestry requirement, then do unbalanced swaps to meet the length requirements but keep no common ancestry.


As you can see ... I haven't actually tried coding it! I suspect that a heap structure might help you.

[Wu zhen hai]

Good thinking. I will try it.

But "we can always swap two ..." is not always right, the precondition is that they are adjacent. We may need swap between non-adjacent rows. You can try h=5, the last row contains 32 nodes.

[lastchance]

You can try h=4, the last row contains 32 nodes.

If h=4 then there are 5 rows and EACH of A or B has 16 nodes (2⁴) in the last row.

I don't know, if h=9 then each of A or B has 512 nodes in the last row, but the final partitions only need 204 or 205 elements. Maybe my initial partitioning wasn't great after all .... Part rows perhaps?

[Wu zhen hai]

Oops!

The heuristic approach can not always work well.

[lastchance]

Mmmm, back to the drawing board for me.

Still like thinking in terms of the rows to deal with the ancestry constraint, though.

[Wu zhen hai]

Thanks.

I found a fast algorithm based on your algorithm.

The final algorithm is a brute force search along with some pruning technique.