Tree production into forest -- binary tree, binary sorting tree, balanced binary tree, B tree, B + tree

Tree structure is not new to everyone, but there are several trees that are really applied to the code - binary sorting tree, balanced binary tree, B tree, B + tree, red and black tree. Whether you know it or not, today, after reading this blog, you will plant it in front of your home.

Binary tree

definition:
It is another kind of tree structure. Its characteristic is that there are only two subtrees in each node (that is, there is no node with a degree greater than 2 in the binary tree). Moreover, the subtrees of the binary tree can be divided into left and right, and their times cannot be reversed arbitrarily.
nature:

  • 1. There are two (i-1) power nodes (I > = 1) on the i-th layer of a binary tree
  • 2. The number of binary trees with depth K has the nodes of K power-1 of 2 (k > = 1)
  • 3. For any binary tree T, if its terminal node number is n0 and the node number of degree 2 is n2, then n0=n2+1

Node structure of binary tree:

Traversal of binary tree:
1. Preorder traversal

  //Recursive implementation of prior traversal
    public static void rec_first(Tree_Node tree){
        System.out.println(tree.value);

        Tree_Node l = tree.lchild;
        if(l!=null){
            rec_first(l);
        }
        Tree_Node r = tree.rchild;
        if(r!=null){
            rec_first(r);
        }
    }

    /**
     * Non recursive implementation with stack structure
     */
    public static void stack_first(Tree_Node tree ){
        Stack_demo1<Tree_Node> stack = new Stack_demo1<>();
        while(tree != null || !stack.isEmpty() )
        {
            while(tree != null)
            {
                System.out.println(tree.value);
                Nodeclass<Tree_Node> ss = new Nodeclass<>();
                ss.setData(tree);
                stack.push(ss);
                tree = tree.lchild;
            }
            if(!stack.isEmpty())
            {
                tree = stack.pop().getData();
//                System.out.println(tree.value);
//                System.out.println(tree.value);
               if (tree.rchild!=null){
                   tree = tree.rchild;
               }else{
                   tree = stack.pop().getData();
                   if (tree!=null) {
                       tree = tree.rchild;
                   }
               }
            }
        }
    }

2. Middle order traversal:

//Recursive implementation of middle order traversal
    public static void rec_second(Tree_Node tree){
        Tree_Node l = tree.lchild;
        if(l!=null){
            rec_second(l);
        }
        System.out.println(tree.value);
        Tree_Node r = tree.rchild;
        if(r!=null){
            rec_second(r);
        }
    }

    /**
     * Non recursive implementation with stack structure
     */
    public static void stack_second(Tree_Node tree ){
        Stack_demo1<Tree_Node> stack = new Stack_demo1<>();
        while(tree != null || !stack.isEmpty() )
        {
            while(tree != null)
            {
                Nodeclass<Tree_Node> ss = new Nodeclass<>();
                ss.setData(tree);
                stack.push(ss);
                tree = tree.lchild;
            }
            if(!stack.isEmpty())
            {
                tree = stack.pop().getData();
                System.out.println(tree.value);
//                System.out.println(tree.value);
//                System.out.println(tree.value);
                if (tree.rchild!=null){
                    tree = tree.rchild;
                }else{
                    tree = stack.pop().getData();
                    if (tree!=null) {
                        System.out.println(tree.value);
                        tree = tree.rchild;
                    }
                }
            }
        }
    }

3. Subsequent traversal:

    //Recursive implementation of post order traversal
    public static void rec_third(Tree_Node tree){


        Tree_Node l = tree.lchild;
        if(l!=null){
            rec_third(l);
        }


        Tree_Node r = tree.rchild;
        if(r!=null){
            rec_third(r);
        }
        System.out.print(tree.value+" -> " );

    }

    /**
     * Non recursive implementation with stack structure
     */
    public static void stack_third(Tree_Node tree ){
        Stack_demo1<Tree_Node> stack = new Stack_demo1<>();
        Stack_demo1<Tree_Node> stack2 = new Stack_demo1<>();
        while(tree!=null||stack!=null){
            if (tree!=null){
                Nodeclass<Tree_Node> node = new Nodeclass<>();
                node.setData(tree);
                stack.push(node);
                stack2.push(node);
//                System.out.println(stack2.top().getData().value);
                if (tree.rchild!=null) {
                    tree = tree.rchild;
                }
            }else{
                tree = stack.pop().getData();
                if (tree.lchild!=null) {
                    tree = tree.lchild;
                      }else{
                    tree = stack.pop().getData();
//                    System.out.println(tree.value);
                    tree = tree.lchild;
//                    System.out.println("");
//                    System.out.println(tree.value);
                }
            }
        }
    }

