Shulou(Shulou.com)06/02 Report--

This article mainly introduces "how to understand and master the AVL tree of Java". In the daily operation, I believe that many people have doubts about how to understand and master the AVL tree of Java. The editor consulted all kinds of materials and sorted out simple and easy-to-use operation methods. I hope it will be helpful to answer the doubts of "how to understand and master the AVL tree of Java". Next, please follow the editor to study!

1. Summary

In the last article, we introduced the algorithm and code practice of binary tree in detail. we know that different morphological structure of binary tree will have a great impact on query efficiency, especially when the morphological structure of the tree becomes a chain structure. the efficiency of querying the last element is extremely low, how to solve this problem?

The key is how to minimize the depth of the tree, so as to improve the query efficiency, it is based on this point, the balanced binary search tree appeared!

Balanced binary search tree, invented by two great gods Adel'son-Vel'skii and Landis, also known as AVL tree, comes from the initials of the two great gods and has the following features:

Its left subtree and right subtree are balanced binary trees.

And the absolute value (balance factor) of the difference between the depth of the left subtree and the right subtree does not exceed 1.

To put it simply, in order to ensure balance, the height difference between the left subtree and the right subtree of the current node does not exceed 1!

No more nonsense, straight to the topic, the idea of the algorithm is as follows!

Second, the idea of algorithm

The idea of balancing the binary search tree is the same as the binary tree, each query is divided in half, only a part of the query, in order to provide efficiency, insert, delete is the same, the biggest difference: after each insert or delete, need to calculate the node height, and then adjust as needed!

How to adjust it? The main methods are: left rotation, right rotation!

Let's analyze the scene adjustments of insertion and deletion respectively.

2.1. Insert the scene

Let's analyze the inserted scenario, as follows:

Scene one

When we insert on the left or right side of 40, that is, the left side of 50, we only need to rotate right around 80 to achieve a tree height difference of no more than 1!

Scene two

When we insert on the left or right of 60, that is, the right of 50, we need to rotate twice, first around 50 once to the left, and then around 80 once to the right, so that the height difference of the tree is less than 1!

Scene 3

When we insert on the left or right side of 120, that is, the right side of 90, we only need to rotate left around 80 to achieve a tree height difference of less than 1!

Scene 4

When we insert on the left or right side of 85, that is, the left side of 90, we need to rotate twice, first around 90 right, and then around 80 left, so that the height difference of the tree is less than 1!

Summary

For the insertion operation, there are actually only these four types of insertions, namely: single left rotation, single right rotation, left rotation-right rotation, right rotation-left rotation, which are summarized as follows:

When the insertion node is in the left subtree of the left node of the node that needs to be rotated, you only need to rotate it right.

When the insertion node is located in the right subtree of the left node of the node that needs to be rotated, left-right rotation is required.

When the insertion node is in the right subtree of the right node of the node that needs to be rotated, you only need to rotate to the left.

When the insertion node is in the left subtree of the right node of the node that needs to be rotated, right rotation-left rotation is required.

2.2. Delete the scene

Next, let's analyze the delete scenario!

In fact, the idea of deleting a scene is the same as that of a binary tree, except that it needs to be adjusted. If the deleted node is located in the tree, you need to determine whether the height difference of the node is greater than 1. If it is greater than 1, rotate left or right!

Scene one

When the deleted node has only the left subtree, just transfer the left subtree to the upper layer!

Scene two

When the deleted node has only the right subtree, just transfer the right subtree to the upper layer!

Scene 3

When the deleted node has left and right subtrees, because the right subtree at the end of the left subtree of the current node or the right subtree of the right subtree of the current node is closest to the current node, find any one of them, and then replace its contents and remove the most terminal node.

Summary

The third scenario is a little more complicated, but it is basically such a routine. Unlike a binary tree, you need to judge the height of the tree after deletion and adjust more than 1, similar to the left and right rotation operations inserted above!

Third, code practice

Next, let's define the entity structure of the tree at the code level, as follows:

1public class AVLNode {2 3 / * * Node keywords * / 4 E key; 56 / * current node tree height * / 7 int height; 8 9 / * * left child node of current node * / 10 AVLNode lChild = null; 11 12 / * * right child node of current node * / 13 AVLNode rChild = null; 14 15 public AVLNode (E key) {16 this.key = key 17} 18 19 @ Override 20 public String toString () {21 return "AVLNode {" + 22 "key=" + key + 23 ", height=" + height + 24 ", lChild=" + lChild + 25 ", rChild=" + rChild + 26'}'; 27} 28}

We create an algorithm class AVLSolution, which is fully implemented as follows:

