This is the fourth day of my participation in the Gwen Challenge.More article challenges

Hello, Aribbard, four more!! The price of this article is a handful of hair, this hair xiaobian first fall for respect!

Preface:

In data structure, tree and graph are symbolic products of data structure. The binary tree we talk about today is a useful compromise scheme. Arrays are easy to search with subscripts, but deleting or inserting certain elements is more difficult. Linked lists, by contrast, delete and insert elements quickly, but lookup is slow. Binary trees have the benefits of linked lists as well as arrays. It is useful when dealing with large amounts of dynamic data. In some scenarios, it’s more convenient to use trees because trees are non-linear, they can represent one-to-many, like directory structures for files;

We all know that for binary search tree and binary tree traversal, but its search efficiency is not stable will appear “inclined tree”, this time the binary balance tree came into being, the binary balance tree has more uses, compared to search is more stable; You can imagine Mysql’s search engines: MyISAM and InnoDB;

Balanced binary trees

Balanced binary tree conditions:

The depth difference between the left and right subtrees of each node in a binary tree is no more than 1.

Balanced binary tree how to achieve self-balance:

However, in the case of “inclined tree”, balanced binary tree will maintain the balance of the tree through rotation, which can be divided into the following four types:

The following picture: A, B, C, E, F represents the node of the tree, the number next to the node represents the depth of the subtree around the current node, the picture is relatively sloppy, to give you A detailed introduction, you can follow my train of thought to walk again, I believe that you can understand

  1. LL (right-handed) : Adds new nodes to the left child of the left subtree

From left to right

  1. FIG. 1 The current tree structure is balanced. The maximum depth of left and right subtrees of each node is 1, which meets the condition of balanced tree
  2. Figure 2 toThe left child of the left treeAdd a new nodeFAt this point, we can see that the depth of the left and right subtrees of our node is 2, which does not satisfy the condition of equilibrium tree. What can we do? Now that our focus is out, let’s move on to 👇
  3. Figure 3 shows our balanced binary tree after dextral rotation, where we can see the original child nodesBRotate it to the right to become the heel node,AThe node also rotates to the right to become a child of node B,The right child of node B is rotated to the right to become the left child of node AWhen the rotation is completed, it can be seen that the depth of the left and right subtrees of each node is the maximumC nodeIs 1, satisfying the condition and achieving self-equilibrium;

I found a vivid right-handed GIF on the Internet for you to look at and understand

2. RR (left-handed) : Add a new node to the right child of the right subtree

From left to right

  1. FIG. 1 The current tree structure is balanced. The maximum depth of left and right subtrees of each node is 1, which meets the condition of balanced tree
  2. Figure 2 toThe right child node of the right treeAdd a new nodeFAt this time, it can be seen that the depth of the left and right subtrees of our node is 2, and the condition of balanced tree is not satisfied at this time.
  3. Figure 3 is the binary tree that we achieved balance after left-handed rotation. Just to keep in mind, you can think about it for yourself. By doing so, you can write in the comments section. Ha ha ha ~ belch ~ let everyone experience the sinister of the society 😁

LR type (first left-handed (unbalanced subtree) then right-handed) : add new nodes on the right child of the left subtree

From left to right

  1. FIG. 1 The current tree structure is balanced. The maximum depth of left and right subtrees of each node is 1, which meets the condition of balanced tree
  2. Figure 2. Add a new node to the right child node in the left treeFAt this time, it can be seen that the depth of the left and right subtrees of our node is 2, and the condition of balanced tree is not satisfied at this time.
  3. Figure 3 is the one circled in our diagramLocal tree structureAfter left rotation, it forms an LL – shaped tree structure;
  4. Figure 4 shows the LL-shaped tree structure that we obtained by going through the initial left rotation after a right rotation (same as the first example above), thus achieving self-equilibrium;

4. RL (right-handed (unbalanced subtree) then left-handed) : add new nodes to the left child of the right subtree

From left to right

  1. FIG. 1 The current tree structure is balanced. The maximum depth of left and right subtrees of each node is 1, which meets the condition of balanced tree
  2. Figure 2 adds a new node to the left child node in the right treeFAt this time, it can be seen that the depth of the left and right subtrees of our node is 2, and the condition of balanced tree is not satisfied at this time.
  3. Figure 3 is the one circled in our diagramLocal tree structureAfter the dextral form an LL tree structure;
  4. Figure 4 shows the LL-shaped tree structure that we obtained through initial dextral rotation after a left rotation (as in the second example above), thus achieving self-equilibrium;

Of course, AVL has other operations, such as delete, besides insertion. Delete post balance) interested can study together

AVL tree:

AVL tree is a binary search tree with balance condition, and the height of the left and right subtrees is no more than 1. AVL tree is a strict balanced binary tree, and the balance condition must be satisfied (the height difference between the left and right subtrees of all nodes is no more than 1). So it’s also called a highly balanced tree.

Ok! This is the end of the article. It takes time for AVL to understand. Of course, there may be some omissions in the AVL written by the author, so I hope it can be helpful for you to avoid detours.

There is space in the details, and neatness makes for great code