Let's start with the real content:

Binary sort tree BFS

definition:
Binary sort tree is also called binary search tree.
A binary sort tree is either an empty tree or a non empty binary tree with the following characteristics:

  • If the left subtree is not empty, the key values of all nodes on the left subtree are smaller than the key values of the root node
  • If the right subtree is not empty, the key values of all nodes on the right subtree are greater than those of the root node
  • The left and right subtrees are also a binary sorting tree

According to the definition of binary sort tree, there are left subtree node value < root node value < right subtree node value. Therefore, an increasing ordered sequence can be obtained by traversing binary sort tree in middle order.
A simple binary sorting tree model:

Insertion of binary sort tree:

	/**
     * Define the method to add data. This is not a static method. The root node of the tree calls in the node to be inserted
     */
    public void add(Node_tree t){
        //If the val value of t is greater than the val value of this node, add it to the right subtree of this node, provided that the right subtree has no value, otherwise recursion will be performed
        if(t.getVal()>val){
            if(rch==null){
                rch=t;
            }else{
                rch.add(t);
            }
        }else{
            //If the val value of t is smaller than the val value of this node, add it to the left subtree of this node, but only if the left subtree has no value, otherwise perform recursion
            if(lch==null){
                lch=t;
            }else{
                lch.add(t);
            }
        }
    }

Delete binary sort tree:

	 /**
     * Define the deletion method. It is necessary to say that there are two methods for deletion,
     * If you delete a node,
     * You can find the largest number in his left subtree
     * The smallest number of its right subtrees
     * One more question to consider is whether the number found has child nodes,
     *      1,No child nodes, that's the best case,
     *      2,There are child nodes. In this case, there may only be one child node, left or right
     *          You should first connect this child node to the parent of the current node
     *         The method of finding the minimum number of right subtrees
     *
     *  There are three situations for deleting nodes:
     *      1,The node to be deleted has two child nodes
     *      2,The node to be deleted has a child node
     *      3,Node to be deleted has no children
     *      The second and the third can be put together
     *
     */

    public static void del(Node_tree node,int n){
        //Find this node
        Node_tree thisNode = check(node,n);
        //Find the parent of this node
        Node_tree parent = getparent(node,n);
        //1. If this node does not exist, end method
        if(thisNode == null){
            return;
        }
        if(thisNode.getLch()!=null&&thisNode.getRch()!=null){
            //Both left and right child nodes of the node to be deleted have
            Node_tree rm = right_min(thisNode);
            //The father of this successor node
            Node_tree rm_par = getparent(node,rm.getVal());
            //Give the value of this successor node to the node to be deleted
            thisNode.setVal(rm.getVal());
            //Delete this successor node because it must have only a single child node or none
            del_one(rm,rm_par);
            return;

        }else{
//            2. The node to be deleted has a child node
//             3. Node to be deleted has no children
            del_one(thisNode,parent);
        }
    }
    /**
     * Encapsulates a method for deleting a node with or without children
     */
    public static  void del_one(Node_tree thisNode,Node_tree parent){
        //2. The node to be deleted has a child node
//             3. Node to be deleted has no children
        if(thisNode.getVal()>parent.getVal()){
            //The node to be deleted is the right child of the parent node
            if(thisNode.getRch()!=null){
                parent.setRch(thisNode.getRch());
            }else if(thisNode.getLch()!=null){
                parent.setRch(thisNode.getLch());
            }else{
                parent.setRch(null);
            }
        }else{
            //The node to be deleted is the left child of the parent node
            if(thisNode.getRch()!=null){
                parent.setRch(thisNode.getRch());
            }else if(thisNode.getLch()!=null){
                parent.setRch(thisNode.getLch());
            }else{
                parent.setLch(null);
            }
        }
    }

