A road named NoNameUno

First my apology for not being active for couple months! Lately, jumping around like a monkey from one place to another and buring really big holes in my pocket, I had to back off from writing...

I've always thought about writing some thing about Tree ADT, and its various incarnations. First it is a very common data structure, second my mother told me that I've monkey's bone in my hip because I do seem to jump around many places except study desk in my school days. Ah, that gives me enough confidence write something about trees...

 Tree was considered, mainly because of applying order relation to find data in O(logN). Basically the binary search tree(BST) is based on implicit order relation, and expect the container is fairly balenced. In reality, a sequence of data may cause the binary tree to be quite unbalenced, so there are many re-incurnations based on different needs. The area of BST has been under active research for long time.

Due to distributed data processing for search, social media, etc. there is another thing came to be useful is - Compititive cost analysis for Online algorithms. This is now a fundamental basis for analysis of lot of data structures including BST and its variants.

The idea behind this analysis technique is to have some solid upper bound to compare with for online objects. Here an object could be thought of an element wrapped inside a data structure object. In case of a BST, inside a BST node. For distributed processing of queries, social media trolling etc. the elements are random, and there is no apriori knowledge of the elements. Think about a random infinite sequences of elements. Now apply your best strategy for you implementations, and analyze using the Compititive cost analyss paradigm.

A FRIENDLY WARNING - This set of notes going to be rather long, and perhaps boring, but I hope it is going to high light some key points !!!

The tree structure and its implementations & analysis is really a subset of graph algorithms, which in turn is a subset of Discrete Mathematics. For example, given a connected graph, and a vertex of the graph, create a tree rooted at that vertex is one example of what I meant by tree being a subset of graphs.

 Way back when I was in graduate school persuing Discrete Math and Algorithms, I was lucky enough to have both my advisors with Erdos Number One. A person has erdos number one, if co-authored a paper with Paul Erdos, a legend in the field of discrete math. So I got some exposure to think from high enough level to encompass related algorithms.

I intend to cover the following topics about Tree, and some more as I go along -

1) Creating random trees, using c programming and data structures.

2) Tree traversals ( inoder, preorder, postorder). BFS, DFS

3) Parameters and attributes of a Tree, why they are important etc.

4) Random set of operations - insertion, deletion, rotations, balencing etc.

5) Kinds of trees, and why they are needed - Red-Black, AVL, among others.

6) Different transformations - these are to solve tree related algorithms.

7) Offline and online analysis - Worst case, Average, Amortized, and Compititive analysis.

8) etc.