| Abstract | Left balanced binary trees can be stored in a linear array. It is also fairly efficient to search in left balanced trees, since going from a parent to a child node can be accomplished with simple shift and add operations. In this brief note, I discuss how to left balance a binary tree. The method is probably not novel, but I did not find other documents on the net describing how to do it.
The technique for left balancing binary trees applies also to kD trees which are used for many applications e.g. in computer graphics. kD trees are very suitable for finding the closest point from a set of points or a group of points in some region. To give an example of an application, kD trees are used to store photon maps in global illumination. |