Binary Search Tree


Today I learned about 
Binary Search Tree
It's a data structure that makes it easier to find, add, remove, data really really fast...more on that later.

The simplest way I think about linked list is like a well a tree...
but not like a normal tree, it's more like a network of trees.




Each of the nodes on the tree starting from the root node will have a value and two children.
From looking at this graph you can already see that a node will no child is the end of the tree.

```javaScript

function binarySearchTree(rootValue) {
  this.value = value;
  this.left = null;
  this.right = null;
}

```
 we start the tree like with a root node like so, and start with no child, on either left or right, we than insert value into the tree to add to the tree.

This data structor doesn't look too different from a "linked list".
You got an property that hold a value, and two nodes, in this case we have left and right child, instead of front and back nodes in a "linked list"

But what makes this binary search tree awesome is that it works really well with the power of...

                                                                    RECURSION



Because each of the node on the tree have the same data structor as each other node, we can treat all the nodes the same way and use the same logic on them.

```javaScript

binarySearchTree.prototype.depthFirstTraversal(){ 
  
  // in-order traversal

     // checks the left side of all the child until there is no more left child
     // looks at the current node
    // checks the right side of all the child until there is no more right child
    // recursion unwinds from most left bottom to most right bottom
// pre-order traversal // looks at the current node
    // checks the left side of all the child until there is no more left child
   // checks the right side of all the child until there is no more right child
   // recursion unwinds from left most branch top to bottom to right most 
      branch
// post-order traversal
   // checks the left side of all the child until there is no more left child
  // checks the right side of all the child until there is no more right child
 // looks at the current node
 // recursion unwinds from left most branch to right most branch order,
    bottom to top order
}
```

We can write a function that looks at each node and check it's children for value and using that to keep the recursion going stop the recursion.
Note this only works with a balanced tree.

BinarySearchTree is fast to search data, using binary search we get the
big O notation: "O (log n)" logarithmic run time, which is really really fast...

Think finding a name in the phone book fast.



Comments

Popular posts from this blog

CSS Review

Hash Table

More CSS ugghhh