« Monkeys on Trees I | Main | parshing county, Nevada - continues »

Monkeys on Trees !

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.




Posted on Sunday, March 23, 2014 at 11:04AM by Registered CommenterProkash Sinha | CommentsPost a Comment | References2 References

References (2)

References allow you to track sources for this article, as well as articles that were written in response to this article.
  • Response
    Response: snapchat app
  • Response
    Response: Baidu Root

Reader Comments

There are no comments for this journal entry. To create a new comment, use the form below.

PostPost a New Comment

Enter your information below to add a new comment.

My response is on my own website »
Author Email (optional):
Author URL (optional):
All HTML will be escaped. Hyperlinks will be created for URLs automatically.