Binary search trees are a special type of tree data structure. They get that name from the binary search algorithm they utilize. This allows for searching that chops off half the values from the tree when the value being searched for can't be stored in the other half.
The above graphic is an example of an unbalanced binary search tree because the number of branches/leaves aren't equal on either side of the root. Here's a cool visualizer of BSTs if you want to play around with them.
Binary search trees start with a root node and then have branches connecting to up to two leaves. The lower value is always to the left of the node and the higher to the right which allows for the chopping actions during search discussed previously.
Binary search trees allow for logarithmic operations along the tree structure. Once a binary search tree reaches a significant height, certain operations will become near linear.
Now that we've got same basics covered, let's look at a real world usage.
3-D Gaming
One approach to 3-D gaming uses a variation of binary search trees called binary space partitioning.
There's an interesting 3-D Rendering of a BSP Tree here.
Doom was the first game to utilize binary space partitioning in 1991. It was revolutionary for the time and was written so that there would be no advantage for someone with more powerful hardware unlike in contemporary gaming.
Before each level started, the game would preload the map of the level including the BSP data for all of the walls. These calculations were why there was often a longish pause between levels during gameplay. Thus the wall data is static and walls cannot move in the game and all doors move on a vertical axis.
Each level(root node) is a binary tree and each location in the level is at a node on the tree. There are specific data values at each branch and leaf that allows for the renderer to properly show the recursive traversal of the tree visually. Once an area is fully rendered, the renderer immediately moves to the adjacent area allowing for a relatively smooth flow of the walls as the marine moves down the halls. The previously drawn segments are stored in a linked list so that they can easily be accessed as a map for what has already been rendered.
The astronomical increases in processor power and powerful discrete graphics cards make Doom seem like Asteroids for someone who played Doom in their childhood. Not being truly able to look up or down seems patently absurd to a young person today. Respect still needs to be paid to a true gaming classic. Hope you enjoyed delving into what makes binary search trees and Doom tick.
Top comments (0)