Geek Answers Handbook

When are two trees equal?

If the relative movement of two biratic trees (and not binary search trees) is the same, do these two trees guarantee the same?

if the answer is no, then do the rounds in the order and in the preliminary order coincide?

+4
source share
3 answers

Definitely not. Two trees

b / \ ad / \ ce

and

  d / \ be / \ ac

both have a workaround of abcde order. In fact, this is a rotation, an operation that saves a bypass .

+8
source

I think no".

It is possible that the two trees are balanced in different ways, but have the same "order" of node values. For example, if from the set

 1,2,3,4,5,6,7

You are building a tree:

  4 2 6 1 3 5 7

in the order of passage will give 1,2,3,4,5,6,7.

however, if you select a different root node (if the list is not sorted correctly in advance)

  5 4 6 2 7 1 3

These two trees will give the same traversal result in order, but (obviously) are not identical.

or even

  7 6 5 4 3 2 1

et cetera.

This is also related to the issue with BSP trees (binary space), which are commonly used when detecting game development collisions and determining visibility.

BSP stores triangles in a tree. Each node contains a triangle or face. The left node contains all the children that are “behind”, and the right child contains everything that is “in front”. Reserve as expected.

If you select the leftmost facet in the scene as your root, the right child will own all the other faces. If you make a bad decision for the right child, the same thing will happen. It is entirely possible to create a BSP compiler that, through idiotic analysis, creates a “tree” that is actually a list (as in my last example above). The problem is to split the data set so that each node splits the remaining list as evenly as possible. This is one of the reasons that BSPs are usually generated at compile time, since building one for very complex geometry can take several hours to find the best solution.

+1
source

NO , and it can be seen in this simple example

  3 2 2 1 3 1 0 0

Both have the same workarounds [0,1,2,3]

But if the bypass of orders and pre-orders is the same, the trees are equal.

+1
source

More articles:


All Articles