Java binary search tree example analysis

Concept

Binary search tree is also called binary sorting tree. It is either an empty tree or has the following properties Binary tree:
1. If its left subtree is not empty, then the values ​​of all nodes on the left subtree are less than the value of the root node.
2. If its right subtree is not empty, the values ​​of all nodes on the right subtree are greater than the value of the root node.
3. Its left and right subtrees are also binary search trees respectively

Direct practice

Preparation work: define a class of tree nodes, and binary search tree classes.

Search function of binary tree

Assume that we have constructed such a binary tree, as shown below

The first question we have to think about is how to find whether a certain value is in the binary tree?

According to the above logic, let’s search method Make improvements.

Insertion operation of searching binary tree

Based on the above logic, let’s write a code to insert a node.

Operation of searching binary tree to delete nodes-difficulty

Let’s analyze again: how curDummy and parentDummy find the “scapegoat” "of.

Total Program - Simulation to Implement Binary Search Tree

class TreeNode{
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val){
        this.val = val;
    }
}


public class BinarySearchTree {
    TreeNode root;

    //在二叉树中 寻找指定 val 值的节点
    // 找到了，返回其节点地址；没找到返回 null
    public TreeNode search(int key){
        TreeNode cur = this.root;
        while(cur != null){
            if(cur.val == key){
                return cur;
            }else if(cur.val < key){
                cur = cur.right;
            }else{
                cur = cur.left;
            }
        }
        return null;
    }
    // 插入操作
    public boolean insert(int key){
        if(this.root == null){
            this.root = new TreeNode(key);
            return true;
        }
        TreeNode cur = this.root;
        TreeNode parent = null;
        while(cur!=null){
            if(key > cur.val){
                parent  = cur;
                cur = cur.right;
            }else if(cur.val == key){
                return false;
            }else{
                parent  = cur;
                cur = cur.left;
            }
        }
        TreeNode node = new TreeNode(key);
        if(parent .val > key){
            parent.left = node;
        }else{
            parent.right = node;
        }
        return true;
    }
    // 删除操作
    public void remove(int key){
        TreeNode cur = root;
        TreeNode parent = null;
        // 寻找 删除节点位置。
        while(cur!=null){
            if(cur.val == key){
                removeNode(cur,parent);// 真正删除节点的代码
                break;
            }else if(cur.val < key){
                parent = cur;
                cur = cur.right;
            }else{
                parent = cur;
                cur = cur.left;
            }
        }
    }
    // 辅助删除方法：真正删除节点的代码
    private void removeNode(TreeNode cur,TreeNode parent){
        // 情况一
        if(cur.left == null){
            if(cur == this.root){
                this.root = this.root.right;
            }else if( cur == parent.left){
                parent.left = cur.right;
            }else{
                parent.right = cur.right;
            }
            // 情况二
        }else if(cur.right == null){
            if(cur == this.root){
                this.root = root.left;
            }else if(cur == parent.left){
                parent.left = cur.left;
            }else{
                parent.right = cur.left;
            }
            // 情况三
        }else{
            // 第二种方法：在删除节点的右子树中寻找最小值，
            TreeNode parentDummy = cur;
            TreeNode curDummy = cur.right;
            while(curDummy.left != null){
                parentDummy = curDummy;
                curDummy = curDummy.left;
            }
            // 此时 curDummy 指向的 cur 右子树
            cur.val = curDummy.val;
            if(parentDummy.left != curDummy){
                parentDummy.right = curDummy.right;
            }else{
                parentDummy.left = curDummy.right;
            }

        }
    }
   // 中序遍历
    public void inorder(TreeNode root){
        if(root == null){
            return;
        }
        inorder(root.left);
        System.out.print(root.val+" ");
        inorder(root.right);
    }

    public static void main(String[] args) {
        int[] array = {10,8,19,3,9,4,7};
        BinarySearchTree binarySearchTree = new BinarySearchTree();
        for (int i = 0; i < array.length; i++) {
            binarySearchTree.insert(array[i]);
        }
        binarySearchTree.inorder(binarySearchTree.root);
        System.out.println();// 换行
        System.out.print("插入重复的数据 9：" + binarySearchTree.insert(9));
        System.out.println();// 换行
        System.out.print("插入不重复的数据 1：" + binarySearchTree.insert(1));
        System.out.println();// 换行
        binarySearchTree.inorder(binarySearchTree.root);
        System.out.println();// 换行
        binarySearchTree.remove(19);
        System.out.print("删除元素 19 ：");
        binarySearchTree.inorder(binarySearchTree.root);
        System.out.println();// 换行
        System.out.print("查找不存在的数据50 ：");
        System.out.println(binarySearchTree.search(50));
        System.out.print("查找存在的数据 7：");
        System.out.println(binarySearchTree.search(7));
    }
}

Performance Analysis

  Insertion and deletion operations must be searched first. Search efficiency represents the performance of each operation in the binary search tree.
 
  For a binary search tree with n nodes, if the probability of searching for each element is equal, the average search length of the binary search tree is the number of nodes in the binary search tree A function of depth, that is, the deeper the node, the more comparisons it takes.
 
  But for the same key code set, if the key codes are inserted in a different order, binary search trees with different structures may be obtained:

If we can ensure that the height difference between the left and right subtrees of the binary search tree does not exceed 1. Try to meet the high balance conditions.
This becomes an AVL tree (highly balanced binary search tree). The AVL tree also has disadvantages: it requires frequent rotation. A lot of wasted efficiency.
At this point, the red-black tree is born to avoid more rotations.

Relationship with java class sets

TreeMap and TreeSet are Map and Set implemented using search trees in java; in fact, red-black trees are used, and red The black tree is an approximately balanced binary search tree, that is, based on the binary search tree, the color and red-black tree properties are verified. Regarding the content of the red-black tree, bloggers will write blogs after learning it.

The above is the detailed content of Java binary search tree example analysis. For more information, please follow other related articles on the PHP Chinese website!