Implementation of balanced binary tree (AVL) for basic algorithm summarization

What is an AVL tree?

Before we talk about AVL trees, let’s recall that binary search trees (binary search trees) we studied earlier. In extreme cases, binary search trees can change from a binary tree to a linked list (inserting data in order), which can greatly reduce query efficiency.

Test the example of binary lookup trees in extreme cases from the previous section:

To solve this problem, we need to turn the binary lookup tree into a binary balanced tree by adding some properties and variations.

AVL tree (invented by G.M.Adelson-Velsky and Evgenii Landis, AVL is named after the initials of two people) is the earliest self-balanced binary search tree. In AVL tree, the maximum height difference of two subtrees corresponding to any node is less than 1.

In a binary tree, all nodes except leaf nodes have two children. The number of nodes reached the upper limit. Procedure All leaf nodes must be on the same layer. And the complete binary tree (the depth of the binary tree is H, except for the h layer, the number of nodes of all other layers (1 ~ H-1) reaches the maximum number, and all nodes of the h layer are continuously concentrated on the left) is naturally a balanced binary tree.

Note: A balanced binary tree is not necessarily a complete binary tree.

Balanced binary tree: the height difference between left and right subtrees of any node cannot exceed 1.

Therefore, AVL can be understood to take into account its balance on the basis of binary search tree. AVL is also called balanced binary search tree or balanced binary tree for short.

Equilibrium factor

Let’s review the height and depth of binary trees:

• Depth: Depth is calculated from the root node and represents the length of the unique path from the root to a node (the number of long sides of the path).

• Height: Indicates the length of the longest path from a node to a leaf node.

Here’s an example:

Now let’s see what the balance factor is: the difference between the height of the left subtree of a node and the height of the right subtree.

The following figure shows the equilibrium factors of an unbalanced binary tree and a balanced binary tree:

3. AVL initialization

3.1. Node definition

Define AVL tree node:

// TreeNode AVL node definition
type TreeNode struct {
  data  int       // Node data
  height  int       // Node height
  left  *TreeNode / / the left child
  right *TreeNode / / right child
}

// NewTreeNode builds a new node
func NewTreeNode(data int) *TreeNode {
  return &TreeNode{
    height: 0,
    left: nil,
    right: nil,
    data: data,
  }
}
Copy the code

Can be modified on the basis of binary search tree, here the focus on the implementation of insert and delete operations, some other operations are basically the same as binary tree operations.

type AVLTree struct {
  root *TreeNode
}

/ / Insert Insert
func (a *AVLTree) Insert(data int) {
    // TODO
}

/ / Delete the Delete
func (a *AVLTree) Delete(data int) {
    // TODO
}

Copy the code

Now we need to add some helper functions to help with insert and delete operations later.

3.2. Node height

We have height in the node, return 0 if the node is nil, otherwise return the height of the node.

// height Gets the height of the node
func (a *AVLTree) height(node *TreeNode) int {
  if node == nil {
    return - 1
  }
  return node.height
}
Copy the code

3.3. Calculate the balance factor

Balance factor: The difference between the height of the left subtree of a node and the height of the right subtree.

// balanceFactor gets the balanceFactor of a node
func (a *AVLTree) balanceFactor(node *TreeNode) int {
  if node == nil {
    return 0
  }
  return a.height(node.left) - a.height(node.right)
}

Copy the code

3.4. Determine whether the current binary tree is a balanced binary tree

And this is the method that we’ll use to adjust the node; After inserting data, determine whether the current binary tree is a balanced binary tree. If not, adjust it.

// IsBalanceTree checks whether it is a balanced binary tree
func (a *AVLTree) IsBalanceTree(a) bool {
  return a.isBalanceTree(a.root)
}
// isBalanceTree recursive judgment
func (a AVLTree) isBalanceTree(node *TreeNode) bool {
  // Node is nil and returns true
  if node == nil {
    return true
  }
  // Get the balance factor of the current node
  factor := a.balanceFactor(node)
  // If the equilibrium factor is greater than 1, the binary tree is not balanced
  if factor * factor > 1 {
    return false
  }
  // Determine the balance factor of left and right subtrees is greater than 1
  return a.isBalanceTree(node.left) && a.isBalanceTree(node.right)
}
Copy the code

3.5. Node increase

Here we first use the middle-order traversal of the binary search tree in the previous section to show the data. Then use recursion to achieve binary tree search tree insertion:

// Insert Inserts data
func (a *AVLTree) Insert(data int) {
  a.root = a.insert(a.root, data)
}

// Max the maximum value between x and y trees
func max(x, y int) int {
  if x > y {
    return x
  }
  return y
}

