Trees In Java

We have read about linear data structures like arrays, linked lists in which arrange the data sequentially. Similarly, we have different data structures which are capable of storing different kinds of data.

The tree data structure is a non-linear data structure used to represent the data in a hierarchical form. The example given below shows the tree data structure.

Example- Suppose we want to show the hierarchical relationship between the principal and the employees in the school.

In the above example, we have shown the tree, which depicts the hierarchy of a school organization.

In this structure, the Principal is head of the school, and the Principal has two direct reports or, you can say, two direct working hands, which are Incharge and Coordinator, and under them, there are three heads are facilitators. The Principal distributes the school work to Incharges and coordinators, and then it is passed to facilitators. Now, you can see that there is a particular kind of logical structure, and this particular structure is called a tree. This tree is similar to a real tree, so it is given the name of Tree. In this structure,  the root is at the top, and its branches are in the downward direction. 

If we would say about tree data structure in one line, then we would say that tree data structure is an efficient way of storing data hierarchically.

Some basic terms of Tree data structure

Some basic terms which are used in the tree data structure are as follows-

The above structure is called the tree.  The nodes are also termed as the key leaf. The lines which are connecting the nodes or leaves are called the link between two nodes or two leaves.

Root Node- This node is the topmost node in the tree hierarchy. The root node doesn't have any parent. In case if there is any node that is directly linked to any other node, then it would be called a parent-child relationship. 

Child Node- If the node or the key is the descendant of any other node, it is known as a child node.

Parent Node- If there is any other node connected to the sub-node or contains a sub-node. Then that node is termed as the parent node.

Siblings- The nodes which share the same parent node then it is termed siblings.

Leaf Node- The nodes in the tree that do not contain any child node, term it as a leaf node. It is present at the bottom-most of the tree, and there can be any number of leaf nodes. Leaf nodes are also called external nodes.

Internal Node- These kinds of nodes have at least one child node, termed the internal node.

Properties-

1. The tree data structure is also known as a recursive data structure. The reason behind being called the recursive data structure is that it has a root node. The root node contains all the links of the roots of its subtrees. We all have seen the tree structure, which is in a hierarchical form. Hence, the recursion property of the tree data structure can be implemented in various applications.

2. In the tree data structure, if there are n nodes, then it will have n-1 edges.

3. In the tree data structure, the depth of any node x can be defined as the number of edges present between the root node and node x. The most important thing is that the depth of the root node is 0.

4. The height of any node x can be defined as the longest path from node x to the leaf node.

Types of Tree data structure

1. General Tree- A node can have either 0 or the maximum number of n nodes in the general tree data structure. The general tree data structure doesn't have any restriction to be imposed on the degree of the node. The degree of a node can be defined as the number of nodes the node can contain.

2. Binary Tree- With the name, we can guess that what this tree is all about. This tree utmost can have two child nodes. In simple terms, if you have to tell about binary tree data structure, it is a tree with either 0 nodes, or 1 node, or 2 nodes.

3. Binary Search Tree- This tree data structure is also called the node-based data structure. It is a non-linear data structure in which one node is being connected to n number of nodes. One thing should always be kept in mind: the value of the left subtree should be less than the root node, and the value of the right subtree must be bigger than the root node.

4. AVL Tree- It is also called the variant of the binary search tree. AVL tree satisfies the properties of both binary tree and binary search tree. One thing which makes the AVL tree so famous is that it is self-balancing which means that it balances the height of the left subtree and the height of the right subtree. This balancing is being measured in terms of the balancing factor. Here, the balancing factor is the difference between the height of the left subtree and the height of the right subtree.

5. Red-Black Tree- It is also the binary search tree. A red-Black tree is also a self-balancing binary search tree, as well as it also a height balancing binary search tree. The reason behind using the Red-Black tree is that in the AVL tree, we do not know how many rotations are required so that the tree can be balanced, but in the Red-black, we need a maximum of 2 rotations to balance the tree. The Red-Black tree contains one extra bit that represents either the black or the red color of a node to ensure that the tree is being balanced or not.

6. Splay Tree- Splaying means recent accessed node. So, the recently accessed node is placed at the root position in the Splay tree data structure.

7. Treap- The name of treap data structure came from tree and heap data structure. So, it has the properties of both data structure that is of tree data structure and the heap data structure.

8. B-Tree- B-tree is a balanced tree but in terms of the order which means that B-tree balances the order of the tree. In the B-tree, we can have more than one key and more than two children.

Implementation-

From the above structure, we can see that a node contains three fields that are-

• The first field stores the address of the left child.

• The second field stores the data.

• The third field stores the address of the right child.

Hence, keeping this sequence in mind, we have to implement the tree.

Applications of Tree Data Structure-

• There are many applications of trees which are as follows-

• Trees are used to store the data naturally in a hierarchical structure. 

• With the help of the tree data structure, we can organize the data for efficient insertion, deletion, and searching.

• The tree data structure also has a special kind of tree named Trie, and it is used for storing dictionaries. Trie data structure is a very fast, efficient, and dynamic way of spell checking.

• Heap is also a tree data structure used for storing or implementing data in the form of arrays.

• B-tree and B+ Tree are used to implement indexing in databases.

• The tree data structure is also used for storing data in routing tables in the routers.

Hence, from the above article, we can conclude that the tree data structure is the most efficient and easy way to store data and perform various operations like insertion, deletion, etc., on the data.