Improve algorithm speed.
Input:
Label the numbers from 1 to 511 in a perfect binary tree:
You can open the picture if you can not imagine what the tree looks like.
https://gitee.com/wuzhenhai1/my-cdn/raw/master/xxx.PNG
Now try to find the first occurrence of the following number set(S) in T:
1) T[0](the first number in T) must be in S
2) try to use the small numbers as much as possible
3) k = |S|
4) if (x,y) is in S, then x is not the ancestor of y and y is not the ancestor of x in the tree.
I develop an top-to-down recursive algorithm, but it is too slow when there are more than 200 elements.
|
|
Label the numbers from 1 to 511 in a perfect binary tree:
|
|
You can open the picture if you can not imagine what the tree looks like.
https://gitee.com/wuzhenhai1/my-cdn/raw/master/xxx.PNG
Now try to find the first occurrence of the following number set(S) in T:
1) T[0](the first number in T) must be in S
2) try to use the small numbers as much as possible
3) k = |S|
4) if (x,y) is in S, then x is not the ancestor of y and y is not the ancestor of x in the tree.
I develop an top-to-down recursive algorithm, but it is too slow when there are more than 200 elements.
Last edited on
In case this matters to your attempt, the tree you show is not correct.
The 1, 2, 3 and 4 wouldn't be on this positions, for example.
1 would be the far leftmost entry or leaf.
The root might be, in a balanced tree that includes data from 1 to 511 inclusive, something closer to 260.
I may not understand what you're doing or asking, though...we see no code.
A balanced height binary tree will perform reasonably well with data beyond several thousand entries, but then "slow" is relative to expectations.
The 1, 2, 3 and 4 wouldn't be on this positions, for example.
1 would be the far leftmost entry or leaf.
The root might be, in a balanced tree that includes data from 1 to 511 inclusive, something closer to 260.
I may not understand what you're doing or asking, though...we see no code.
A balanced height binary tree will perform reasonably well with data beyond several thousand entries, but then "slow" is relative to expectations.
Last edited on
The tree is right.
The illustrated tree is only used for the forth constraint.
There are at most 511 numbers.
The illustrated tree is only used for the forth constraint.
There are at most 511 numbers.
I feel like I am not understanding the rules.
1 can't be in the table -- is ancestor of everything except itself.
rules say 1 must be in table.
unless T[0] means something else.
1 can't be in the table -- is ancestor of everything except itself.
rules say 1 must be in table.
unless T[0] means something else.
1 may not be in T.
T only picks partial numbers in the tree.
T only picks partial numbers in the tree.
|
|
Last edited on
"The tree is right."
Then either those aren't values in the tree (and I have no idea what those numbers are if they are not values in the tree), or...it isn't a binary tree - not by the classic meaning of that term.
What is it?
If you say it is a binary tree, there are no binary tree algorithms that could search that tree if this lists the values of the leaves. The tree could be traversed, by the standard binary tree algorithms would not list the values in order.
Maybe it is being called a binary tree in the context of your work or study, but it isn't a standard definition. It may be a kind of directed graph or some other data structure.
This looks like the numbers of blocks in a pyramid...well, one side of it or just a triangle if this is 2d (and not necessarily square blocks or tiles), which is the layout of a geometric structure.
Can you show any code?
Then either those aren't values in the tree (and I have no idea what those numbers are if they are not values in the tree), or...it isn't a binary tree - not by the classic meaning of that term.
What is it?
If you say it is a binary tree, there are no binary tree algorithms that could search that tree if this lists the values of the leaves. The tree could be traversed, by the standard binary tree algorithms would not list the values in order.
Maybe it is being called a binary tree in the context of your work or study, but it isn't a standard definition. It may be a kind of directed graph or some other data structure.
This looks like the numbers of blocks in a pyramid...well, one side of it or just a triangle if this is 2d (and not necessarily square blocks or tiles), which is the layout of a geometric structure.
Can you show any code?
Last edited on
Ouch.
You can open the picture if you can not imagine.
https://gitee.com/wuzhenhai1/my-cdn/raw/master/xxx.PNG
A simple view is that:
select k numbers from T and there are 4 constraints. The constraints have already been introduced.
You can open the picture if you can not imagine.
https://gitee.com/wuzhenhai1/my-cdn/raw/master/xxx.PNG
A simple view is that:
select k numbers from T and there are 4 constraints. The constraints have already been introduced.
Last edited on
@Niccolo
Wu zhen hai's use of terminology is correct. What's depicted is a perfect (albeit truncated) binary tree. It's just not a binary search tree.
@Wu zhen hai
We don't know what algorithm you're using nor how you implemented it. Showing the code that's "too slow" would help us help you immensely.
-Albatross
Wu zhen hai's use of terminology is correct. What's depicted is a perfect (albeit truncated) binary tree. It's just not a binary search tree.
@Wu zhen hai
We don't know what algorithm you're using nor how you implemented it. Showing the code that's "too slow" would help us help you immensely.
-Albatross
My implementation is almost a violent enumeration.
I need a smarter algorithm.
Or there is only one stupid algorithm, no smarter algorithm.
I need a smarter algorithm.
Or there is only one stupid algorithm, no smarter algorithm.
Last edited on
Topic archived. No new replies allowed.