preface

  • This paper mainly discusses the realization process of balanced binary tree, for the principle of please browse other materials to learn

1. Introduction to balanced binary trees

1.1 What is a balanced binary tree

So the first thing we need to know about balanced binary trees is what is a tree structure

  • The tree structure

A tree is a data structure that consists of a set of n (n>=1) finite nodes with a hierarchical relationship.

Definition of a tree: It’s called a tree because it looks like an upside-down tree, meaning it has roots up and leaves down. It has the following characteristics:

  1. A tree consists of several nodes

  2. If a tree is not empty, it has at least one root node, and the root node has no parent

  3. Each node can have several children

  4. In addition to the root node, each child node can be divided into multiple disjoint subtrees

  • Binary tree

Binary tree is an important type of tree structure. The data structure abstracted from many practical problems is often in the form of binary tree, even the general tree can be simply converted into binary tree, and the memory structure and algorithm of binary tree are relatively simple, so binary tree is particularly important. The characteristic of binary tree is that each node can only have two subtrees at most, and there are left and right branches [1].

A binary tree is a set of n finite elements that is either empty or consists of an element called the root and two disjoint binary trees called the left subtree and the right subtree. It is an ordered tree. When the set is empty, the binary tree is called an empty binary tree. In a binary tree, an element is also called a node [1].

Binary tree definition:

  1. A binary tree consists of several nodes

  2. If a binary tree is not empty, it has at least one root node, and the root node has no parent node

  3. Each node can have up to two children, a left child node and a right child node

  4. If the left subtree of any node is not empty, all nodes in the left subtree are smaller than the value of this node

  5. If the right subtree of any node is not empty, the values of all nodes in the right subtree are greater than the value of this node

  6. Each child node must also conform to the 2-5 specifications

There are five basic forms of binary trees: Disadvantages of binary trees:

Although the binary tree improves the search efficiency of O(logn), when the data inserted is an ordered sequence, the binary tree looks like a linked list, and the search efficiency decreases to O(n).

Let’s say I insert {1,2,3,4,5,6}In order to avoid such a situation, in 1962, a big AV (G. M. Adelson-Velsky) and a big L (Evgenii Landis) proposed the “balanced binary tree” (AVL). Insert {1,2,3,4,5,6} and the result looks like this:

  • Balanced binary tree

In computer science, AVL tree is the first self balanced binary search tree invented. In an AVL tree, the maximum height difference between the two subtrees corresponding to any node is 1, so it is also called a height-balanced tree. The average and worst case time complexity of lookups, inserts, and deletes is O(logn). Adding and removing elements may require one or more tree rotations to rebalance the tree. The AVL tree takes its name from its inventors G. M. Adelson-Velsky and Evgenii Landis, They published this data structure in their 1962 paper An Algorithm for the Organization of Information.

Balanced binary tree definition:

  1. A balanced binary tree consists of several nodes
  2. If a binary tree is not empty, it has at least one root node, and the root node has no parent node
  3. Each node can have up to two children, a left child node and a right child node
  4. If the left subtree of any node is not empty, all nodes in the left subtree are smaller than the value of this node
  5. If the right subtree of any node is not empty, the values of all nodes in the right subtree are greater than the value of this node
  6. No nodes have equal keys
  7. The absolute value of the height difference between the left and right trees cannot exceed 1
  8. Each child node must also conform to the 3-7 specification

Here is a balanced binary tree (Figure 1)

  • We take the root node 4 as the reference frame, and we can see that the binary tree is not empty, and there is only one root node, satisfying definition 2
  • Each node has at most two children, satisfying definition 3
  • The left subtree 2 of root node 4 is not empty, and the child node of 2 is {1,3}, then the set of left subtree nodes of root node 4 is [2, 1,3], and any value of this set is less than the value of root node 4, satisfying definition 4
  • The right subtree 7 of root node 4 is not empty, the child node of 7 is {6, 9}, the child node of 6 is {5, null}, and the child node of 9 is {8,10}, then the right subtree node set of root node 4 is [7, 6, 9, 5, 8,10], and any value of this set is greater than the value of root node 4, satisfying definition 5
  • The tree has no equal nodes, satisfying definition 6
  • The left subtree depth of 4 is 2 and the right subtree depth is 3, then the height difference between left and right is = left subtree depth – Right subtree depth =2-3=-1. It can be seen that there is a red -1 above the root node, indicating the height difference between left and right subtrees, and the absolute value of -1 is 1, satisfying definition 7
  • Each child node of root node 4 also conforms to the above specification, satisfying Definition 8

1.2 The role of balanced binary trees

Binary tree support dynamic insertion and search, ensure the operation in O(height) time, this is to complete the hash table inconvenient to complete the work, dynamic. But binary trees have the possibility of worst-case, if the input sequence has been sorted, then the time complexity is O(N).

The purpose of balancing binary/red-black trees is to keep the search time in order of logN. Therefore, if the input combination is determined and all that is needed is query, hash table can be considered. If the input set is uncertain, balanced binary tree/red-black tree can be considered to ensure maximum efficiency. The main advantage of balanced binary tree is fast search.

2. Key words overview

  • Root node (root_node)

    A balanced binary tree that is not empty has one and only one root node

  • Parent node (parent_node)

    In addition to the root node, each non-empty node has one and only one parent

  • Left subtree

    Left branch tree of any node (representing the set of nodes under the left branch)

  • Right subtree (right_tree)

    Right branch node tree of any node (representing the set of nodes under the right branch)

  • Left child node (left_child)

    The first node in the left subtree of any node (representing a single node)

  • Right child node (right_Child)

    The first node in the right subtree of any node (representing a single node)

  • Leaf node

    If the left and right child nodes of any node except the root node are empty, the node is called a leaf node, indicating that there is no successor branch

  • BalanceFactor

    Represents the height difference between the left and right subtrees of any node

    The calculation formula is: BF = left subtree height – right subtree height If the absolute value of BF is greater than 1, the tree is out of balance

  • MinUnBalanceTree

    The smallest unbalance node

3. Code implementation ideas

3.1 Node Class (TreeNode)

