A look at trees
--
Data Structures and Binary Trees
There are plenty programming data structures each with their own characteristics, pros and cons. A data structure is just a way to organize data to be usable. Examples include arrays, linked-list, matrixes, and binary tress. Binary trees are defined by nodes and up to 2 children, a left and right pointer.
The uppermost node is known as the root of the binary tree. Each node in a binary tree can have children but it is not required. When a node has no children it is referred to as a leaf or leaves. When you traverse a tree, access data within it, you have to travel down from node to node.
Purpose of trees
A good example of a binary tree is your computers directory. Your folders and files have a hierarchical structure, if you want to get to a downloads you have traverse a path similar to something like this.
C:Drive > User > Downloads > *Filename*
You can’t access the file without traverse from the “User” node, then the “Downloads” node and then the file itself.
Trees can be faster at access data than other data structures especially when they are sorted like a Binary Search Tree. They are mostly used in routing algorithms, multi-stage decision making and building out large structures both scalable and fast.
Quick example
The above image shows how one would traverse the tree find results. An example of how this would work in JavaScript would look like this.
function search(root, key) {
if (root == null || root.key == key)
return root;
if (root.key < key){
return search(root.right, key);
}else {
return search(root.left, key);
}
}// The key is the case would be 27
// The script will continue to run checking all nodes from left to right
This works well when the binary tree is organized, also known as the Binary Search Tree. Learning how to organize binary trees can be incredibly helpful. Be on the lookout for the next blog that were I’ll cover the topic of sorting binary trees.
