Properties:
* Each node has exactly one parent.
* There is a path from the root to every node.
* There are no paths in the tree that form loops .
Important terms:
Height of a tree : The length of the longest path between the root and a leaf.
Depth of a node : The length of the path from the root to the node.
A binary tree is a special kind of tree with a branching factor of 2. Lets apply what we learned in recursion to recursively define a binary tree:
A binary tree is :
- either empty or
- has a node with value k (root ) with a Binary Tree as its left child and a Binary Tree as its right child.
A binary search tree however is a special kind of binary tree with all nodes in our left subtree that have values less than the value k and all the nodes in our right subtree that have values more than the value k.
As shown above we can also define a binary search tree recursively simply by adding the property we just mentioned.
There are three important operations that we are concerned about it in binary search trees :
- Searching for a certain value.
- Insertion.
- Deletion.
Searching is relatively straight forward, where we compare the target's value to the root value and decide which subtree to recurse on.
Insertion however requires us to maintain the Binary Search Tree property after inserting the new value (i.e.insert the node where you would expect it to be if you did a binary search for its value).
Therefore insertion requires searching !!
Finally deletion,, uhmm deletion has a lot of cases and I would like to represent examples of these cases in another post to keep this post brief and clear.
You definitely touched on a lot of important characteristics of Binary Search Trees.The process of searching for and deleting values is pretty simple and the same can be said about deleting when you want to get rid of a node that is a leaf.As you mentioned,there are multiple possibilities to consider when deleting a node therefore deletion is a more complicated process.
ReplyDelete