Based on the definition of a balanced binary tree above, the node class needs to have the following fields

  • Data (node value)
  • Bf (Equilibrium factor)
  • Parent_node: parent node
  • Left_child
  • Right_child (right child node)
  • Count (number of times node data has been inserted repeatedly)

Create a new node class (TreeNode)

  	/** * Node class where data is stored */
    static class TreeNode {
        private int bf = 0;//BalanceFactor
        private int data;// The data stored on the node
        private TreeNode parent_node;// The parent node of this node
        private TreeNode left_child, right_child;// The left and right child nodes of the node
        private int count = 0;// Record the number of times the data was inserted repeatedly

        public TreeNode(int data) {
            this.data = data;

        }
		
		 /** * Do not print all of the left and right child nodes and the parent nodes ** because the nodes reference each other, if you print all of them, the stack will overflow ** therefore, print the values of the left and right child nodes **@return* /
        @Override
        public String toString(a) {
            String p_data = null, l_data = null, r_data = null;
            if(parent_node ! =null) {
                p_data = String.valueOf(parent_node.data);
            }
            if(left_child ! =null) {
                l_data = String.valueOf(left_child.data);
            }
            if(right_child ! =null) {
                r_data = String.valueOf(right_child.data);
            }
            return "TreeNode{" +
                    " data=" + data +
                    ", bf=" + bf +
                    ", count=" + count +
                    ", parent_node_data=" + p_data +
                    ", left_child_data=" + l_data +
                    ", right_child_data=" + r_data +
                    '} ';
        }
		 /** * Because the nodes of a balanced binary tree have unique values, we only need to compare the values to be equal *@param o
         * @return* /
        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null|| getClass() ! = o.getClass())return false;
            TreeNode node = (TreeNode) o;
            return data == node.data;
        }

        @Override
        public int hashCode(a) {
            returnObjects.hash(bf, data, parent_node, left_child, right_child, count); }}Copy the code

3.2 AVLTree

The tree class needs to meet the following conditions:

  • The value of the node in the left subtree of any node is less than the value of the node, and the value of the node in the right subtree is greater than the value of the node. This rule also applies to the child nodes of the node
  • The absolute value of the depth difference between the left and right subtrees of each node is not greater than 1

Create a new tree (AVLTree)

	/** * Balanced binary tree * conditions: * 1. The value of any node in the left subtree is less than the value of the node, the value of the right subtree is greater than the value of the node, the same rule is applicable to the node's children * 2. The absolute value of the depth difference between the left and right subtrees of each node is not greater than 1 */
    static class AVLTree {}Copy the code

We need a queue in the tree class to hold our node values

	// Queue for storing nodes
	private Queue<TestAVL_Tree.TreeNode> tree = new LinkedList<TestAVL_Tree.TreeNode>();
Copy the code

Now let’s insert the first node, write a method to insert the node

	/** * Insert node **@paramData value */
	public void insertNode(int data) {
            TestAVL_Tree.TreeNode new_node = new TestAVL_Tree.TreeNode(data);
            tree.add(new_node);
        }
        
Copy the code

Write a test class and insert data 7 to see the result of the call

	AVLTree avlTree = new AVLTree();
	avlTree.insertNode(7);
	System.out.println("End result:" + avlTree.tree.toString());
Copy the code

TreeNode{data=7, bf=0, count=0, parent_node_data=null, left_child_data=null, right_child_data=null}] TreeNode{data=7, bf=0, count=0, parent_node_data=null, left_child_data=null, right_child_data=null}

At this time, the AVL tree state is:

  • Since the root node must have no parent, it is not indicated here
  • Since both the left and right subtrees are NULL, the equilibrium factor is 0,

Then we insert the second node 6

	avlTree.insertNode(6);
Copy the code

Since the value of 6 is smaller than the root node 7, it is placed in the left child node of the root node, as shown in the figure

  • Node 6 is added to the left tree of root node 7
  • Because a new node is inserted into the left tree, the balancing factor needs to be recalculated. At this time, the left tree depth of root node 7 is 1, the right tree depth is 0, bf=1, and the AVL tree maintains a balanced state

What if root node 7 already had children before it was inserted? There are four possibilities

  • If the new node to be inserted is smaller than the left child node of the root node, the method of inserting is called left_left, that is, inserting the left child node under the left subtree of the node

Insert process:1. According to the definition of AVL tree above,The values of all nodes in the left subtree of any node are smaller than the value of this node; 2. The value of the root node is 7 and the value of the new node is 4. Due to theValue of new node < value of root node3. The value of the left child node is 5, and the value of the new node is 4; Due to theValue of new node < value of left child node, and the left child node has no successor child node to continue to pass, then the new node is inserted under the left subtree of the left child node.

  • If the new node inserted is larger than the left child node of the root node, the method of inserting is called left_right, that is, inserting the right child node under the left subtree of the node

Insert process: ***Copy the code

1. As can be seen from the above definition of AVL tree, the values of all nodes in the left subtree of any node are less than the value of this node, and the values of all nodes in the right subtree are greater than the value 2 of this node. The root node has a value of 7 and the new node has a value of 6. Since the value of the new node is < the value of the root node, the left child of the root node is passed, and the comparison 3 continues. The left child node has a value of 5, and the new node has a value of 6. Since the value of the new node is greater than the value of the left child node, and the left child node has no successor child nodes to continue passing, the new node is inserted under the right subtree of the left child node.

  • The new node inserted is greater than the right child node of the root node. The method of inserting is called right_right, that is, inserting the right child node under the right subtree of the node

Insert process: ***Copy the code

1. According to the definition of AVL tree above, the values of all nodes in the right subtree of any node are greater than the value 2 of this node. The root node has a value of 7 and the new node has a value of 15. Since the value of the new node is greater than the value of the root node, it is passed to the right child of the root node and the comparison 3 continues. The right child node has a value of 10, and the new node has a value of 15. Since the value of the new node is greater than the value of the right child node, and the right child node has no successor child nodes to continue passing, the new node is inserted under the right subtree of the right child node.

  • The new node inserted is smaller than the right child node of the root node. The method of inserting is called right_left (right_left), that is, inserting the left child node under the right subtree of the node

