Different types of trees in data structure pdf

The tree shown in Fig 1 is a General Tree. Binary tree is the type of tree in which each parent can have at most two children. The children are referred to as left child or right child.

This is one of the most commonly used trees. We will see all these types in details as we move ahead. Fig 2: Binary Tree Source. In BST, the value of the left child of a node must be smaller than or equal to the value of its parent and the value of the right child is always larger than or equal to the value of its parent.

This property of Binary Search Tree makes it suitable for searching operations as at each node we can decide accurately whether the value will be in left subtree or right subtree. Therefore, it is called a Search Tree. Fig 3: Binary Search Tree Source. AVL tree is a self-balancing binary search tree. This was the first dynamically balancing tree. In AVL tree, each node is assigned a balancing factor based on which it is calculated whether the tree is balanced or not.

In AVL tree, the heights of children of a node differ by at most 1. The valid balancing factor in AVL tree are 1, 0 and When a new node is added to the AVL tree and tree becomes unbalanced then rotation is done to make sure that the tree remains balanced. The common operations like lookup, insertion and deletion takes O log n time in AVL tree.

It is widely used for Lookup operations. Fig 4: Source. Even though this tree is not fully balanced, the searching operation only takes O log n time. The maximum number of children in this type of tree with a node is N. A binary tree is a two-year tree, as at most 2 children in every binary tree node. A complete N-ary tree is a tree where kids of a node either are 0 or N.

Here in this article, we have seen what a tree structure is, different types of trees in a data structure, and its benefits. I hope you got an idea of some of the common trees in the structure of the data. This is a guide to Types of Trees in Data Structure. Here we discuss the basic concept with 6 types of Trees in Data Structure along with advantages.

You can also go through our other related articles to learn more —. Submit Next Question. By signing up, you agree to our Terms of Use and Privacy Policy.

Forgot Password? This website or its third-party tools use cookies, which are necessary to its functioning and required to achieve the purposes illustrated in the cookie policy. By closing this banner, scrolling this page, clicking a link or continuing to browse otherwise, you agree to our Privacy Policy.

Popular Course in this category. Course Price View Course. Free Data Science Course. Login details for this Free course will be emailed to you. Email ID. Contact No. A general tree is characterised by the lack of any specification or constraints on the number of children a node can have. Any tree with a hierarchical structure can be classified as a general tree. A node can have multiple children, and there can be any sort of combination for the orientation of the tree. The nodes can be of any degree, from 0 to n.

Any node in a binary tree can have 0, 1, or 2 nodes at the most. Binary trees in data structures are highly functional ADTs and can be further subdivided into many types. They are primarily used in data structures for two purposes:. The following is a basic diagram of a binary tree in a data structure:. A BST is defined by the representation of the nodes based on three fields: the data, its left child, and its right child. The governing factors for BST are:. Such an arrangement reduces the search times to half of a linear search, as found in an array.

Thus, binary search trees in data structures are widely applicable for searching and sorting compared to other ADTs. Even though both BTs and BSTs are essentially trees in data structures , do not get confused by the similarity in their names. Find out the difference between a binary tree and a binary search tree in detail at upGrad.

The AVL tree is characterised by a self-balancing nature. The heights of two subtrees of its root nodes are restricted to less than two. When the height difference increases above 1, the child nodes are rebalanced.

AVL trees are height-balanced, and this rebalancing occurs through single or double rotations. The balancing factor is the difference between the heights of the left subtree and the right subtree, and the values are -1, 0, and 1. This type resembles the AVL trees since red black trees are also height-balanced. What separates them is that it does not require more than two rotations to balance them.

They contain an extra bit that defines the red or black colour of a node, which ensures that the trees are balanced during deletions and insertions.

The red black colour coding is also repainted during changes but at almost no extra cost of memory. Another subtype of the binary search tree, the splay tree, has a unique property of performing rotational operations to adjust the recent node. The node that is accessed recently is arranged as the root node by performing a rotation.

It is a balanced tree, but not a height-balanced one. After every operation, the tree is rotated to balance itself, and the searched element is arranged to the top as a root node. In a heap data structure, the root node has the lowest value, and its child nodes both left and right have larger values.

Thus, a treap holds a value in the form of a key resembling BSTs and a priority like heaps.