What are the different tree methodologies in data structure?

Answer 1

The question itself is a bit vague since it doesn't suggest whether you're asking about the types of trees or the operations which can be performed on trees.

A tree is a data structure which stores information in a logical way that typically is ideally suited for searching quickly, often by ordering the nodes or items of the tree, also ideally, nodes should be able to be added to or removed from a tree quickly and efficiently. Often, trees are chosen as a means of simply structuring data in a meaningful way with no concerns as to their performance.

When trees are chosen as an alternative to a list, the reason for this is to gain the benefits of rapid insertion, searching and deletion of nodes. Common tree structures for this purpose are the binary tree and the black and red tree. A binary tree has an extremely simple and extremely fast method of searching for data, but it is highly dependent on nodes being added in an order which is somewhat random. If ordered data is added to a tree, the depth of the tree will be linear, thereby providing no benefits over a linked list in addition, removal of nodes can cause a binary tree to have to be rebuilt as all the nodes beneath the deleted node will have to be re-added to the tree, typically under different nodes, commonly causing linear branches of the tree and slowing down application performance.

R&B trees were designed to address many of the issues of a binary tree. By developing a data structure which intentionally keeps the depth of the tree shallow, high speed searching and node removal can be achieved, but at a cost to the insertion algorithm which is designed to "shake things up" a little. R&B trees are far beyond the scope of this answer.

General trees are used less as a means of providing ideal performance but instead are intended as a means of providing structure for data. General trees store information in a way which reflects the data format itself. An example of a general tree is the file system of a disk drive. The root directory contains zero or more children which each contain zero or more children which each contain zero or

more... you get the point. This structure is also used for things like the abstract syntax tree of a compiler. Source code is parsed into "tokens" which are the structured as nodes of a tree which are then "walked" when optimizing and producing binary code.

There are many more types of trees. Many of which ate covered by Donald Knuth in extensive, if not insane detail in "The Art of Computer Programming".

Among the operations you'd perform on the tree are insertion, deletion, searching, walking, reduction, simplification and more.