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

This article introduces the relevant knowledge of "the concept and implementation of binary search tree". In the operation of actual cases, many people will encounter such a dilemma, so let the editor lead you to learn how to deal with these situations. I hope you can read it carefully and be able to achieve something!

A binary search tree is a tree that constructs a group of disordered data into an ordered data, and its design idea is similar to that of dichotomy. The efficiency of massive data search is well improved, and the time complexity is reduced from O (n) to O (log (n)) from traversal to binary search.

Concept

Node: each element on the tree.

Root node: a node that has no parent node.

Parent node: a node at the next level of a node.

Child node: the next level node of a node.

Leaf node: a node without a child node.

Sibling node: an adjacent node with the same parent node.

Degree of a node: the number of sub-nodes in a node.

Degree of a tree: the degree of the largest node on a tree.

The level of the node: take the root node as 1, and add 1 for each sub-node level.

Height of the tree: the hierarchy of the largest nodes in the tree.

Characteristics

All the node values of the left subtree are less than, equal to the root node value or empty.

All node values of the left subtree are greater than, equal to the root node value or empty.

The left and right subtrees are also binary sort trees, respectively.

There are no nodes with equal key values.

Construction

To build a binary search tree, we mainly follow several principles: those that are smaller than the current node are on the left, those that are larger are on the right, and those that are equal will not be dealt with. However, combined with the actual business requirements, it can also be placed on the left node or the right node when it is equal, but the rules must be unified, and there cannot be equality between the left and the right. Create a node object:

