Shulou(Shulou.com)06/01 Report--

This article mainly explains "java binary search tree use case analysis", interested friends may wish to take a look. The method introduced in this paper is simple, fast and practical. Next let the editor to take you to learn "java binary search tree use case analysis" bar!

Concept

Binary search tree, also known as binary sort tree, is either an empty tree or a binary tree with the following properties:

1. If its left subtree is not empty, then the value of all nodes on the left subtree is less than the value of the root node.

2. If its right subtree is not empty, the value of all nodes on the right subtree is greater than the value of the root node.

3. Its left and right subtrees are also binary search trees.

Direct practice preparation: define the class of a tree node and the class of a binary search tree.

Search function of searching binary tree

Suppose we have constructed such a binary tree, as shown in the following figure

The first question we need to think about is how to find out if a value is in the binary tree.

According to the above logic, let's improve the search method.

Insert operation of searching binary tree

According to the above logic, let's write a code that inserts the node.

Operation of searching binary tree to delete nodes-difficulty

Let's take a look at how curDummy and parentDummy found a scapegoat.

Master program-simulate the 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; / / find the node with the specified val value in the binary tree / / find the node address and return its node address Cannot find return 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;} / / delete operation public void remove (int key) {TreeNode cur = root; TreeNode parent = null; / / find the location of the delete node. While (curving null) {if (cur.val = = key) {removeNode (cur,parent); / / the code that actually deletes the node break;} else if (cur.val < key) {parent = cur; cur = cur.right;} else {parent = cur Cur = cur.left;} / / Auxiliary deletion method: private void removeNode (TreeNode cur,TreeNode parent) {/ / case-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;} / / case II} 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;} / / case 3} else {/ / second method: find the minimum value in the right subtree of the deleted node, TreeNode parentDummy = cur TreeNode curDummy = cur.right; while (curDummy.left! = null) {parentDummy = curDummy; curDummy = curDummy.left;} / / the cur right subtree cur.val = curDummy.val; if (parentDummy.left! = curDummy) {parentDummy.right = curDummy.right pointed to by curDummy at this time } else {parentDummy.left = curDummy.right;}} / / Central order traversal 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 binarySearchTree.inorder (binarySearchTree.root); BinarySearchTree binarySearchTree = new BinarySearchTree (); for (int I = 0; I < array.length; iota +) {binarySearchTree.insert (array [I]);} binarySearchTree.inorder (binarySearchTree.root); System.out.println () / / Wrap System.out.print ("insert duplicate data 9:" + binarySearchTree.insert (9)); System.out.println (); / Wrap System.out.print ("insert non-repeating data 1:" + binarySearchTree.insert (1)); System.out.println (); / / Wrap binarySearchTree.inorder (binarySearchTree.root); System.out.println () / / Wrap binarySearchTree.remove (19); System.out.print ("Delete element 19:"); binarySearchTree.inorder (binarySearchTree.root); System.out.println (); / / Wrap System.out.print ("find non-existent data 50:"); System.out.println (binarySearchTree.search (50)); System.out.print ("find existing data 7:") System.out.println (binarySearchTree.search (7));}}

Performance analysis.

Both    insert and delete operations must be looked up first, and the search efficiency represents the performance of each operation in the binary search tree.

 

   for a binary search tree with n nodes, if the search probability of each element is equal, then the average search length of the binary search tree is a function of the depth of the node in the binary search tree, that is, the deeper the node, the more times of comparison.

 

   but for the same key set, if each key is inserted in a different order, you may get a binary search tree with different structures:

If we can ensure that the height difference between the left and right subtrees of the binary search tree is not more than 1. Try to meet the condition of high balance.

This becomes the AVL tree (a highly balanced binary search tree). The AVL tree also has a drawback: it requires a frequent rotation. Waste a lot of efficiency.

At this point, the red-black tree was born to avoid more rotation.

The relationship with the java class set

TreeMap and TreeSet, that is, Map and Set; realized by using the search tree in java, actually use the red-black tree, while the red-black tree is an approximately balanced binary search tree, that is, based on the binary search tree + color and red-black tree property verification, the content about the red-black tree, and so on, bloggers will write a blog.

At this point, I believe that everyone on the "java binary search tree use case analysis" have a deeper understanding, might as well to the actual operation of it! Here is the website, more related content can enter the relevant channels to inquire, follow us, continue to learn!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.