1public class AVLSolution {2 3 / * * define root node * / 4 public AVLNode root = null; 56 / * * 7 * insert 8 * @ param key 9 * / 10 public void insert (E key) {11 System.out.println ("insert [" + key + "]:"); 12 root = insertAVL (key,root) 13} 14 15 private AVLNode insertAVL (E key, AVLNode node) {16 if (node = = null) {17 return new AVLNode (key); 18} 19 / / left subtree search 20 if (key.compareTo (node.key))

< 0){ 21 //当前节点左子树不为空,继续递归向下搜索 22 node.lChild = insertAVL(key,node.lChild); 23 //出现不平衡，只会是左子树比右子树高，大于1的时候，就进行调整 24 if(getHeight(node.lChild) - getHeight(node.rChild) == 2){ 25 if(key.compareTo(node.lChild.key) < 0){ 26 //如果插入的节点位于当前节点的左节点的左子树，进行单次右旋转 27 node = rotateRight(node); 28 }else{ 29 //如果插入的节点位于当前节点的左节点的右子树，先左旋转再右旋转 30 node = rotateLeftRight(node); 31 } 32 } 33 }else if(key.compareTo(node.key) >

0) {34 / / the right subtree of the current node is not empty, continue to search down recursively for 35 node.rChild = insertAVL (key,node.rChild) 36 / / when there is an imbalance, only if the right subtree is taller than the left subtree, when it is greater than 1, adjust 37 if (getHeight (node.rChild)-getHeight (node.lChild) = = 2) {38 if (key.compareTo (node.rChild.key))

< 0){ 39 //如果插入的节点位于当前节点的右节点的左子树，先右旋转再左旋转 40 node = rotateRightLeft(node); 41 }else{ 42 //如果插入的节点位于当前节点的右节点的右子树，进行单次左旋转 43 node = rotateLeft(node); 44 } 45 } 46 } else{ 47 //key已经存在，直接返回 48 } 49 //因为节点插入，树高发生变化，更新节点高度 50 node.height = updateHeight(node); 51 return node; 52 } 53 54 /** 55 * 删除 56 * @param key 57 */ 58 public void delete(E key){ 59 root = deleteAVL(key,root); 60 } 61 62 private AVLNode deleteAVL(E key, AVLNode node){ 63 if(node == null){ 64 return null; 65 } 66 if(key.compareTo(node.key) < 0){ 67 //左子树查找 68 node.lChild = deleteAVL(key,node.lChild); 69 //可能会出现，右子树比左子树高2 70 if (getHeight(node.rChild) - getHeight(node.lChild) == 2){ 71 node = rotateLeft(node); 72 } 73 } else if(key.compareTo(node.key) >

0) {74 / / right subtree lookup 75 node.rChild = deleteAVL (key, node.rChild); 76 / may appear. The left subtree is 2 77 if higher than the right subtree (getHeight (node.lChild)-getHeight (node.rChild) = 2) {78 node = rotateRight (node) 79} 80} else {81 / / find the target element and delete it in three cases 82 / / 1. The current node has no left subtree, so return to the right subtree 83 / / 2 of the current node directly. The current node does not have a right subtree, so return directly to the current node's right subtree 84 / / 3. When the current node has a left subtree or a right subtree, find the extreme left subtree of the right subtree of the current node, replace and remove 85 if (node.lChild = = null) {86 return node.rChild; 87} 88 if (node.rChild = = null) {89 return node.lChild 90} 91 / / find the left subtree at the end of the right subtree of the current node, that is, the smallest node of the right subtree 92 AVLNode minLChild = searchDeleteMin (node.rChild); 93 / delete the smallest node, if the height changes, adjust 94 minLChild.rChild = deleteMin (node.rChild); 95 minLChild.lChild = node.lChild / / transfer the left subtree of the current node to the smallest node 96 97 node = minLChild;// overwrites the current node 98 / / because the height of the right subtree becomes lower, you may need to adjust 99 if (getHeight (node.lChild)-getHeight (node.rChild) = = 2) {100 node = rotateRight (node) 1010 node.height = updateHeight (node); 104 return node; 105} 106107 / * * 108* search for 109@ param key 110 * @ return 111112public AVLNode search (E key) {113return searchAVL (key, root); 114115116private AVLNode searchAVL (E key, AVLNode node) {117if (node = null) {118return null Left subtree search 121 if (key.compareTo (node.key))

< 0){ 122 return searchAVL(key, node.lChild); 123 }else if(key.compareTo(node.key) >

0) {124 return searchAVL (key, node.rChild); 125} else {126 / / key already exists. Direct return of 127return node 128129} 130131 / * * 132* find the elements to be deleted 133134134@ return 135* / 136private AVLNode searchDeleteMin (AVLNode node) {137if (node = = null) {138return null; 139} 140while (node.lChild! = null) {141node = node.lChild; 142143return node 144,145146 / * * 147* Delete element 148@ param node 149149151private AVLNode deleteMin (AVLNode node) {152if (node = = null) {155return null; 155155if (node.lChild = = null) {156return node.rChild Remove the smallest node 159 node.lChild = deleteMin (node.lChild); 160 / / remove the left node to determine whether the balance height is broken 161if (getHeight (node.rChild)-getHeight (node.lChild) = = 2) {162 / / adjust 166node = rotateLeft (node); 16165return node 166167} 168169 / * * 170* single left rotation 171st * @ param node 172* @ return 173* / 174private AVLNode rotateLeft (AVLNode node) {175System.out.println ("Node:" + node.key + ", single left rotation"); 176AVLNode x = node.rChild;// to get the right node of the rotating node 177node.rChild = x.lChild / transfer the left node of the right node of the rotation node, x.lChild = node;// as the right subtree of the rotation node 179 180 / update adjust the height of the rotation node (first adjust the rotation node node) 181 node.height = updateHeight (node); 182 x.height = updateHeight (x); 183 return x 185186 / * * 187* single right rotation 188 * @ return 189 * / 190 private AVLNode rotateRight (AVLNode node) {191 System.out.println ("Node:" + node.key + ", single right rotation"); 192 AVLNode x = node.lChild;// to get the left node of the rotation node 193 node.lChild = x.rChild / / transfer the right node of the left node of the rotation node. 194 x.rChild = node;// as the left subtree of the rotation node updates the height of the rotation node as the right subtree of the left subtree of the rotation node (first adjust the rotation node node) 197 node.height = updateHeight (node); 198 x.height = updateHeight (x); 199 return x Left-right rotation 204@ param node 205* @ return 206* / 207private AVLNode rotateLeftRight (AVLNode node) {208System.out.println ("Node:" + node.key + ", left-right rotation"); 209 / first rotate the left node of the current node 210node.lChild = rotateLeft (node.lChild) The current node is rotated by 217 * @ param node 219 * / 220private AVLNode rotateRightLeft (AVLNode node) {221 System.out.println ("Node:" + node.key + ", right rotation-left rotation"). 223 node.rChild = rotateRight (node.rChild); 224 return rotateLeft (node); 225 226} 227 228 / * * 229 * to get the height of the node. If empty, it is equal to-1230 * @ param node 231 * @ return 231 * / 233 private int getHeight (AVLNode node) {234 return node! = null? Node.height:-1; 235} 236 237 / * * 238 * Update node height 239 * @ param node 240 * @ return 241 * / 242 private int updateHeight (AVLNode node) {243 / / compare the height of the left subtree and the right subtree of the current node to obtain the node height of 244 return Math.max (getHeight (node.lChild), getHeight (node.rChild)) + 1 Preorder traversal 249 * @ param node 250 * / 251 public void frontTreeIterator (AVLNode node) {252 if (node! = null) {253 System.out.println ("key:" + node.key); 254 frontTreeIterator (node.lChild); / / traverse the left subtree of the current node 255 frontTreeIterator (node.rChild) / / traversing the right subtree of the current node 261 * @ param node 262 * / 263 public void middleTreeIterator (AVLNode node) {264 if (node! = null) {265 middleTreeIterator (node.lChild); / / traversing the left subtree of the current node 266 System.out.println ("key:" + node.key); 267 middleTreeIterator (node.rChild) / / traversing the right subtree of the current node 268} 269} 270271 / * * 272 * traversing 273 * @ param node 274 * / 275 public void backTreeIterator (AVLNode node) {276 if (node! = null) {277 backTreeIterator (node.lChild); / / traversing the left subtree of the current node 278 backTreeIterator (node.rChild) / / traverse the right subtree of the current node 279 System.out.println ("key:" + node.key)

Test the code as follows:

1public class AVLClient {2 3 public static void main (String [] args) {4 / / create an Integer type data structure 5 AVLSolution avlTree = new AVLSolution (); 6 7 / insert node 8 System.out.println ("= insert element ="); 9 avlTree.insert (new Integer (100)); 10 avlTree.insert (new Integer (85)); 11 avlTree.insert (new Integer (120)) 12 avlTree.insert (new Integer (60)); 13 avlTree.insert (new Integer (90)); 14 avlTree.insert (new Integer (80)); 15 avlTree.insert (new Integer (130)); 16 System.out.println ("= medium order ergodic element ="); 17 18 / / medium order traversal 19 avlTree.middleTreeIterator (avlTree.root); 20 System.out.println ("= find elements with key =") 21 22 / / query node 23 AVLNode searchResult = avlTree.search; 24 System.out.println ("find results:" + searchResult); 25 System.out.println ("= delete element with key 90 ="); 26 27 / / delete node 28 avlTree.delete (90); 29 System.out.println ("= traversal element in the middle order again =") 30 31 / / traversing 32 avlTree.middleTreeIterator (avlTree.root); 33} 34}

The output is as follows:

At this point, the study on "how to understand and master the AVL tree of Java" is over. I hope to be able to solve your doubts. The collocation of theory and practice can better help you learn, go and try it! If you want to continue to learn more related knowledge, please continue to follow the website, the editor will continue to work hard to bring you more practical articles!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.