Understanding Binary Trees🌳
Disclaimer
This is by no means an accurate guide to working with binary trees. Most of what I discuss and implement is from reading a bunch of articles online and trying to remember my data structures and algorithms course I took in my 2nd year of university. My core goal with implementing a base binary tree data structure is more for my own understanding and I can only hope that for those who are reading this you gains some understanding too.
I will post some useful links that I am using that explain everything I discuss here.
What I understand so far
To model the hierarchical structure of a file system we use a binary tree. A binary tree specifically gives us a best case of O(logn) time for searching, insertion and deletion since we only ever (at best) keeping looking at half the the number of items at every level of the tree (hence binary). In the below example, if I search for the node labelled A then,
instead of traversing 9 nodes (worst case linked list) I only traverse 4 nodes. The drawback to a binary tree is if we have a degenerate tree and it would basically be traversing the elements of a linked list. So one thing we need to think about when we optimize code later on would be to try and balance the binary search as we build it (at this point I'm not sure if that is possible).
EDIT: I forgot to mention, no duplicate entries (in my implementation are allowed). I'll probably work in my own exception class just to be fancy that detects when their is a duplicate entry
Currently Implemented
Node
I have implemented a data structure called a Node, which has a label and references to its right and left child. I have also implemented a binary tree class which is instantiated by passing a root node into the constructor. This way we always have something pointing to the root of the tree.
A compare() method that compares a node according to the natural ordering of the label was added. Ideally for the specific implementation of modelling a file system, I will probably create a new type of Node called File that extends the Node base class.
Binary Tree
I make use of recursion to insert and search for a node in the binary tree. I was a bit rusty and figured out that the values from a recursive call must be returned. I was initially just setting the root node in a recursive to the new node added (or searched for).
EDIT: the implementation above allows duplicate entries and does not handle them well. It inserts them as the left child. Based on the above edit I will be disallowing duplicate entries
TODO
Removal of a node will be implemented next.
Comments
Post a Comment