In the adventure of object oriented programming, we often find ourselves in situations like the famous character Neo, from my favorite movie "The Matrix".  You are working in your everyday life, oblivious to the things around you and how they actually work, and then you find some tidbit that really makes you think.  It connects the puzzle and how oddly it connects, too.

There are two major players in the world today... data and logic.  It's how we represent our data that really makes it workable in ways we never imagined.  Its the rules that connect the data that make it do the things, represent the things, make up the software, connect the systems, and bind the data into useful representations.

This post is an exploration on the connection of data, the best way to represent data, and the way I perceive data.

Lets jump right in and take a look at a simple example of a binary tree:

In the picture above, the root node of the tree is four.  Four could corrispond to a specific object or memory address in our application. In fact, all of the numbers in the tree could represent keys with pointers to the actual records or data persisted in storage. A binary search tree provides an algorithm and dataset organized in such a way, that it splits the time it takes to find a specific element in the tree in half, for each traversal of a node in the tree.  This is also referred to as log₂(n) in Big O notation, or sublinear because the running time is less than linear running time.

The binary tree above is a balanced binary search tree.  Neither the left or the right side of the number four, root node, are ever 1 less or greater than the other.  That is to say, if we were to add a nine node to the right child of node eight and another right child of node nine, the balance of the binary tree would be lost.  The less balanced the binary tree, the less optimal the running time becomes.  At worst, the running time for the binary search tree becomes linear.  Linear running times are found in unsorted arrays, unsorted linked list (searches, inserts, delets), or contiguous data that requires CRUD functionality.

We find this kind of efficiency useful for reducing the running times in graphics applications and games.  In a game, each frame must perform a set of events, or check a set of values against objects that exist in the current frame or current level of the game.  If you have ever done graphics development, you know that as the number of objects in the scene or canvas grows, the running time of each frame is increased.  Binary search trees are also helpful in determining which objects in the scene are culled.

Check back as I continue my small series on binary search trees and provide credit to the amazing minds behind it.