Insert process:1. According to the definition of AVL tree above,The values of all nodes in the left subtree of any node are less than the value of this node, and the values of all nodes in the right subtree are greater than the value of this node2. The value of the root node is 7 and the value of the new node is 8. Due to theNew node value > root node value3. The value of the right child is 10, and the value of the new node is 8; Due to theValue of new node < value of right child node, and the right child node has no subsequent child nodes to continue to pass, then the new node is inserted under the left subtree of the right child node.

	   /** * Compute the position of the newly inserted node **@paramOld_node Indicates the old node *@paramNew_node New node */
        private void indexOf(TreeNode old_node, TreeNode new_node) {
            if (new_node.data == old_node.data) {// The value of the new node equals the value of the old node
                old_node.count++;// Do not calculate the new node in the table below, directly in the old node count+1;
            } else if (new_node.data < old_node.data) {// The value of the new node is smaller than the value of the old node
                if (old_node.left_child == null) {// If the left subtree is empty, put the left subtree of the old node
                    old_node.left_child = new_node;
                    new_node.parent_node = old_node;// Set the current old node as the parent of the new node
                } else {
                    indexOf(old_node.left_child, new_node);// If the left subtree is not empty, then the position is calculated recursively}}else if (new_node.data > old_node.data) {// The value of the new node is greater than or equal to the value of the old node
                if (old_node.right_child == null) {// If the right subtree is empty, put the right subtree of the old node
                    old_node.right_child = new_node;
                    new_node.parent_node = old_node;// Set the current old node as the parent of the new node
                } else {
                    indexOf(old_node.right_child, new_node);// If the right subtree is not empty, then the position is calculated recursively}}}Copy the code

It can be seen that the above four insertion cases will lead to the absolute value of root node BF >1, at which point the binary tree is unbalanced, and the balance state needs to be restored by rotation. For the four insertion cases (left-left, left-right, right-right, right-left), there are four different rotation strategies, and the two rotation methods are respectively left-right and right-left

== Left-handed and right-handed are different from counterclockwise and clockwise. The following two giFs are easy to understand: == left-handed

Left spin is to pull the right branch of the node to the left, the right child node becomes the parent node, and the promotion of the redundant left child node to the right child node of the demoted node

Right hand

Right-rotation is the reverse, pulling the left branch of the node to the right, the left child node becomes the parent node, and the promotion of the redundant right child node to the left child of the demoted node

So if you rotate left, you transform left, and if you rotate right, you transform right. Whether it is left-handed or right-handed, the purpose of rotation is to transfer one node with more nodes to another node with fewer nodes

Left, left

  • The rotation strategy for the LL type (left_left) is right-rotation

In this case, the least unbalanced subtree is the root node 7. As can be seen from the figure below, if the left subtree depth of the root node is 2 and the right subtree depth is 0, it is necessary to perform right-rotation on node 5

  • The old root node (node 7) is the right subtree of the new root node (node 5)

  • The right subtree (if any) of the new root (node 5) is the left subtree of the old root

Find the least uneven subtree before you rotate

The search process is:

1. Start from the newly inserted node and look up the parent node to determine whether the absolute value of BF of the parent node is greater than 1 or 2. If < or = 1, then the parent node is the least unbalanced subtree. 3. If < or = 1, then the parent node of the parent node continues to be tracked up until the grandfather node of bf>1 is found

	   /** * Calculate the least unbalanced subtree * possible cases: * 1. This node is the root node (no parent node) * 2. The balance factor of the parent node of this node is >1, which means that this node is the least unbalanced subtree * 3. The balance factor of the parent node is <1, and the recursion continues to look up * *@paramNode Newly inserted node *@returnLeast unbalanced subtree */
        private TreeNode countMinUnBalanceNode(TreeNode node) {
            TreeNode from_node = node.parent_node;// Get the parent of the newly inserted node
            if(from_node ! =null) {// This node is not the root node
                int bf_abs = Math.abs(from_node.bf);
                if (bf_abs > 1) {// The absolute value of the balance factor >1 indicates that the node is out of balance, and is the minimum unbalance subnumber
                    return from_node;
                } else if (bf_abs <= 1) {
                    return countMinUnBalanceNode(from_node);// Otherwise the recursive call looks up}}else {// This node is the root node
                int bf_abs = Math.abs(node.bf);
                if (bf_abs > 1) {// The absolute value of the balance factor >1 indicates that the node is out of balance, and is the minimum unbalance subnumber
                    returnnode; }}return null;
        }
        
Copy the code

Node right-handed code

  	   /** * Right-turn nodes **@paramNode Indicates the node (*/) to be rotated right-handed
        private void rightRotate(TreeNode node) {
            TreeNode left_child = node.left_child;// The left subtree of the current node
            TreeNode parent_node = node.parent_node;// The parent node of the current node
            if(parent_node ! =null) {// If the current node is not the root node
                // Determine whether the current node is the left or right subtree of the parent node
                if (node.equals(parent_node.left_child)) {
                    node.parent_node.left_child = left_child;// Replace the current node in the parent node with the left subtree
                } else if (node.equals(parent_node.right_child)) {
                    node.parent_node.right_child = left_child;// Replace the current node in the parent node with the left subtree
                }
            }
            left_child.parent_node = parent_node;// The parent node of the original left subtree (current parent) is changed to the parent node of the original parent (current right subtree)

            TreeNode left_child_right = left_child.right_child;// Get the right node of the original left subtree
            // If not null, set the right node of the left subtree as the left subtree of the original parent
            if(left_child_right ! =null) {
                left_child_right.parent_node = node;
            }
            node.left_child = left_child_right;// The parent node of the right node of the original left subtree is changed to the left node of the current right subtree (original parent node)

            left_child.right_child = node;// Change the right subtree of the current parent node (original left child node) to the original parent node
            node.parent_node = left_child;// Change the parent node of the current right subtree (original parent) to the original left subtree (current parent)
            reCountNodeBF();// The right hand rotation completes the recalculation of the node's balance factor
            System.out.println("Dextropronation:" + tree.toString());
        }
        
Copy the code

Right, right

  • The rotation strategy for RR (RIGHT_right) is left rotation

In this case, the least unbalanced subtree is root node 7. As can be seen from the figure below, if the depth of the left subtree of the root node is 0 and the depth of the right subtree is 2, it is necessary to perform left-handed rotation on node 10

  • The old root node (node 7) is the left subtree of the new root node (node 10)
  • The left subtree (if any) of the new root (node 10) is the right subtree of the old root

Node left-handed code

/** * Turn the node left-handed **@paramNode Indicates the node (*/) to be rotated to the left
        private void leftRotate(TreeNode node) {
            TreeNode right_child = node.right_child;// The right subtree of the current node
            TreeNode parent_node = node.parent_node;// The parent node of the current node
            if(parent_node ! =null) {// If the current node is not the root node
                // Determine whether the current node is the left or right subtree of the parent node
                if (node.equals(parent_node.left_child)) {
                    parent_node.left_child = right_child;// Replace the current node in the parent node with the left subtree
                } else if (node.equals(parent_node.right_child)) {
                    parent_node.right_child = right_child;// Replace the current node in the parent node with the left subtree
                }
            }
            right_child.parent_node = parent_node;// The parent node of the original right subtree (current parent) is changed to the parent node of the original parent (current left subtree)

            TreeNode right_child_left = right_child.left_child;// Get the left node of the original right subtree
            // If not null, set the parent of the left node of the right subtree as the right node of the original parent (the current left subtree)
            if(right_child_left ! =null) {
                right_child_left.parent_node = node;
            }
            node.right_child = right_child_left;// The parent node of the left node of the original right subtree is changed to the right node of the current left subtree (original parent node)

            right_child.left_child = node;// The left subtree of the current parent (the original right subtree) is changed to the original parent
            node.parent_node = right_child;// The parent node of the left subtree (original parent) is changed to the original right subtree (current parent)
            reCountNodeBF();// The leftward rotation completes the recalculation of the node's balance factor
            System.out.println("Left supination:" + tree.toString());
        }
        
Copy the code

Or so

  • The rotation strategy for THE LR type (left_right) is: first rotate from left to left, then rotate right

In this case, the least unbalanced subtree is the root node 7. As can be seen from the figure below, the depth of the left subtree of the root node is 2, and the depth of the right subtree is 0, and the new node (6) is less than the left subnode (5) of the root node, then the left and right rotation of node 6 should be performed first

Right to left

  • The rotation strategy for RL type (RIGHT_left) is: turn right to right, then left

In this case, the least unbalanced subtree is the root node 7. As can be seen from the figure below, the depth of the left subtree of the root node is 0, and the depth of the right subtree of the root node is 2, and the new node (6) is less than the right subnode (5) of the root node, then the right subtree should be rotated to node 6 first

  	   /** * Perform rotation * 4 possible scenarios: * 1. Left-left (direct right-rotation) * 2. Left/right (first left to left then right) * 3. Right/right (direct left) * 4. Right to left (first right to right then left) * *@paramNew_node Newly inserted node *@paramMinUnBalanceTree Minimum unbalanced subtree */
        private void executeRotation(TreeNode new_node, TreeNode minUnBalanceTree) {
            System.out.println("Before rotation:" + tree.toString());
            TreeNode old_node = new_node.parent_node;
            if (minUnBalanceTree.bf > 1) {// More left, more right
                if(new_node ! = old_node.left_child) {// Left and right (the current node is not the left subtree of the old node)
                    leftRotate(old_node);// Turn left to left first
                    minUnBalanceTree = countMinUnBalanceNode(new_node);// Calculate the least unbalanced subtree
                }
                rightRotate(minUnBalanceTree);/ / right
            } else if (minUnBalanceTree.bf < -1) {// More on the right, more on the left
                if(new_node ! = old_node.right_child) {// Right left (current node is not the right subtree of the old node)
                    rightRotate(old_node);// Turn right to right
                    minUnBalanceTree = countMinUnBalanceNode(new_node);// Calculate the least unbalanced subtree
                }
                leftRotate(minUnBalanceTree);/ / left}}Copy the code

The method of inserting a node is changed to

 	   /** * Insert node * Perform the following steps: * 1. Calculate the coordinates of the insert node * 2. Add to queue * 3. Recalculate the balance factor for each node * 4. Calculate the least unbalanced subtree * 5. If there is a least unbalanced subtree, then rotation * * is performed@paramData value */
        public void insertNode(int data) {
            TreeNode new_node = new TreeNode(data);
            int size = tree.size();
            if (size == 0) {// If there is no node in the tree, it is added for the first time
                tree.add(new_node);
            } else {
                indexOf(getRootNode(), new_node);// Calculate the insertion position
                if(new_node.parent_node ! =null) {
                    tree.add(new_node);// Add to queue
                }
                reCountNodeBF();// Recalculate the balance factor for each node
                TreeNode minUnBalanceTree = countMinUnBalanceNode(new_node);// Calculate the least unbalanced subtree
                if(minUnBalanceTree ! =null) {// represents imbalance
                    System.out.println("The least unbalanced subtree is:" + minUnBalanceTree.toString());
                    executeRotation(new_node, minUnBalanceTree);// Perform rotation}}}Copy the code

Similarly, we can easily write a method to insert an array of node values

 	   /** * Insert array **@paramArr Array of node values */
        public void insertArr(int[] arr) {
            for (intdata : arr) { insertNode(data); }}Copy the code

To find the node

  • The principle of

Let’s start with a pictureThe idea of finding nodes is similar to dichotomyFor example, if we want to find node 3, we know the node according to the definition of balanced binary treeThe left subtreeOn the value of theLess thanThe node itself,The right subtreeOn the value of theIs greater thanThe node itself starts with the root node, whose value is4.Is greater thanOur lookup value3, then our target node can only exist in the root nodeThe left subtreeThe value of the left child of the root node is2.Less thanWe look for values3, then our target node can only exist in this nodeThe right subtreeThe value of the right child of node 2 is3.Is equal to theOur lookup value, then this node is our target node

** Similarly, if we search for a nonexistent node 7** >, we first judge from the root node, and the value of the root node is **4**, ** is less than ** our search value **7**, then our target node can only exist in the right subtree ** of the root nodeCopy the code

The value of the right child node of the root node is 5, which is less than our search value of 7, then our target node can only exist in the right child node of the node’s right subtree node 6. The right child node is empty, and the node value is less than our search value of 7, which means that the target node does not exist

  • Code implementation
 	   /** * Find nodes * similar to dichotomy **@paramData value *@return Node
         */
        public TreeNode searchNode(int data) {
            TreeNode rootNode = getRootNode();// Get the root node
            return dichotomousSearch(data, rootNode);// Start at the root node and search down (using dichotomy)
        }
        
Copy the code
	   /** * Recursive binary search * has the following cases: * 1. The target value is equal to the value of the comparison node, indicating that * 2 has been found. If the target value is less than the value of the comparison node, then recursively search * 3 starting from the left subtree of the comparison node. If the target value is greater than the value of the comparison node, we recursively search * * from the right subtree of the comparison node@paramTarget_data Target value *@paramCompare_node Node that compares the target value *@return Node
         */
        private TreeNode dichotomousSearch(int target_data, TreeNode compare_node) {
            if (target_data == compare_node.data) {// Return the comparison node if the target value is equal to the value of the comparison node
                return compare_node;
            } else if(target_data < compare_node.data && compare_node.left_child ! =null) {// If the target value is greater than the value of the comparison node, the recursive search starts from the left subtree of the comparison node
                return dichotomousSearch(target_data, compare_node.left_child);
            } else if(target_data > compare_node.data && compare_node.right_child ! =null) {// If the target value is greater than the value of the comparison node, the recursive search starts from the right subtree of the comparison node
                return dichotomousSearch(target_data, compare_node.right_child);
            }
            return null;
        }
       
Copy the code

To summarize, the process of inserting a node is as follows:

  1. Traverse the binary tree to determine whether the newly inserted node already exists. If so, count++ to the node and do not repeat the insertion
  2. Compute the coordinates of the new node (who is its parent and whether it is a left or right child of the parent)
  3. Add nodes to the binary tree
  4. Traverse the binary tree and recalculate the balance factor of all nodes to see if any node is out of balance
  5. If there is an imbalance, start at the newly inserted node and find the least unbalanced subtree
  6. According to the type of imbalance (left to left, left to right, right to left, right to right), different rotation strategies are performed

Deleting a node The case of deleting a node is complicated because deleting a node is as likely to cause the binary tree to lose balance as adding a node

The deletion process can be divided into three situations

  1. The deleted nodes are leaf nodes (such as nodes 1, 3, and 6 in the figure above), that is, there are no left or right child nodes
  2. The deleted node has only left subtree or only right subtree (such as node 5 in the figure above)
  3. Deleted nodes have both left and right subtrees (such as nodes 4,2 in the figure above)

We need to know that the deletion of a node in the left subtree is equivalent to the insertion of a new node in the right subtree, and the deletion of a node in the right subtree is equivalent to the insertion of a new node in the left subtree. According to this, we make a judgment and take the corresponding balance adjustment operation.

Consider these three cases:

  1. The deleted node is a leaf node

Case 1: For example, nodes {8,14,25,31,40} in the figure above are all leaf nodes. Let’s delete node 14

** The deleted tree structure is: **Copy the code

We need to redo the parent node of the deleted node. Start by looking up to see if there are any unbalanced nodes

  • If the parent node value of node 14 is 10, the left subtree depth of node 10 is 1, and the right subtree depth of node 10 is 0, then bf = 1; No imbalance, continue to look up

  • If the parent node value of node 10 is 20, the left subtree depth of node 20 is 2, and the right subtree depth of node 20 is 3, then bf = -1; No imbalance, since this node is already the root node, stop looking

  • Now the binary tree is in equilibrium

    Example 2: In the figure above, nodes {7, 21, 40} are all leaf nodes. Let’s remove node 7

    The deleted tree structure is as follows: According to example 1, the steps to retrieve a node are

  • If the parent of node 7 is 8, and node 8 has no subtree, then bf = 0; No imbalance, continue to look up

  • The value of the parent node of node 8 is 20, the depth of the left subtree of node 20 is 1, and the depth of the right subtree of node 20 is 3, then bf = -2, this node is unbalanced, and this node is the least unbalanced subtree

  • The binary tree is out of balance

So how do you adjust?

As mentioned above, deleting a node from the left subtree is the same as inserting a node into the right subtree.

We find the child node 30 of the right subtree of node 20, and find that the height of the left subtree of node 30 is higher than that of the right subtree, which is equivalent to inserting a new node under the left subtree of node 30 of the right subtree of node 20. This requires RL type (right left) adjustment.

== Note: the RL type (right left) adjustment is different from the adjustment steps for inserting nodes above!! = =

First, right-handed adjustment is made to the right child node (30) of the least unbalanced subtree (node 20). After the adjustment, it can be:

Next, the least unbalanced subtree (node 20) is adjusted left-handed. After adjustment, it can be: Through retrieval, the binary tree at this time remains in equilibrium

Example 3: Let’s delete node 8, and the tree structure after deletion is: Through retrieval, it can be concluded that the root node (25) is the least unbalanced subtree, bf = -2, which is in an unbalanced state and needs to be adjusted. As mentioned above, deleting a node from the left subtree is the same as inserting a node into the right subtree.But how to adjust it also depends on the height difference between the right and left subtrees of the unbalanced node.

The adjustment steps are as follows:

  1. Find the right child node (30) of the least unbalanced subtree (root node 25)
  2. The height of the left and right subtrees of node 30 is the same, so only RR (right and right) adjustment is required

The adjusted binary tree is:

To summarize, the steps to remove a leaf node are:

  1. Remove the node directly from the tree
  2. Start from the parent node of the deleted node and search upward to determine whether the height difference between the left and right subtrees of the node exceeds 1. If yes, the tree is unbalanced, and this node is the least unbalanced subtree; If not, the search continues up to the root node.
  3. If the imbalance is retrieved, different rotation policies are executed according to the type of imbalance (LL, LR, RL, RR) (== The rotation policy at this time is different from that of adding nodes ==).

Code implementation:

	   /** * Remove a leaf node (a node with no left or right subtree) **@paramNode Indicates the deleted node *@return Result
         */
        private Result deleteNodeByLeafNode(TreeNode node) {
            if (node.parent_node == null) {// This node is the root node (in this case, the binary tree has only one node)
                tree.remove(node);// Remove this node from the queue
                return new Result(true, node);
            } else {// This node is a leaf node
                if (node == node.parent_node.left_child) {// This node is the left child of the parent node
                    node.parent_node.left_child = null;// Set the node to null
                } else if (node == node.parent_node.right_child) {// This node is the right child of the parent node
                    node.parent_node.right_child = null;// Set the node to null
                }
            }
            tree.remove(node);// Remove this node from the queue
            return new Result(false, node);
        }
        
Copy the code

Delete the result callback class:

 /** * Delete the result callback class */
    static class Result {
        private boolean isSkipBuild;// Whether to skip retrieval
        private TreeNode target_node;// Tag node

        public Result(boolean isSkipBuild, TreeNode target_node) {
            this.isSkipBuild = isSkipBuild;
            this.target_node = target_node; }}Copy the code

To determine how to perform a rotation:

  	   /** * Unscramble the node tree * to determine if rotation is required **@param target_node
         */
        private void rebuild(TreeNode target_node) {
            TreeNode minUnBalanceTree = countMinUnBalanceNode(target_node);// Find the least unbalanced subtree, starting with the parent node of the deleted node
            if (minUnBalanceTree == null) return;
            System.out.println("The least unbalanced subtree is:" + minUnBalanceTree.toString());
            if (minUnBalanceTree.bf > 1) {// The deleted node belongs to the right branch of the least unbalanced subtree
                if (minUnBalanceTree.left_child.bf >= 0) {// The left tree is equal to the right tree or the left tree is taller than the right tree
                    System.out.println("Before rotation:" + tree.toString());
                    rightRotate(minUnBalanceTree);
                } else if (minUnBalanceTree.left_child.bf < 0) {// The right tree is taller than the leftleftRotate(minUnBalanceTree.left_child); rightRotate(minUnBalanceTree); }}else if (minUnBalanceTree.bf < -1) {// The deleted node belongs to the left branch of the least unbalanced subtree
                if (minUnBalanceTree.right_child.bf > 0) {// The left tree is taller than the right tree
                    rightRotate(minUnBalanceTree.right_child);
                    leftRotate(minUnBalanceTree);
                } else if (minUnBalanceTree.right_child.bf <= 0) {// The right tree is the same height as the left tree or the right tree is taller than the left tree
                    System.out.println("Before rotation:"+ tree.toString()); leftRotate(minUnBalanceTree); }}// Retrieve recursively upward
            rebuild(minUnBalanceTree.parent_node);
        }
      
Copy the code

  1. The deleted node has only one subtree (left or right)

    Case 1: In this tree, there is only one subtree whose node is {29, 40}. Let’s delete node 29

    The deleted tree structure is as follows:

    You can see that the binary tree is in equilibrium

    If we change the node removed in example 1 to 40, we need to replace node 40 in its parent node with the right subtree or the left subtree of node 40 because node 40 only has a right subtree, in this case we replace it with the right subtree of node 50

    The deleted tree structure is as follows:

    Through retrieval, it can be seen that node 30 is out of balance, and the minimum unbalance subtree is 30.Deleting a node from the right subtree is equivalent to inserting a new node into the left subtree, which is equivalent to inserting nodes into the right subtree of the left subtree. So we’re going to do LR adjustment here.

    Adjustment steps:

    • We first find the replacement node 50 for the deleted node 40
    • Starting from node 50, retrieve the unbalanced node upward
    • When the root node (30) is unbalanced, bf = 2,
    • Find the left child node (25) of the least unbalanced subtree (root node 30) and perform left-handed rotation
    • Perform a right turn on the least unbalanced subtree (root node 30)

The structure of the left supination tree is:

The dextral tree structure is:

To summarize, the steps to remove a node with a child node are:

  1. Remove the node directly from the tree
  2. Replace the node in its original position with a subsequent stepson node (left or right child node) of the node
  3. Start from the parent node of the deleted node and search upward to determine whether the height difference between the left and right subtrees of the node exceeds 1. If yes, the tree is unbalanced, and this node is the least unbalanced subtree; If not, the search continues up to the root node.
  4. If the imbalance is retrieved, different rotation policies are executed according to the type of imbalance (LL, LR, RL, RR) (== The rotation policy at this time is different from that of adding nodes ==).

Code implementation:

 	   /** * delete a node with only a left subtree **@paramNode Indicates the deleted node *@return Result
         */
        private Result deleteNodeByOnlyleftTree(TreeNode node) {
            if(node.parent_node ! =null && node.data < node.parent_node.data) {// If there is a parent node and the value of this node is less than the value of the parent node (indicating that this node is the left child of the parent node)
                node.parent_node.left_child = node.left_child;// The left child of the current parent replaces the left child of this node
                node.left_child.parent_node = node.parent_node;// Replace the parent node of the left child node of the current node with the parent node of the current node
            } else if(node.parent_node ! =null && node.data > node.parent_node.data) {// If there is a parent node and the value of this node is greater than the value of the parent node (indicating that this node is the right child of the parent node)
                node.parent_node.right_child = node.left_child;// The right child of the current parent replaces the left child of this node
                node.left_child.parent_node = node.parent_node;// Replace the parent node of the left child node of the current node with the parent node of the current node
            } else {// Indicates that the node to be deleted is the root node and the root node has only left child nodes
                node.left_child.parent_node = null;// Leave the parent reference of the left child of the node blank and skip the search
                tree.remove(node);// Remove this node from the queue
                return new Result(true, node);
            }
            tree.remove(node);// Remove this node from the queue
            return new Result(false, node);
        }
Copy the code
	   /** * delete a node with only the right subtree **@paramNode Indicates the deleted node *@return Result
         */
        private Result deleteNodeByOnlyRightTree(TreeNode node) {
            if(node.parent_node ! =null && node.data < node.parent_node.data) {// If there is a parent node and the value of this node is less than the value of the parent node (indicating that this node is the left child of the parent node)
                node.parent_node.left_child = node.right_child;// The left child of the current parent replaces the right child of this node
                node.right_child.parent_node = node.parent_node;// Replace the parent node of the left child node of the current node with the parent node of the current node
            } else if(node.parent_node ! =null && node.data > node.parent_node.data) {// If there is a parent node and the value of this node is greater than the value of the parent node (indicating that this node is the right child of the parent node)
                node.parent_node.right_child = node.right_child;// The right child of the current parent replaces the right child of this node
                node.right_child.parent_node = node.parent_node;// Replace the parent node of the left child node of the current node with the parent node of the current node
            } else {// Indicates that the node to be deleted is the root node and the root node has only the right child node
                node.right_child.parent_node = null;// Empty the reference to the parent node of the right child of the node and skip the retrieval
                tree.remove(node);// Remove this node from the queue
                return new Result(true, node);
            }
            tree.remove(node);// Remove this node from the queue
            return new Result(false, node);
        }
Copy the code

  • The deleted node has both left and right subtrees

    Case 1:

    {10,20}; let’s remove the root node (20).This is different from case 2, because the root node has both left and right subtrees, so it is not easy to replace the location of the deleted node with the left and right subtrees

    Let’s analyze the situation:

    • As the balance factor of the root node (20) is 1, it can be known that the left tree depth of the root node is higher than the right tree
    • At this point we need to find the maximum node in the left subtree of the root node
    • It can be seen from the figure above that the maximum node is 15, and we replace the value of node 15 with that of node 20 (== is only a value replacement, without changing other information of the two nodes, such as parent node reference, left and right child node reference, balance factor, insert times ==).

After the replacement, the tree structure is:

  • Then delete the node whose value is 20

The deleted tree structure is as follows:

At this time, we find that the parent node (10) bf = 2 of the deleted node whose value is 20 is in an unbalanced state, and the minimum unbalanced subtree is node 10. It is necessary to adjust the subtree with 10 as the root node (when deleting at this place, it is equivalent to inserting into the right subtree of the left subtree with 10 as the root node), which is LR adjustment. The left child node (8) of node 10 is rotated to make it left-left

The structure of the left supination tree is:

Then right-rotate the least unbalanced subtree (node 10)

The dextral tree structure is:

Now the binary tree is balanced

To summarize, the steps to delete a node with left and right subtrees are:

  1. Determine whether the bf value of the deleted node belongs to the interval of [0,1] or = -1 (belonging to [0,1] means that the left subtree of the node is deeper than the right subtree or as deep as the right subtree; equal to -1 means that the right subtree is deeper than the left subtree)
  2. If left subtree depth > = right subtree depth, the maximum node in the left subtree is found
  3. If right subtree depth > left subtree depth, the minimum node in the right subtree is found
  4. Exchange the value of the maximum or minimum found node with that of the deleted node (== only exchange the value without modifying other attributes ==)
  5. Delete the node where the original value is located
  6. Start from the parent node of the deleted node and search upward to determine whether the height difference between the left and right subtrees of the node exceeds 1. If yes, the tree is unbalanced, and this node is the least unbalanced subtree; If not, the search continues up to the root node.
  7. If the imbalance is retrieved, different rotation policies are executed according to the type of imbalance (LL, LR, RL, RR) (== The rotation policy at this time is different from that of adding nodes ==).

PS: With regard to maximum and minimum nodes, let’s explore a question here. Why does the left subtree depth > = right subtree depth find the maximum node in the left subtree to replace, and the right subtree depth > left subtree depth find the minimum node in the right subtree to replace? Could you flip it the other way around?

Let’s see what happens the other way around, or in the example above

Instead of replacing node 20 with node 15, which is the largest node in the left subtree, let’s replace it with node 8, which is the smallest node in the left subtree

After the replacement, the tree structure is:

  • Then delete the node whose value is 20

    The deleted tree structure is as follows:

The left child of the root node (8) is 10 and the right child is 25. According to the definition of binary tree above, the value in the left subtree of any node is smaller than that node, and the value in the right subtree is greater than that node. Obviously, the value of the left child node of node 8 is greater than this node, which does not meet the requirements of binary tree. So you can only replace it with the maximum node in the left subtree.

How do I get the maximum node in the left subtree

Case diagram: For example, I want to get the maximum value node 3 in the left subtree of the root node 4, becauseThe right subtree value of any node is greater than the value of that nodeTo obtain node 3 is to obtain the rightmost node in the left subtree of the root node. What if there is no rightmost node in the left subtree of the node? For example, I want to obtain the maximum value node in the left subtree of node 7. The left subtree of node 7 is node 6. Since the right subnode of node 6 is empty, node 6 is the maximum value node in the left subtree.

Code implementation: Here are two implementation ideas

  • recursive

       /** * Obtain the maximum value of the target node. Node * Obtaining the maximum value of a node is essentially obtaining the rightmost child node of that node@param node
     * @return* /
    private TreeNode getMaxNode(TreeNode node) {
        if (node == null) return null;
        return node.right_child == null ? node : getMaxNode(node.right_child);
    }
    
Copy the code

  • cycle

       /** * Obtain the maximum value of the target node. Node * Obtaining the maximum value of a node is essentially obtaining the rightmost child node of that node@param node
     * @return* /
    private TreeNode getMaxNode(TreeNode node) {
        if (node == null) return null;
         while(node.right_child ! =null) {
            node = node.right_child;
        }
        return node;
    }
    
Copy the code

    Similarly, the smallest node in the right subtree of the node can be obtained

    Code implementation:

    • recursive
       /** * Obtain the minimum value of the target node node ** obtain the minimum value of the node is to obtain the leftmost child node **@param node
     * @return* /
    private TreeNode getMinNode(TreeNode node) {
        if (node == null) return null;
        return node.left_child== null ? node : getMinNode(node.left_child);
    }
    
Copy the code

  • cycle

       /** * Obtain the minimum value of the target node node ** obtain the minimum value of the node is to obtain the leftmost child node **@param node
     * @return* /
    private TreeNode getMinNode(TreeNode node) {
        if (node == null) return null;
         while(node.left_child! =null) {
            node = node.left_child;
        }
        return node;
    }
    
Copy the code

The complete code for deleting a node is:

  	   /** * Delete a node ** there are four cases: ** 1. Delete a node with no left or right child nodes (leaf or root) ** 2. The deleted node has the left child node * * 3. The deleted node has the right child node * * 4. The nodes to be deleted include left and right child nodes * *@paramData value *@returnTrue: the deletion succeeds. False: the deletion fails */
        public boolean deleteNode(int data) {
            TreeNode node = searchNode(data);// Find the node
            if (node == null) return false;
            boolean isSkipBuild = false;// Whether to skip rebuild()
            Result result = null;// Delete the result callback
            /** * If the node to be deleted has no left or right subtrees * 1. Check whether the node is the root node (if the root node has no left or right subtrees, you can skip the search) * 2. To determine whether this node is the left or right child of its parent, leave its chain of references to the parent null * 3. Delete the node * 4. Search up from the parent node of the deleted node to check whether any node is out of balance. If yes, stop the search and perform rotation */ based on the type of the node out of balance
            if (node.left_child == null && node.right_child == null) {
                result = deleteNodeByLeafNode(node);// Delete a leaf node (a node with no left or right subtree)
                node = result.target_node;
                isSkipBuild = result.isSkipBuild;
                System.out.println(The deleted node is: + node.toString());
                /** * If only the left subtree is deleted * 1. Determine whether the node is the root node (delete only the left subtree root node can skip retrieval) * 2. Determine whether the node is the left child node or the right child node of the parent node, replace its original reference chain in the parent node with the left child node of the node, and replace the parent node of the left child node of the node with the parent node * 3 of the node. Delete a node * 4. Search up from the parent node of the deleted node to check whether any node is out of balance. If yes, stop the search and perform rotation */ based on the type of the node out of balance
            } else if(node.left_child ! =null && node.right_child == null) {
                result = deleteNodeByOnlyleftTree(node);// Delete a node with only the left subtree
                node = result.target_node;
                isSkipBuild = result.isSkipBuild;
                System.out.println(The deleted node is: + node.toString());
                /** * If only the right subtree is deleted * 1. Determine whether the node is the root node (delete only the right subtree root node can skip retrieval) * 2. Determine whether the node is the left child node or the right child node of the parent node, replace its original reference chain in the parent node with the right child node of the node, and replace the parent node of the right child node of the node with the parent node * 3 of the node. Delete a node * 4. Search up from the parent node of the deleted node to check whether any node is out of balance. If yes, stop the search and perform rotation */ based on the type of the node out of balance
            } else if(node.right_child ! =null && node.left_child == null) {
                result = deleteNodeByOnlyRightTree(node);// Delete a node with only the right subtree
                node = result.target_node;
                isSkipBuild = result.isSkipBuild;
                System.out.println(The deleted node is: + node.toString());
                /** * If the node to be deleted has left and right subtrees * 1. Determine whether the balancing factor of the node is 0 or 1. If yes, find the maximum node (left_max node) in the left subtree of the node and exchange the value of this node with the value of left_max node (only exchange the value, do not replace the reference chain, calculate the factor, etc.) * 2. Judge whether the balance factor of this node is -1. If yes, find the minimum value node (right_min node) in the right subtree of this node, and exchange the value of this node with the value of right_min node (only exchange value, do not replace the reference chain, calculate the factor, etc.) * 3. Remove the left_max node or the right_min node * 4 after the replacement value. The parent node of the deleted node is searched up to see if any nodes are out of balance. If so, the search is stopped and rotation */ is performed based on the type of imbalance
            } else if(node.left_child ! =null&& node.right_child ! =null) {
                if (node.bf == 0 || node.bf == 1) {// If the node's balancing factor is 0 or 1
                    TreeNode max_node = getMaxNode(node.left_child);// Get the maximum value of the node in the left subtree of the deleted node (this node can only be a leaf node or a node with only left subtree)
                    int temp_data = node.data;// Swap node values
                    node.data = max_node.data;
                    max_node.data = temp_data;
                    if(max_node.left_child ! =null) {// This node is a node with only the left subtree
                        result = deleteNodeByOnlyleftTree(max_node);// Delete a node with only the left subtree
                        node = result.target_node;
                        isSkipBuild = result.isSkipBuild;
                    } else {// This node is a leaf node
                        result = deleteNodeByLeafNode(max_node);// Delete a leaf node (a node with no left or right subtree)
                        node = result.target_node;
                        isSkipBuild = result.isSkipBuild;
                    }
                    System.out.println(The deleted node is: + max_node.toString());
                } else if (node.bf == -1) {// If the node's balancing factor is -1
                    TreeNode min_node = getMinNode(node.right_child);// Get the minimum node in the right subtree of the deleted node (this node can only be a leaf node, or a node with only the right subtree)
                    int temp_data = node.data;// Swap node values
                    node.data = min_node.data;
                    min_node.data = temp_data;// Swap node values
                    if(min_node.right_child ! =null) {// This node is a node with only the right subtree
                        result = deleteNodeByOnlyRightTree(min_node);// Delete a node with only the right subtree
                        node = result.target_node;
                        isSkipBuild = result.isSkipBuild;
                    } else {// This node is a leaf node
                        result = deleteNodeByLeafNode(min_node);// Delete a leaf node (a node with no left or right subtree)
                        node = result.target_node;
                        isSkipBuild = result.isSkipBuild;
                    }
                    System.out.println(The deleted node is: + min_node.toString());
                }
            }
            reCountNodeBF();// Recalculate the balance factor
            if(! isSkipBuild) { rebuild(node); }return true;
        }
Copy the code

Modify the node

Modify the node is relatively simple, here only to say the realization of ideas, do not draw the principle of discussion. Changing the value of a node is equivalent to deleting the node and inserting a new one

Modification Steps:

  1. The binary tree is retrieved to determine whether the modified node exists
  2. Deletes the retrieved node
  3. Create a node with the modified value

Code implementation:

       /** * Modify a node * to change the value of a node is equal to deleting the node and assigning the expected value to the new node **@paramTarget_value Target value *@paramExpected_value Expect value *@returnModification result */
        public boolean modifyNode(int target_value, int expected_value) {
            TreeNode node = searchNode(target_value);
            if (node == null) return false;// This node is not found
            if (deleteNode(target_value)) {// Delete the target value node
                insertNode(expected_value);// If the deletion is successful, a new node is inserted with the target value
            } else {
                return false;
            }
            return true;
        }
Copy the code

Finally paste the complete source resources, interested can copy down to test. Source address ==ps: The code has not been optimized for performance, interested in further study ==