Search of binary sort tree:
Take the above picture as an example to find the node with a value of 9

  1. Find the root node (10), which is smaller than 10, and query to the left subtree
  2. Find the root node (5) of the left subtree, which is larger than 5, and query the right subtree
  3. Found equal, return

Binary balance tree AVL

definition:

In order to avoid the tree height growing too fast and reduce the performance of binary sorting tree, we stipulate that when inserting and deleting binary tree nodes, the absolute value of height difference between left and right subtrees of any node should not exceed 1 at most. Such binary tree is called balanced binary tree
If the height difference between the left subtree and the right subtree of a node is defined as the balance factor of the node, then the value of the balance factor of the node of the balanced two tree can only be -1, 0, 1

1. A balanced binary tree can be an empty tree or a binary tree with the following properties:
2. ① its left and right subtrees are balanced binary trees, and the absolute value of the height difference between the left and right subtrees is not more than 1

The number next to the node in the picture is the value of the balance factor

The basic idea of binary sorting tree to ensure the balance point: whenever A node is inserted (deleted) in the binary sorting tree, first check whether the node on the insertion path is unbalanced due to this operation. If it leads to imbalance, first find out the insertion path and which node A is closest to the insertion point and whose absolute value of the balance factor is greater than 1. Then, for the subtree with A as the root, on the premise of maintaining the characteristics of the binary sort tree, adjust the position relationship of each node to make it reach balance again.
Insert 0

As for rotation, I will introduce it in the following article. I found this in my study article pretty good

Binary balance tree search

The process of searching on the balanced binary tree is the same as that of the binary sorting tree, so the number of keywords compared with the given value in the process of searching does not exceed the depth of the tree. It is assumed that Nh represents the minimum number of nodes in the balance tree with depth H. Obviously, N0=0, N1=1, N2=2, and Nh=N(h-1)+N (h-2) + 1

B tree

definition:

First of all, we need to know the concept of multiple search tree, which is defined as follows:
A multi-way search tree can have more than two children per node, and each node can store multiple elements.
B-tree is a balanced multi-path search tree. The largest number of children in a node is called the Order of B-tree

A m-order B-tree has the following properties:

If the root node is not a leaf node, it has at least two subtrees.
Every non root branch node has k-1 elements and K children, where [m/2] < K ≤ m. Each leaf node n has k-1 elements, in which [m/2] < K ≤ m.
All leaf nodes are at the same level.
All branch nodes contain the following information data (n, A0, K1, A1, K2, A2 , Kn, An), where: ki (I = 1, 2 , n) is the key word, and Ki < ki + 1 (I = 1, 2 ,n-1 ); Ai ( i=0, 2, … , n) is the pointer to the root node of the subtree, and the keywords of all nodes in the subtree indicated by the pointer Ai-1 are less than ki (I = 1,2,...) , n), An refers to all nodes in the subtree whose keywords are greater than Kn, n ([M / 2] - 1 ≤ n ≤ m-1) is the number of keywords (or n+1 is the number of subtrees).

Simulate the creation of a 2-3 tree to help understand
Its nature:

  • A 2-node contains one element and two children (or no children), which is consistent with the binary sorting tree. The left subtree contains less elements than the element, and the right subtree contains more elements than the element. But this 2-node either has two children, or has no children, not only one child.
  • A 3-node contains two elements and three children (or no children). The left subtree, the smaller element, the middle subtree, the larger element and the right subtree are also sorted from small to large. A 3-node has either three children or no children.
  • All leaf nodes of 2-3 tree are on the same level.


Create steps:
1. Create a node with a value of 1

2. Insert 7 to upgrade the node to 3

3. Insert 4 next. You can see that the root node is already 3 nodes. Because it must be balanced, you can only split the root node into 3 2 nodes, as shown below

4. When inserting 9, because 9 is larger than 4, it is inserted to the right, and the node where 7 is can be upgraded to 3, so the insertion result is as follows:

5. Next, insert 15. Since the node where 9 is located is already a 3-node, but its parent node 4 is a 2-node, you can upgrade the node where 4 is located. Because the 3-node must have three children, the nodes where 7 and 9 are located need to be split, as shown below:

