Skip to main content

Basic concept of Trees and its type In Data Structure

      ⇰ TREE :-

Tree is one of the important non-liner data structure in computer science. Many real life problems can be represented and solved using trees. Trees are very flexible, versatile and powerful non-liner data structure that can be used to represent data items possessing hierarchical. 

 

  Other data structures such as arrays, linked list, stack, and queue are linear data structures that store data sequentially. In order to perform any operation in a linear data structure, the time complexity increases with the increase in the data size. But, it is not acceptable in today's computational world. Different tree data structures allow quicker and easier access to the data as it is a non-linear data structure.


  A tree is an ideal data structure for representing hierarchical data. A tree can be theoretically defined as a finite set of one or more nodes or data items such that :-
i >  There is a special node called the root of the tree.
 ii > All nodes are partitioned into number of nodes each of which is itself a tree, are called sub tree.

  

    APPLICATION OF TREES :-
 Easy to search data by traversal.
  ∗ Manipulate  hierarchical data as well as sorted lists of data.
   Used in  Router algorithms.
  ∗ Form of a multi-stage decision-making.


  ⇰ BASIC TERMINOLOGIES :-

Node :- It contains a key or value and pointers to its child nodes. The first node is called root node and the last nodes of each path are called leaf nodes that do not contain a link/pointer to child nodes. The node having at least a child node is called an internal node.


Edge :- The edge is the link between any two nodes. It means every node is connected to other nodes with the help of edges.


Height :- The height of a node is the number of edges from the node to the deepest leaf . It is the longest path from the node to a leaf node.


Depth :- The depth of a node is the number of edges from the root to the node.


Degree :- The number of  a node is the total number of branches of that node.


Forest :- The collection of many disjoint trees is called forest.

Tree implementation in Java (root, parents and children) - Stack ...



  ⇰ TYPES OF TREE :-

There are many kinds of tree data structure but we will discuss here few of them which are as follows :-

  i > General Tree.
 ii > Binary Tress.
iii > Binary Search Tree.
iv > AVL Tree.

i > General Tree :- If no any constraint is applied on the hierarchy of the tree then that tree can  said to be general tree. Every node may have infinite number of children in general tree. This type of tree is the super-set of all other trees. This is the simplest type of tree.



Difference between General tree and Binary tree - GeeksforGeeks




ii > Binary Tree :- A tree in which every node can have maximum of two children is called as Binary Tree.. In binary tree that two children  are known as Left child and Right Child. It is also a method of placing and locating the records in a database.



  Binary Trees

 Here A is root node and B & C are child of A . Again B have one child D and C have two child E & F. We can see here every node have maximum of two children only so this tree is binary tree.


iii > Binary Search Tree :- Binary Search Tree is a binary tree where all nodes of left subtree are less than root node , all nodes of right subtree are more than root node and both subtrees of each node are also binary search trees.


Binary Trees


Here 10 is considered as root node and children are 6 and 18. 6 is connected on left as 6 is smaller then 10 and 18 is connected on right  as 18 is greater than 10 and so on.  



iv > AVL Tree :- An AVL is balanced binary search tree named after their inventors, Adelson-Velskii and Landis. In AVL tree the sub-trees of every node differ in height by atmost one and every sub-tree is an AVL tree.


LL Rotation in AVL Tree - javatpoint
TYPES OF BINARY TREE :- https://priypurnea.blogspot.com/2020/04/types-of-binary-tree.html
 Keep connected and comment for detailed discussion on each type of tree seperately. 

 Follow (follow option is on the top right 3 line icon) and please comment if you find anything incorrect, or to share more information about the topic discussed above.

Comments

  1. Thanku for this... It is very helpful.. I need this

    ReplyDelete

Post a Comment

Please comment.

Popular posts from this blog

Process Scheduling And Types of Process Schedular :-

        ⇰ PROCESS SCHEDULING Process Scheduling  is a task  of Operating System that schedules processes of different states like new, ready, waiting, terminated  and running.This scheduling helps in allocation of CPU time for each process, and Operating System allocates the CPU time for each procss. And the process scheduling plays important role to keep the CPU busy all the time.  ⏩   Followings are some objectives of Process Scheduling :-  i > To increase the amount of users within acceptable response times.  ii > To maintain the balance between response and utilization of system. iii > To decrease the enforce priorities and  give reference to the processes holding the key resources.      ⇰  PROCESS SCHEDULAR A scheduler carries out the pro cess scheduling work. Schedulers are often implemented so they keep all computer resources busy and  allows multiple users to share system resources  to achieve  multiprogramming .  There are  mainy three types of pro

Tokens and its types in 'C'

   Tokens are the smallest individual unit of a program or in simple words it is a main part of C program.Tokens are the building blocks of any program. The smallest individual and basic unit of a C programming is called c tokens.      *    Normally there are six types of tokens in C:- i> Keywords:-          Keywords are special words that are used to give a special meaning to the program and can't be used as variable and constant.They are basically a sequence of characters that have fixed to mean. For example:-                 auto     double      long     break                 float    short        char     if                while    continue   int       void etc. All keywords must be written in lower case.It is 32 in number. ii> Identifiers:-         The identifiers are basically a token. It can be a variable's name or a label's name. So identifiers are actually a user defined data. But there are certain rules to frame an identifier. They are as follo

Process & Its state And process control block :-

                ⇰  PROCESS :- A process can be thought of as a program in execution. Means when any program is executed it becomes process. A processwill need certain resources such as CPU time , memory, files and I/O devices to complete its task. These resources are allocated to the process either when it is created or at the time of execution.             A process is the unit of work in most systems. A system consistes of a collection of processes. All these processes may execute concurrently. Traditionally a process contained only a single thread. Most modern operating ststems now supports processes that have multiple threads.         The operating system is responsible for several important works of process management as - the creation and deletion of process, the schrduling of process, communication and deadlock handling of process. Process is broudly divided into two types:-  i> System  Process. ii> User Process. Early computers allowed only one program be ex