// insert built-in recursive functions to build binary lookup trees
func (a *AVLTree) insert(node *TreeNode, data int) *TreeNode {
  If the current node is nil, create a new node and return it
  if node == nil {
    return NewTreeNode(data)
  }
  // If the data of the current node is less than the data value
  if node.data < data {
    // Add from the right subtree
    node.right = a.insert(node.right, data)
  }
  // If the data of the current node is greater than the data value
  if node.data > data {
    // Add from the left subtree
    node.left = a.insert(node.left, data)
  }
  // Update the height
  node.height = 1 + max(a.height(node.left), a.height(node.right))
  // Calculate the balance factor of the current node
  balanceFactor := a.balanceFactor(node)

  fmt.Printf("Node :%d :%d => %d\n", node.data, node.height, balanceFactor)
  return node
}
Copy the code

3.6. Test

Here by generating 1000 random numbers, output constructed binary search tree.

func TestNewTreeNode(t *testing.T) {
  rand.Seed(time.Now().UnixNano())
  tree := AVLTree{}
  for i := 0; i < 1000; i++ {
    tree.Insert(rand.Intn(1000))
  }
  tree.InOrderTraverse()
}
Copy the code

Four. Insert maintenance balance

When a node is inserted, the binary tree balance will be broken, so it is necessary to maintain the binary tree lookup tree, so that the binary tree balance factor does not exceed 1.

In 3.5, only height was set and the balance factor calculated during the construction of the binary lookup tree. But it does not maintain balance for the whole tree after insertion.

// insert built-in recursive functions to build binary lookup trees
func (a *AVLTree) insert(node *TreeNode, data int) *TreeNode {
  If the current node is nil, create a new node and return it
  if node == nil {
    return NewTreeNode(data)
  }
  // If the data of the current node is less than the data value
  if node.data < data {
    // Add from the right subtree
    node.right = a.insert(node.right, data)
  }
  // If the data of the current node is greater than the data value
  if node.data > data {
    // Add from the left subtree
    node.left = a.insert(node.left, data)
  }
  // Update the height
  node.height = 1 + max(a.height(node.left), a.height(node.right))
  // Calculate the balance factor of the current node
  balanceFactor := a.balanceFactor(node)
  
  // TODO maintains balance
  
  return node
}
Copy the code

So here we need to talk about how to maintain equilibrium when there’s an imbalance after nodes are inserted.

Note: before the nodes are added, the binary tree lookup tree is a balanced binary tree; You have to increase it to break the equilibrium.

4.1. RR: Right rotation

When the number of increasing nodes increases all the way to the left subtree, the balance factor will be unbalanced when it exceeds 1, as shown in the figure below:

As can be seen from the figure, the right rotation is triggered by the condition that the balance factor of the current node is greater than 1 and the balance factor of the left subtree of the current node is greater than or equal to 0, which ensures that the binary tree is biased to the left. Now let’s see how we should rotate right:

From the figure above, it can be seen that: set the pointer of NODE B to D2 to node A, and then set the left pointer of node A to D2, which node B originally pointed to. Finally, we need to modify the height of node A and node B.

Code implementation:

// rightSpin right rotation
func (a *AVLTree) rightSpin(node *TreeNode) *TreeNode {
  // Save the address to which the pointer points
  lCh := node.left
  lRCh := lCh.right

  / / rotation
  lCh.right = node
  node.left = lRCh
  
  // Update the height of the node first (after the rotation, the node becomes a child of lCh) and then update the height of lCh
  node.height = max(a.height(node.left), a.height(node.right)) + 1
  lCh.height = max(a.height(lCh.left), a.height(lCh.right)) + 1
  
  // Return the rotated root
  return lCh
}
Copy the code

4.2. LL: Turn left

Left rotation and right rotation are inverse operations. The nodes added are always shifted to the right. If the balance factor exceeds -1, the current binary tree is not a balanced binary tree.

It can be seen from the figure that the conditions for triggering the left rotation are: the balance factor of the current node is less than -1 and the balance factor of the right subtree of the current node is less than or equal to 0, which can ensure that the binary tree is biased to the right. Now let’s see how we should rotate left:

The implementation is the opposite of the right rotation, the code implementation:

// leftSpin
func (a *AVLTree) leftSpin(node *TreeNode) *TreeNode {
  
  // Save the address to which the pointer points
  rCh := node.right
  rLCh := rCh.left
  
  / / options
  rCh.left = node
  node.right = rLCh
  
  // Update the height
  node.height = max(a.height(node.left), a.height(node.right)) + 1
  rCh.height = max(a.height(rCh.left), a.height(rCh.right)) + 1
  
  // Return the rotated root
  return rCh
}
Copy the code

