Binary Trees PDF

What is a tree? A tree is a kind of data structure that is used to represent the data in hierarchical form. It can be defined as a collection of objects or entities called as nodes that are linked together to simulate a hierarchy. Tree is a non-linear data structure as the data in a tree is not stor...

What is a tree? A tree is a kind of data structure that is used to represent the data in hierarchical form. It can be defined as a collection of objects or entities called as nodes that are linked together to simulate a hierarchy. Tree is a non-linear data structure as the data in a tree is not stored linearly or sequentially. Definitions and Concepts of Binary trees, Binary trees are a type of hierarchical data structure in which each node has at most two children, referred to as the left child and the right child. Here are some key definitions and concepts related to binary trees: Node: A node is a fundamental unit of a binary tree that contains data and two pointers/references to its left and right children. Root: The root is the topmost node of a binary tree. It is the starting point for accessing all other nodes in the tree. Leaf Node: A leaf node, also known as a terminal node, is a node that does not have any children. In a binary tree, leaf nodes are the nodes at the bottommost level. Internal Node: An internal node is a node that has at least one child. It is any node in the tree that is not a leaf node. Parent Node: The parent node of a given node is the node that is directly above it in the tree. Each node, except for the root, has a parent node. Child Nodes: The child nodes of a given node are the nodes directly below it. A node can have at most two children: a left child and a right child. Sibling Nodes: Sibling nodes are nodes that share the same parent. In other words, sibling nodes are children of the same parent node. Subtree: A subtree is a portion of a binary tree that consists of a node and its descendants (children, grandchildren, etc.), including all their branches. Height: The height of a binary tree is the length of the longest path from the root node to any leaf node. It represents the maximum number of levels in the tree. Depth: The depth of a node in a binary tree is the length of the path from the root node to that specific node. The depth of the root node is 0. Binary Search Tree (BST): A binary search tree is a binary tree with the additional property that for each node, all the values in its left subtree are less than its value, and all the values in its right subtree are greater than its value. BSTs are commonly used for efficient searching, insertion, and deletion of data. Traversal: Traversal refers to the process of visiting all the nodes in a binary tree in a specific order. The most common traversal algorithms are Inorder (left, root, right), Preorder (root, left, right), and Postorder (left, right, root). Binary trees are versatile data structures with various applications in computer science, including representing hierarchical relationships, organizing data efficiently, and enabling efficient search and manipulation operations. Types of Binary Tree, There are several types of binary trees that exhibit different properties and structures. Here are some commonly known types: Full Binary Tree: A full binary tree is a binary tree in which every node has either zero or two children. In other words, every node is either a leaf node or an internal node with exactly two children. Complete Binary Tree: A complete binary tree is a binary tree in which all levels, except possibly the last level, are completely filled, and all nodes are as left as possible. In a complete binary tree, if any nodes are missing from the last level, they will be in the leftmost positions. Perfect Binary Tree: A perfect binary tree is a binary tree in which all internal nodes have exactly two children, and all leaf nodes are at the same level. It is also known as a complete binary tree. Balanced Binary Tree: A balanced binary tree is a binary tree in which the difference in height between the left and right subtrees of every node is at most 1. A balanced binary tree ensures that the height of the tree is logarithmic in terms of the number of nodes, which leads to efficient search and traversal operations. Skewed Binary Tree: A skewed binary tree is a binary tree in which all the nodes have only one child, either to the left or to the right. Depending on the arrangement, a skewed binary tree can be either left-skewed (all nodes have a left child) or right-skewed (all nodes have a right child). A skewed binary tree can degenerate into a linked list in the worst case. Threaded Binary Tree: A threaded binary tree is a binary tree in which each node is threaded to either its predecessor (in-order predecessor) or successor (in-order successor) in the in-order traversal sequence. Threaded binary trees provide faster in-order traversal without using recursion or stacks. Expression Tree: An expression tree is a binary tree in which each internal node represents an operator, and each leaf node represents an operand. Expression trees are commonly used to represent arithmetic or logical expressions, making it easier to evaluate or manipulate them. Heap: A binary heap is a complete binary tree that satisfies the heap property. In a min-heap, for any given node, the value of that node is less than or equal to the values of its children. In a max-heap, the value of each node is greater than or equal to the values of its children. Heaps are often used in priority queues and sorting algorithms. These are just a few types of binary trees, each with its own characteristics and applications. Understanding the properties and structures of different types of binary trees can help in choosing the appropriate data structure for specific use cases. Representation of Binary tree: Array & Linked List. Binary trees can be represented using arrays by considering the index-based approach. Here's an example of how to represent a binary tree using an array in C: #include #define MAX_SIZE 100 // Array to store the binary treeint binaryTree[MAX_SIZE]; // Function to initialize the binary treevoid initializeBinaryTree() { for (int i = 0; i < MAX_SIZE; i++) {  binaryTree[i] = -1; // Initialize all elements with -1 (indicating empty) } } // Function to insert a node into the binary treevoid insertNode(int data, int index) { binaryTree[index] = data; } // Function to print the binary treevoid printBinaryTree() { printf("Binary Tree: "); for (int i = 0; i < MAX_SIZE; i++) { if (binaryTree[i] != -1) { printf("%d ", binaryTree[i]); } } printf("\n"); } int main() { initializeBinaryTree(); insertNode(10, 0); insertNode(20, 1); insertNode(30, 2); insertNode(40, 3); insertNode(50, 4); insertNode(60, 5); insertNode(70, 6); printBinaryTree(); return 0; } In this example, we define an array binaryTree of size MAX_SIZE to store the elements of the binary tree. The function initializeBinaryTree initializes all elements of the array with -1, indicating an empty node. The function insertNode is used to insert a node into the binary tree at the specified index in the array. The data value is stored at the given index in the array. The function printBinaryTree traverses the array and prints the non-empty elements, which represent the nodes of the binary tree. In the main function, we demonstrate the usage of the array representation of a binary tree by inserting nodes and printing the binary tree. General tree, forest, Expression Tree. Forest and general tree to binary tree conversion. Binary Search Tree Creation, Operations on Binary Search Trees: insertion, deletion & Search an element, Traversals on Binary SEARCH TREE and algorithms. What is a tree? A tree is a kind of data structure that is used to represent the data in hierarchical form. It can be defined as a collection of objects or entities called as nodes that are linked together to simulate a hierarchy. Tree is a non-linear data structure as the data in a tree is not stored linearly or sequentially. Example of creating a binary search tree Now, let's see the creation of binary search tree using an example. Suppose the data elements are - 45, 15, 79, 90, 10, 55, 12, 20, 50 First, we have to insert 45 into the tree as the root of the tree. Then, read the next element; if it is smaller than the root node, insert it as the root of the left subtree, and move to the next element. Otherwise, if the element is larger than the root node, then insert it as the root of the right subtree. Now, let's see the process of creating the Binary search tree using the given data element. The process of creating the BST is shown below - Step 1 - Insert 45. Step 2 - Insert 15. As 15 is smaller than 45, so insert it as the root node of the left subtree. Step 3 - Insert 79. As 79 is greater than 45, so insert it as the root node of the right subtree. Step 4 - Insert 90. 90 is greater than 45 and 79, so it will be inserted as the right subtree of 79. Step 5 - Insert 10. 10 is smaller than 45 and 15, so it will be inserted as a left subtree of 15. Step 6 - Insert 55. 55 is larger than 45 and smaller than 79, so it will be inserted as the left subtree of 79. Step 7 - Insert 12. 12 is smaller than 45 and 15 but greater than 10, so it will be inserted as the right subtree of 10. Step 8 - Insert 20. 20 is smaller than 45 but greater than 15, so it will be inserted as the right subtree of 15. Step 9 - Insert 50. 50 is greater than 45 but smaller than 79 and 55. So, it will be inserted as a left subtree of 55. Now, the creation of binary search tree is completed. After that, let's move towards the operations that can be performed on Binary search tree. We can perform insert, delete and search operations on the binary search tree. Let's understand how a search is performed on a binary search tree. Searching in Binary search tree Searching means to find or locate a specific element or node in a data structure. In Binary search tree, searching a node is easy because elements in BST are stored in a specific order. The steps of searching a node in Binary Search tree are listed as follows - First, compare the element to be searched with the root element of the tree. If root is matched with the target element, then return the node's location. If it is not matched, then check whether the item is less than the root element, if it is smaller than the root element, then move to the left subtree. If it is larger than the root element, then move to the right subtree. Repeat the above procedure recursively until the match is found. If the element is not found or not present in the tree, then return NULL. Now, let's understand the searching in binary tree using an example. We are taking the binary search tree formed above. Suppose we have to find node 20 from the below tree. Step1: Step2: Step3: Height balanced Tree: AVL AVL Tree AVL Trees are Self-Balanced Binary Search Trees. In AVL trees, the balancing factor of each node is either 0 or 1 or -1. Balance Factor of AVL Tree calculated as = Height of Left Sub-tree - Height of Right Sub-tree Construction of AVL Trees - Insertion Operation is performed to construct the AVL Tree. Inserting the element in the AVL tree is same as the insertion performed in BST. After insertion, check the balance factor of each node of the resulting tree. After the insertion, the balance factor of each node is either 0 or 1 or -1, then the tree is considered to be balanced, concludes the operation, and inserts the next element if any. After the insertion, the balance factor of at least one node is not 0 or 1 or -1, then the tree is considered to be imbalanced, perform the suitable rotation to balance the tree, and after the tree is balanced, insert the next element if any. Rotations used to Balance the AVL Tree - After inserting an element in the AVL tree, If a tree becomes imbalanced, then there exists one particular node in the tree by balancing which the entire tree becomes balanced automatically. To rebalance the tree, balance that particular node. To find that particular node: Traverse the path from the newly inserted node to the root node. Check the balance factor of each node that is encountered while traversing the path. The first encountered imbalanced node will be the node that needs to be balanced. To balance that node: Count three nodes in the direction of the leaf node. Then, use the concept of AVL Tree Rotations to rebalance the tree. LL Rotation - In LL rotation, every node moves one position to left from the current position. RR Rotation - In RR rotation, every node moves one position to right from the current position. LR Rotation - In LR rotation, at first, every node moves one position to the left and then one position to right from the current position. RL Rotation - In RL rotation, at first every node moves one position to right and then one position to left from the current position. Step-by-Step Construction of the AVL Tree for the given Sequence 21, 26, 30, 9, 4, 14, 28, 18,15,10, 2, 3, 7 - B-Tree, 2-3 Tree, B+Tree: Creation, Insertion & Deletion