AVL TREE - DATA STRUCTURES

[Music] hello friends welcome back to our channel so in the previous session we have seen the different operations that can be performed on binary search tree so from today's session will start the another type of binary tree that is AV editing right so this is also a type of binary tree that means it's a type of binary tree that means it satisfies the property of a binary tree that means every node should contain a close to two children that means every node in this tree should have at least a 0 or a 1 or 2 chainz not more than 2 change right there is a property of violently or we can simply we can also say that it's a variant of binary search III my research tree so it should weigh the property of binary search tree also that makes all the elements which are on the left subtree should be less than the hoop phone and all the elements of right subtree should be less greater than than so it should go better the property of binary search tree nodes and this is a self of balancing by research self balancing my research self oberlin see by this entry which was invented by Harrison brusky and Elena's so these three persons invented the cell balancing by literally so that that's why it was named as a BLT so where is this self balancing what is it self management so self balancing means here the balancing of heights of left sub-tree and white circles so balancing heights of left and right subtrees so balancing them left and right centers so this is measured in terms of dancing factor balancing factor right so balancing factor so what is this balancing factor and how to calculate this balancing factor and if this tree obeys this binary search tree always this balancing factor then only we can call that as it EVLT so this balancing factor is nothing but hide off left subtree - hide off right sudden right so that means the difference of height of left sub-tree and right center so that is that use the balancing factor which can be either 0 1 or minus 1 it is 0 1 4 minus 1 so that means we can see every node should satisfy this balancing factor that means every node must have the well balancing factor and either 0 or 1 or minus 1 right so we hope you understand this AVL tree should satisfy the binary sensitive property along with that binary search tree property it also satisfies this balancing factor that means every node so contain the balancing factor either 0 1 or minus 1 what is the 0 1 minus 1 how to calculate this balancing factor there is a difference between the height of left subtree and the right sub right so first of all height how to calculate the height it's a 1 spot from these two from leaf node to that node so from where we are finding the height so the leaf node to that node the longest path gives the height of a node so height of a sub tree - a height of the right subtree then we'll see an example so don't get confused so it should satisfy the binary search it a property right so it should satisfy binary tree and also it should satisfy that self balancing that puts balancing factor every node should have the balancing factor at their 0 1 or minus 1 if any node is having other than these 3 values either 0 1 or minus 1 that implies that is not an AVL tree that doesn't call it as it we agree right so let us see an example and let us see how do we get a 0 1 or a minus 1 let us take an example for yeah let us take this example first see let us take this example first so if you consider if you consider this example we know that this one is the left - subtree and this one is a right sample right no balancing factor what is the balancing factor see balancing factor first binary search tree some binary search tree means all the elements which are on the left subtree are less than the root node all the elements which are on the right subtree are greater than the so excited binary search tree then coming to this balancing factor what is the balancing factor for 80 so that is nothing but kind of left subtree - height of my sudden so what is the height of left subtree - - what's a better right subtree 1 which is equal to 1 which is equal to 1 right so it is in the 0 1 1 - 1 so it satisfies the condition of aviary so this is called again right so if this we have to serve 3 is having fewer Allah means 30 and some 45 and again it is having 20 and the 30 final now what's the result so what is the left subtree of this 80 so 1 2 3 4 hi this 4 1 2 3 & 4 hi teaspoon try accepted one will get 3 which is not equal to 0 1 or minus 1 so this is not a every l3 not an AVL tree so because every Lord should have the balancing factor is a zero one or minus one which violates this condition okay so that's why this is not a ability see according to the relevancy factor so we have to calculate this balancing factor for every node every node right so if this dancing factor is a minus one if this balancing factor is a minus one this tree is called as right heavy area tree right heavy immunity or heavy light immunity or heavy height in right if it is a zero it is called balancing again it is one that we call it as heavy left area it is quite a heavy left a theater right so this is how we can consider so which type of AVL tree it is based upon the balancing factor right so we are supposed to find this balancing factor for every node of it binary search tree if it satisfies then we can call it as a where is it so let us take this example see if you find the balancing factor for this one the NC factor for this one height of left 3 that means it 2 minus 1 which is 1 so what is one heavy left on left heavy heavy left arm left leg that's the heavy tree right so heavy right now right banned city right so based upon this balancing factor value we can have whether it is a left TV or right there we or a balance it so this is we are getting the balancing factor will read one so we can call it as it left the heavy balancing T because the height of left is greater than the height of right height of left is greater than height of right so if you avoid this one if you consider this 190 in 110 C in this the balancing factor is height or I left sub-tree head of left deceptive means 1 - hi - fried circuitry - which is not equal to which is equal to minus 1 so it is within the given balancing factors so if it is a minus 1 it is called as a right heavy tree right heavy tree because here we can observe that the height of limb is less than fight of right or height of right is greater than a top left so we can get the minus 1 so we can say it has a right heavy tree or heavy right and if you have this one see 40 60 so if you consider this one this is also satisfies the binary search should be called all the elements on the left subtree then the root element of the all the elements of which are greater than the root element or 1 right subtree so it satisfies the binary search tree property and Emily this balance factor say if you observe this one so balancing factor for every road every node we can check for every node right so here the right subtree height is 2 and left subtree height is 2 which is equal to 0 which is equal to 0 that means the height of left subtree is equal to height of right subtree so if it is you know we count as a battle secretary or a balance of three a very balanced in a be empty so this is how we can find whether the given three is a binary search tree or AVL tree so every three is also one type of binary search tree with a balancing factor so that's why we can call it as a AVL tree can be called as self-balancing binary search tree and operations can be performed on this one those are insertion and deletion so operations are insertion and deletion so these two operations that can be performed on these AVL things so while after inserting on are after deleting that should not deviate this balancing factor so that means if you insert an element into this AVL tree that may disturb the property of a BLT that may disturb the balancing factor right so we have to take care while inserting an element so that the balancing factor should not change that means the property of a will eventually should not violate right so that should be taken care by inserting an element or a deleting an element from event right so we'll see these operations in the next session so hope you understood this one so AVL tree is also a variant of binary search tree that we call it as a self-balancing binary tree binary search tree that means here we have to find the balancing factor which which is nothing but the height the difference between the height of a left subtree and the right subtree so the values may be minus 1 0 or 1 so if the height of height of left subtree is a greater than height of right subtree will get a value of 1 then that will call it as it left a heavy t and if if the height of right subtree is greater than height of left subtree we get a minus 1 and we will call it as a white-headed thing and hit the height of right subtree and height of left subtree both are equal then we get a zero value and that is for a balancing or a balancing kvl thing so this is how we can find whether the given given three is a binary search tree tree or an AVL tree so hope you understood this property of AVL tree right so we have to find this balancing factor for every node in the tree so every node in the tree should satisfy this balancing factor so that means every node in the tree should have either minus 1 0 or 1 as a balancing factor right so hope you understood this one and if you are having any doubts regarding this introduction so feel free to post your talks in the comment section so that definitely I will try to clarify all your doubts and there are you if you really understood my sessions like my sessions share processions with your friends and don't forget to subscribe to our channel thanks for watching and keep following our channel thank you very much

Channel: Sundeep Saradhi Kanthety

Views: 32,555

Keywords: sundeep, saradhi, kanthety, data structures, lists, trees, primitive, non primitive, linear, non linear, linked lists, ds fundamentals, ds basics, nodes, parent, child, leaf node, sub tree, root node, tree terminology, TREES IN DATA STRUCTURES, binary trees, binary search trees, BST, BST BASICS, BST CONSTRUCTION, binary search, right subtree, left subtree, AVL TREE, BALANCING FACTOR, SELF BALANCING, HEIGHT OF LEFT SUBTREE, HEIGHT OF RIGHT SUBTREE, HEIGHT DIFFERENCE

Id: N9EwTeMJl5s

Length: 17min 6sec (1026 seconds)

Published: Thu Aug 01 2019