{"id":320,"date":"2018-07-19T05:43:57","date_gmt":"2018-07-19T05:43:57","guid":{"rendered":"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/?post_type=chapter&p=320"},"modified":"2018-12-12T10:34:18","modified_gmt":"2018-12-12T10:34:18","slug":"balanced-binary-search-trees-and-avl-trees","status":"publish","type":"chapter","link":"https:\/\/ebooks.inflibnet.ac.in\/csp01\/chapter\/balanced-binary-search-trees-and-avl-trees\/","title":{"rendered":"Balanced Binary Search Trees and AVL Trees"},"content":{"raw":"
\"epgp<\/a>\r\n<\/span><\/div>\r\n
\r\n\r\n \r\n\r\n \r\n\r\n \r\n

Welcome to the e-PG Pathshala Lecture Series on Data Structures. We have understood the basic concept of an important ADT \u2013 the Tree ADT and also the special type of tree the binary search tree. In this module we will discuss one very important type of binary search tree that is the balanced binary search tree and one example of balanced binary search tree namely the AVL trees.<\/p>\r\n \r\n\r\nLearning Objectives<\/strong>\r\n\r\n \r\n\r\nThe learning objectives of the module are as follows:\r\n\r\n \r\n\r\n\u2022\u00a0 To understand the concept of Balanced Binary Search Trees\r\n\r\n\u2022\u00a0 To discuss the properties of AVL Trees\r\n\r\n\u2022\u00a0 To describe\u00a0 Single Rotation of AVL Trees\r\n\r\n\u2022\u00a0 To discuss the Double Rotation of AVL Trees\r\n\r\n \r\n\r\n23.1\u00a0 Introduction to Balanced Binary Search Trees<\/strong>\r\n\r\n \r\n

As a tree becomes more unbalanced, running time of the search operation increases from O(log n) to O(n) because as the tree gets more unbalanced the shape starts becoming a list. Binary Search Trees and important data structure used in many applications needing the search operation are fast if they\u2019re shallow or in other words the tree is a complete tree. The disadvantage of an unbalanced binary search tree is that its height can be as large as N-1. This essentially means that when one branch is much longer than the other, the time needed to perform insertion, deletion and search operations is much more.Now we need to define the concept of a \u201csort of\u201d complete tree where by \u201csort of\u201d we mean a binary search tree that is as balanced as possible. In other we want to keep the binary search tree balanced as nodes are added\/removed, so searching\/insertion remain efficient.<\/p>\r\n \r\n

A class of binary search trees is said to be balanced<\/strong>, if each of the three dictionary operations searching, inserting and deleting of keys for a tree with n<\/em> keys can always (in the worst case) be carried out in O<\/em>(log n<\/em>) steps.<\/p>\r\n \r\n\r\n23.1.1 Approaches to Balancing Trees<\/strong>\r\n\r\n \r\n

There are many approaches that can be adopted for balancing trees. The first and simplest method is we do not do balancing. However in this case we may end up\u00a0with some nodes being very deep. The other extreme of the simple policy is to main a strict balance that is the tree must always be balanced perfectly. The next approach is what is called pretty good balance where we allow a little out of balance. The fourth and final approach is adjusting the balance during access \u2013 the so called self-adjusting trees.<\/span><\/p>\r\n \r\n

23.2 Balanced Binary Search Trees<\/strong><\/p>\r\n \r\n

There are two basic kinds of balanced binary search trees. <\/span>Height balancedtrees<\/strong> wherewe ensure that the height of siblings are \u201capproximately the same\u201d. The other type is the <\/span>Weight-balancedtrees<\/strong> where we ensure that the number of descendants of sibling nodes are \u201capproximately the same\u201d. \u201cTree rotations\u201d are used to maintain balance on insert\/delete<\/span><\/p>\r\n\r\n<\/div>\r\n

\r\n\r\n \r\n

Now let us define the concept of balance - A binary tree<\/em> is balanced<\/em><\/strong>(here unless otherwise specified balanced implies height balanced) if the difference in height between any node\u2019s left and right subtree is \u00a3 1.<\/p>\r\n \r\n

balance = height(left subtree) - height(right subtree)<\/strong><\/p>\r\n \r\n

By convention the height of a \u201cnull\u201d subtree is assumed to be -1. If the balance is zero everywhere then the tree is said to be perfectly balanced. If the balance is small everywhere that is at each and every node then the tree is balanced enough to ensure operations will take time of the O(log n).<\/strong> This is because the maximum depth of the tree can be only 1.44 log n.<\/p>\r\n \r\n\r\n\"\"\r\n

Perfect Balance <\/strong>is said to occur if we want a complete tree after every operation. This means that the tree is full except possibly in the lower right. However maintaining perfect balance is expensive. For example (Figure 23.2), insert 2 in the tree on the left and then rebuild as a complete tree<\/p>\r\n \r\n\r\n\"\"\r\n\r\n23.2.1 Prevent the degeneration of the Binary Search Tree (BST) :<\/strong>\r\n\r\n<\/div>\r\n

\r\n\r\n \r\n

A BST can be set up to maintain balance during every update operation typically insertions and removals. Our objective is to keep the height of a binary search tree O(log N) . This allows us to achieve a worst-case runtime of O(log n) for searching, inserting and deleting.<\/p>\r\n \r\n\r\nTypes of BST which maintain the optimal performance are the following:\r\n