[Data Structures] Binary Tree - 2 | Application of Trees (File Systems, BSP)

File Systems

Trees are commonly used to represent hierarchical data. A tree represent files and directories in a file system, since a file system is a hierarchy. 

A file in a file system tree is alwyas a leaf node. 

A directory in a file system tree can be both leaf node or internal node. 

Unlike binary trees that have a fixed number of children per node (0-2), a file system tree must support a variable number of children per directory node. 

 

Binary Space Partitioning (BSP)

Binary space partitioning (BSP) is a technique of repeatedly separating a region of space into 2 parts and cataloging objects contained within the regions. A BSP tree is a binary tree used to store information for binary space partitioning. Each node in a BSP tree contains information about a region of space and which objects are contained in the region.

In graphics applications, a BSP tree can be used to store all objects in a multidimensional world. The BSP tree can then be used to efficiently determine which objects must be rendered on screen. The viewer's position in space is used to perform a lookup within the BSP tree. The lookup quickly eliminates a large number of objects that are not visible and therefore should not be rendered.

When traversing down a BSP tree, half of the spaces are eliminated each level, and approximately half of the elements are elimiated, but not exactly. 

In practice, most BSP implementations partition according to how objects exist in the world, not simply just in the middle.