erich brant

Ranch Hand

Posts: 246

Vladan Radovanovic

Ranch Hand

Posts: 216

posted 16 years ago

Hi I can tell You only about balanced binary trees. i mean the name tells you right away. Balanced means the child (left or right) can not be more than one level bigger than its sibling. It means it is balanced. the inner working of a tree are such that if the one child becomes more than one level deeper or bigger than the other one, then tree is going to balance itself right away. You want to have it balanced so You can do the search in the O( log N) on average.

Vladan

Vladan

posted 16 years ago

What is a BSP Tree?

Overview

A Binary Space Partitioning (BSP) tree represents a

recursive, hierarchical partitioning, or subdivision, of

n-dimensional space into convex subspaces. BSP tree construction

is a process which takes a subspace and partitions it by any

hyperplane that intersects the interior of that subspace. The

result is two new subspaces that can be further partitioned by

recursive application of the method.

A "hyperplane" in n-dimensional space is an n-1 dimensional object which can be used to divide the space into two half-spaces. For example, in three dimensional space, the "hyperplane" is a plane. In two dimensional space, a line is used.

BSP trees are extremely versatile, because they are powerful

sorting and classification structures. They have uses ranging from hidden surface removal and ray tracing hierarchies to solid

modeling and robot motion planning.

Example

An easy way to think about BSP trees is to limit the discussion to two dimensions. To simplify the situation, let's say that we will use only lines parallel to the X or Y axis, and that we will

divide the space equally at each node. For example, given a quare

somewhere in the XY plane, we select the first split, and thus the root of the BSP Tree, to cut the square in half in the X

direction. At each slice, we will choose a line of the opposite

orientation from the last one, so the second slice will divide

each of the new pieces in the Y direction. This process will

continue recursively until we reach a stopping point, and looks

like this:

The resulting BSP tree looks like this at each step:

Other space partitioning structures

BSP trees are closely related to Quadtrees and Octrees. Quadtrees

and Octrees are space partitioning trees which recursively divide

subspaces into four and eight new subspaces, respectively. A BSP

Tree can be used to simulate both of these structures.

--

Overview

A Binary Space Partitioning (BSP) tree represents a

recursive, hierarchical partitioning, or subdivision, of

n-dimensional space into convex subspaces. BSP tree construction

is a process which takes a subspace and partitions it by any

hyperplane that intersects the interior of that subspace. The

result is two new subspaces that can be further partitioned by

recursive application of the method.

A "hyperplane" in n-dimensional space is an n-1 dimensional object which can be used to divide the space into two half-spaces. For example, in three dimensional space, the "hyperplane" is a plane. In two dimensional space, a line is used.

BSP trees are extremely versatile, because they are powerful

sorting and classification structures. They have uses ranging from hidden surface removal and ray tracing hierarchies to solid

modeling and robot motion planning.

Example

An easy way to think about BSP trees is to limit the discussion to two dimensions. To simplify the situation, let's say that we will use only lines parallel to the X or Y axis, and that we will

divide the space equally at each node. For example, given a quare

somewhere in the XY plane, we select the first split, and thus the root of the BSP Tree, to cut the square in half in the X

direction. At each slice, we will choose a line of the opposite

orientation from the last one, so the second slice will divide

each of the new pieces in the Y direction. This process will

continue recursively until we reach a stopping point, and looks

like this:

The resulting BSP tree looks like this at each step:

Other space partitioning structures

BSP trees are closely related to Quadtrees and Octrees. Quadtrees

and Octrees are space partitioning trees which recursively divide

subspaces into four and eight new subspaces, respectively. A BSP

Tree can be used to simulate both of these structures.

--

erich brant

Ranch Hand

Posts: 246