We start with the following tree. After performing the single rotation we get the following. If tree C has height h , the tree is not height-balanced.
We need to do something else. Look again at rebalancing a tree, and assume that a single rotation does not fix it. Then the heights must be as follows. Let's expand it one more level. A double rotation lifts z up between x and y , yielding the following tree. There is a similar double-rotation for the case where the left subtree is 2 higher than the right subtree. See if you can see what it should be. If a node is already height-balanced, you should not do any kind of rotation on it.
Leave it alone. But if it is not height-balanced, decide whether a single rotation or a double rotation is appropriate as follows. Starting at the root, take two steps downward, each time moving into the higher subtree. So a rotation is called for. Imagine taking two steps toward the higher subtree.
So, starting at 20, step to 30 and then to If the two steps are in the same direction two right steps or two left steps , as they are in this example, we call it a zig-zig , and a single rotation is called for. Performing the single rotation yields the following tree. There is only one edge between the node n2 and n4 and two edges between the nodes n7 and n2; therefore, node n7 is the farthest from the root node.
The height of the left subtree is 2. The right subtree contains only one leaf node, i. The difference between the heights of the left subtree and right subtree is 1. Since we got the value 1 so we can say that the above tree is a height-balanced tree. This process of calculating the difference between the heights should be performed for each node like n2, n3, n4, n5, n6 and n7. When we process each node, then we will find that the value of k is not more than 1, so we can say that the above tree is a balanced binary tree.
In the above tree, n6, n4, and n3 are the leaf nodes, where n6 is the farthest node from the root node.
Three edges exist between the root node and the leaf node; therefore, the height of the above tree is 3. When we consider n1 as the root node, then the left subtree contains the nodes n2, n4, n5, and n6, while subtree contains the node n3. In the left subtree, n2 is a root node, and n4 and n6 are leaf nodes. Among n4 and n6 nodes, n6 is the farthest node from its root node, and n6 has two edges; therefore, the height of the left subtree is 2.
The right subtree does have any child on its left and right; therefore, the height of the right subtree is 0. Since the height of the left subtree is 2 and the right subtree is 0, so the difference between the height of the left subtree and right subtree is 2.
According to the definition, the difference between the height of left sub tree and the right subtree must not be greater than 1. In this case, the difference comes to be 2, which is greater than 1; therefore, the above binary tree is an unbalanced binary search tree. The above tree is a binary search tree because all the left subtree nodes are smaller than its parent node and all the right subtree nodes are greater than its parent node.
Suppose we want to want to find the value 79 in the above tree. First, we compare the value of node n1 with 79; since the value of 79 is not equal to 35 and it is greater than 35 so we move to the node n3, i.
Since the value 79 is not equal to 48 and 79 is greater than 48, so we move to the right child of The value of the right child of node 48 is 79 which is equal to the value to be searched. The number of hops required to search an element 79 is 2 and the maximum number of hops required to search any element is 2. This means that in an AVL tree the difference between left subtree and right subtree height is at most one. AVL tree is a self-balancing binary search tree. In an AVL tree if the difference between left and right subtrees is greater than 1 then it performs one of the following 4 rotations to rebalance itself :.
We will need a function that can calculate the height of the tree. One way to do this is to write a separate function for calculating the height and call it every time height is needed. This is going to be computationally inefficient. Dynamic Programming. Explore Python Examples. Popular Examples Add two numbers. Check prime number. Find the factorial of a number. Print the Fibonacci sequence.
Check leap year.
0コメント