4.3. LR: Left rotation; Right rotation

This situation corresponds to the following figure, which shows that adding nodes to the right subtree of the left child of a node causes an imbalance.

To change the unbalanced state, first turn left to the RR shape we are familiar with, and then turn right according to the RR shape.

4.4. RL: Right rotation; Left rotation

This situation corresponds to the following figure, which shows that adding nodes to the left subtree of the right child of a node causes an imbalance.

To change the unbalanced state, first turn right to the familiar LL type, and then turn left according to LL type.

4.5. Improve the insertion method

Integrate the above four cases into the maintenance balance part of backtracking; This allows you to turn the binary lookup tree into an AVL tree.

Firstly, the maintenance balance is extracted into a method:

// Maintain balance
func (a *AVLTree) maintain(node *TreeNode) *TreeNode {
  // Calculate the balance factor of the current node
  balanceFactor := a.balanceFactor(node)

  / / right turn
  if balanceFactor > 1 && a.balanceFactor(node.left) >= 0 {
    return a.rightSpin(node)
  }
  / / left rotation
  if balanceFactor < - 1 && a.balanceFactor(node.right) <= 0 {
    return a.leftSpin(node)
  }

  // LR
  if balanceFactor > 1 && a.balanceFactor(node.left) < 0 {
    node.left = a.leftSpin(node.left)
    return a.rightSpin(node)
  }

  // RL
  if balanceFactor < - 1 && a.balanceFactor(node.right) > 0 {
    node.right = a.rightSpin(node.right)
    return a.leftSpin(node)
  }

  return node
}
Copy the code

Implementation of the insert method:

// Insert Inserts data
func (a *AVLTree) Insert(data int) {
  a.root = a.insert(a.root, data)
}

// insert Recursively inserts data
func (a *AVLTree) insert(node *TreeNode, data int) *TreeNode {
  If the current node is nil, create a new node and return it
  if node == nil {
    return NewTreeNode(data)
  }
  // If the data of the current node is less than the data value
  if node.data < data {
    // Add from the right subtree
    node.right = a.insert(node.right, data)
  }
  // If the data of the current node is greater than the data value
  if node.data > data {
    // Add from the left subtree
    node.left = a.insert(node.left, data)
  }
  // Update the height
  node.height = 1 + max(a.height(node.left), a.height(node.right))
  
  // Maintain balance
  return a.maintain(node)
}
Copy the code

Finally, test the extreme case (write node data sequentially) :

func TestNewTreeNode(t *testing.T) {
  tree := AVLTree{}
  for i := 0; i < 10000; i++ {
    tree.Insert(i)
  }
  t.Log(tree.IsBalanceTree())  // true
}
Copy the code

It is clear that extreme cases are not reverted to linked lists after adjustment.

V. Node deletion

The deletion of nodes can be modified on the basis of the original binary search tree. The current binary balanced tree was a binary balanced tree before deletion. After deletion, it may no longer be a balanced binary tree and needs to be rebalanced.

So rebalancing is just going to take the path of the deleted node and rotate it backwards to rebalance it.

// Remove Remove a node
func (a *AVLTree) Remove(data int) {
  a.root = a.remove(a.root, data)
}

// remove recursively remove
func (a *AVLTree) remove(node *TreeNode, data int) *TreeNode {

  // If current node is nil
  if node == nil {
    return nil
  }

  var newNode *TreeNode

  if data < node.data {
    node.left = a.remove(node.left, data)
    newNode = node
  } else if data > node.data {
    node.right = a.remove(node.right, data)
    newNode = node
  } else {
    // Data is the same as the data of the current node

    // The left subtree of the node to be deleted is empty
    if node.left == nil {
      right := node.right
      node.right = nil
      newNode = right
    } else if node.right == nil {
      // The right subtree of the node to be deleted is empty
      left := node.left
      node.left = nil
      newNode = left
    } else {
      // The left and right subtrees of the node to be deleted are not empty

      // Find the smallest node in the right subtree of the node to be deleted
      minMode := a.min(node.right)
      // Remove the smallest node in the right subtree of the node to be deleted
      minMode.right = a.remove(node.right, minMode.data)
      minMode.left = node.left

      // Set the left and right subtrees of the node to be deleted to nil
      node.left = nil
      node.right = nil

      // Return the new node
      newNode = minMode
    }

  }

  if newNode == nil {
    return nil
  }
  // Update the height
  newNode.height = 1 + max(a.height(newNode.left), a.height(newNode.right))
  // Maintain balance
  return a.maintain(newNode)
}
Copy the code