Package com.ytao.bst;/** * Created by YANGTAO on 2019-11-3 0003. * / public class Node {private Integer value; private Node leftChildren; private Node rightChildren; public Integer getValue () {return value;} public void setValue (Integer value) {this.value = value;} public Node getLeftChildren () {return leftChildren;} public void setLeftChildren (Node leftChildren) {this.leftChildren = leftChildren;} public Node getRightChildren () {return rightChildren } public void setRightChildren (Node rightChildren) {this.rightChildren = rightChildren;} public Node (Integer value) {this.value = value;}}

Implementation of creating a tree:

Package com.ytao.bst;/** * Created by YANGTAO on 2019-11-3 0003. * / public class BuildBST {private Node rootNode = null; public Node build (int [] vals) {/ / traverse all the data, each time you need to start from the root node to find the empty location of the left or right child node and add for (int val: vals) {this.assemble (rootNode, val);} return rootNode } private void assemble (Node node, int val) {/ / create root node if (node = = null) {rootNode = new Node (val);} else {/ / judge if (val) according to the characteristics of left, small and right

< node.getValue()){ Node leftNode = node.getLeftChildren(); // 如果左子结点为空，就添加为当前结点的左结点，否则继续递归下去 if (leftNode == null){ node.setLeftChildren(new Node(val)); }else{ this.assemble(node.getLeftChildren(), val); } }else{ Node rightNode = node.getRightChildren(); // 如果右子结点为空，就添加为当前结点的右结点，否则继续递归下去 if (rightNode == null){ node.setRightChildren(new Node(val)); }else{ this.assemble(rightNode, val); } } } }} 使用[7,5,9,2,11,6]测试是否满足我们创建树的要求： public static void main(String[] args) { int[] vals = {7,5,9,2,11,6}; Node node = new BuildBST().build(vals); System.out.println(new Gson().toJson(node));} 测试结果满足我们要求 { "value": 7, "leftChildren": { "value": 5, "leftChildren": { "value": 2 }, "rightChildren": { "value": 6 } }, "rightChildren": { "value": 9, "rightChildren": { "value": 11 } }}查找 假设从一百万个数字中获取值为88的数据，如果我们使用遍历的方式，最糟的情况就是排在第一百万个位置的时候，需要我们遍历一百万次才能获取到数据，这就是我们最不想遇到的情况。这时将一百万个数据构建成二叉查找树，我们就可通过树快速找到我们想要的数据。 由于设定一百万个数据比较多，这里我们举例当前拥有数据[7,5,9,2,11,6],我们要找出其中的6。 使用循环遍历所有数据的方法，我们需要6次遍历 7->

5-> 9-> 2-> 11-> 6. When using a binary search tree, the structure of the first built binary search tree is shown in the figure:

Start with the root node

Get root node 7, which is not equal to 6, and 65, so continue to find the right child node

Finally, node 6 is obtained to meet the conditions we need. The data traversed is 7-> 5-> 6. Code implementation lookup:

Package com.ytao.bst;/** * Created by YANGTAO on 2019-11-3 0003. * / public class SearchBST {public Node search (Node node, int val) {/ / if the node is empty, there is no matching node if (node = = null) return null; int nodeVal = node.getValue (); / / if the key values on the node are equal, it is the node if (val = = nodeVal) {return node that we are looking for } else if (val

< nodeVal){ // 如果小于结点的值，那么一定在结点的左子树中 return this.search(node.getLeftChildren(), val); }else{ return this.search(node.getRightChildren(), val); } }}插入 二叉查找树的插入规则，必须是要插入后的结点是作为叶子结点。现在向上面的树中插入10，根据上面所分析到的规则，为确保二叉查找树的完整性，最终的插入流程为7->

9-> 11-> 10:

Code implementation:

Package com.ytao.bst;/** * Created by YANGTAO on 2019-11-3 0003. * / public class InsertBST {public void inesrt (Node node, int newVal) {/ / when the node is empty, it is used as the root node if (node = = null) {node = new Node (newVal);} int nodeVal = node.getValue (); / / if it is less than the value of the node, insert it into the left subtree, and if greater than, insert if (newVal) into the right subtree.

< nodeVal){ Node leftNode = node.getLeftChildren(); // 为空时，说明为叶子结点，可插入 if (leftNode == null){ node.setLeftChildren(new Node(newVal)); }else { this.inesrt(leftNode, newVal); } }else if (newVal >

NodeVal) {Node rightNode = node.getRightChildren (); if (rightNode = = null) {node.setRightChildren (new Node (newVal));} else {this.inesrt (rightNode, newVal) }} if else {/ / todo is equal, you can abandon it according to specific business processing, or select a} in the left and right tree to delete it.

Deleting a node can be divided into a variety of situations, among which the main ones are:

Leaf node

Delete the leaf node, delete the leaf node you want to delete directly, such as delete node 6.

The node of a single node.

Deleted node, if there is only one child node, then after the deleted node is deleted, the child node of the node will fill its position, for example, delete node 9.

Nodes with left and right child nodes

In order to express more clearly that the nodes with left and right nodes are deleted, three more nodes are added to the tree. Then delete node 9. The solution here is that after deleting 9, you can fill it with a precursor node or a successor node. The precursor node is the largest node in the left subtree, and the successor node is the smallest node in the right subtree. The scheme to make up for the future node is as follows:

The deleted node is added to the subsequent node:

After the deletion is completed, the following node is added:

Code implementation:

Package com.ytao.bst;/** * Created by YANGTAO on 2019-11-3 0003. * / public class DeleteBST {public Node delete (Node node, int delVal) {/ / is empty, representing the leaf node if (node = = null) {return node;} int nodeVal = node.getValue (); Node leftNode = node.getLeftChildren (); Node rightNode = node.getRightChildren () / / the deleted node, compared with the current node traversed, is less than, greater than or equal to if (delVal)

< nodeVal){ Node tempLeftNode = delete(leftNode, delVal); node.setLeftChildren(tempLeftNode); } else if(delVal >

NodeVal) {Node tempRightNode = delete (rightNode, delVal); node.setRightChildren (tempRightNode) } else {/ / when the deleted node is equal to the current ergodic node / / and the left node is empty, return the right node to make up the deleted position, otherwise return the left node to make up / / explain that the deleted node is a single node if (leftNode = = null) {return rightNode } else if (rightNode = = null) {return leftNode;} / / get the successor node Node minNode = minNode (rightNode) by querying the smallest right node; int minNodeValue = minNode.getValue (); node.setValue (minNodeValue); / / delete the successor node Node tempRightNode = delete (rightNode, minNodeValue) Node.setRightChildren (tempRightNode);} return node;} private Node minNode (Node node) {/ / keep looking for the minimum until the left child node is empty until Node leftNode = node.getLeftChildren (); if (leftNode! = null) return minNode (leftNode); return node;}}

So far, all three of the above have been satisfied.

Summary

The operation of the binary search tree has been introduced above, but in real use, it is necessary to make relevant adjustments in combination with the actual business to meet their own needs, otherwise, all the optimization means are fake. Although the binary search tree is easy to use, but it also has certain requirements, in the case of small amount of data, the use of traversal is more in line with our requirements, so it is generally used in massive data query, used to improve query efficiency.

This is the end of the content of "the concept and implementation of binary search tree". Thank you for your reading. If you want to know more about the industry, you can follow the website, the editor will output more high-quality practical articles for you!

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.