6. When inserting 13 and 6, the corresponding nodes can be upgraded, so the insertion results are as follows:

7. When inserting element 5, it is found that the node where 6 is located is already 3 nodes, and the parent node, that is, the root node, is also 3 nodes. At this time, it can only be split again. First of all, the number between 5, 6 and 7 is 6. Let's put it forward. It should be between 4 and 9, as follows:

Because 3 nodes can only have two elements, the root node must also be split. The result is as follows:

8. It can be found that the height of the tree increases after the root node is split. Next, insert 8, 10 and 3. Repeat the steps as follows:

9. Now, it is very simple to insert elements 12, 14 and 2. The results are as follows:

10. Insert 11 at last. It can be found that it is between 10 and 12, and the parent node is also 3 nodes. Therefore, 10 and 12 should be split, 9 and 13 should also be split. 11 and 6 should be upgraded to 3 nodes together. The results are as follows:

Delete B tree:
There are several cases of deletion:

1. Delete leaf node directly
2. Delete the node with children, upgrade or split the child node, and replace the original node (note here that if the depth of the subtree changes after replacement, it will make the whole tree unbalanced, so it is necessary to move the previous node of the subtree down one level under the condition of changing the nature)

Application of B tree:

B-tree is widely used in database and file system.

Its design idea is to gather relevant data together as much as possible, so as to read multiple data at a time and reduce the number of hard disk operations. B-tree algorithm reduces the intermediate process of locating records, thus speeding up the access speed.

If a node can hold 100 values, then the 3-tier B-tree can hold 1 million data. If you change to a binary search tree, you need 20 tiers! Assuming that the operating system reads one node at a time and the root node remains in memory, the B-tree looks up the target value in 1 million data, and only needs to read the hard disk twice.

For example, when mongoDB database is used, single query is faster than Mysql on average (but from the side view, Mysql at least takes about the same average query time)

B + tree

A brother who is more handsome than tree B, and whose query speed is faster than tree B

A B + tree needs to meet the following conditions:

The number of subtrees of nodes is the same as the number of key words (the number of key words in B-tree is one less than that in subtree). The key words of nodes represent the maximum number in subtree, which also contains this data in subtree
The leaf node contains all the data, and conforms to the order of left small and right large

An example:

Briefly summarize the three characteristics of B + tree:

  1. The number of key words is the same as that of subtree
  2. Non leaf node is only used as index, its key and child nodes have duplicate elements
  3. The leaf nodes are connected by pointers

Firstly, the first point need not be specially introduced. In B-tree, the key words of node are used to determine the query interval during query, so the number of key words is one less than that of subtree; in B + tree, the key words of node represent the maximum value of subtree, so the number of key words is equal to the number of subtree.

Second, the keywords of all nodes except the leaf node also exist in its next level subtree, and finally all data are stored in the leaf node.

The maximum key of the root node actually represents the maximum element of the entire B + tree.

Third, the leaf nodes contain all the data, and they are arranged in order. The B + tree uses a linked list to arrange them, so that it is more efficient when querying.

Because the middle node of the B + tree does not contain the actual data, only the maximum data of the subtree and the subtree pointer, so more node elements can be accommodated in the disk page, that is to say * * in the same data situation, the B + tree will make the B tree more "chunky" * * * *, so the query efficiency is faster.

B + tree search will find leaf nodes, which is more stable.

Sometimes it is necessary to query the data within a certain range. Because the leaf node of B + tree is an ordered list, it can only be traversed on the leaf node, instead of traversing the size one by one like B tree.

There are three advantages of B + trees:

Lower level, less IO
Every time you need to query the leaf node, the query performance is stable
Leaf nodes form an ordered list, which is convenient for range query

Creation process of B + tree:
Find a dynamic picture of cowhide, and the creation process of B + tree is clear at a glance

Photo source website: https://blog.csdn.net/luzhensmart/article/details/88617936
Application of B + tree:

mysql uses B + tree as index:

Tags: less MySQL Database MongoDB

Posted on Sun, 07 Jun 2020 01:31:13 -0700 by srikanthiv