Improve the partition of a perfect binary tree
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?
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?
Consider a case h = 3 (that's actually 4 rows, counting the head). The number of elements in each row is illustrated below.
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.
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:
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.
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.
Last edited on
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.
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.
Last edited on
| 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 (24) 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?
Last edited on
Mmmm, back to the drawing board for me.
Still like thinking in terms of the rows to deal with the ancestry constraint, though.
Still like thinking in terms of the rows to deal with the ancestry constraint, though.
Thanks.
I found a fast algorithm based on your algorithm.
The final algorithm is a brute force search along with some pruning technique.
I found a fast algorithm based on your algorithm.
The final algorithm is a brute force search along with some pruning technique.
Topic archived. No new replies allowed.