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

This article mainly explains "what is a binary search tree". Friends who are interested might as well take a look. The method introduced in this paper is simple, fast and practical. Let's let the editor take you to learn what is a binary search tree.

What is a tree?

Tree is a kind of data structure, which is a hierarchical set composed of n (n > = 1) finite nodes. It is called a "tree" because it looks like an upside-down tree, that is to say, it has roots up and leaves down.

The tree is recursive, and any node of the tree and the nodes under the node can be combined into a new tree, so many problems of the tree are accomplished by recursion.

Root node: the top node (root). The root node has no parent node, only child nodes (0 or more can do)

Number of layers: it is generally believed that the root node is the first layer (some also say layer 0), and the height of the tree is the number of layers with the highest number of layers (the number of layers begins to be 1).

Node relationship:

Parent node: the node above which the node is connected

Child node: corresponding to the parent node, upper and lower relationship. The ancestor node is the parent (or ancestor) node of the parent node.

Sibling nodes: nodes that have the same parent node!

The degree of the node: the number of children that the node has (directly connected children are not descendants).

The degree of the tree: the largest of all nodes (the degree of nodes). At the same time, if the node with a degree greater than 0 is a branch node, and the node with a degree equal to 0 is a leaf node (no descendants).

Related properties:

Binary tree

Binary tree is a kind of tree, but it has many applications, so it needs in-depth study. Each node of binary tree has at most two child nodes (but it doesn't have to have two nodes).

The difference between a binary tree and a degree 2 tree:

1. The tree with degree 2 must have more than three nodes (otherwise it will not be called degree 2, it must exist first), and the binary tree can be empty.

2. The degree of a binary tree is not necessarily 2, such as an oblique tree.

3. The binary tree has the distinction between the left and right nodes, while the tree with degree 2 has no distinction between the left and right nodes.

Several special binary trees:

Full binary tree: a full binary tree with height n has (2 ^ n)-1 node

Full binary tree

Complete binary tree: the upper layer is full, and the bottom layer is arranged from left to right.

Complete binary tree

Binary sort tree: the tree inserts the sort according to certain rules (explained in detail in this article).

Balanced binary tree: the depth difference between the left subtree and the right subtree of any node on the tree is less than 1 (explained later).

Properties of binary tree:

1. The properties of binary tree useful tree

2. The number of leaf nodes of non-empty binary tree = the number of nodes with degree 2 + 1. Originally, if the degree of a node is 1. Then there is only one leaf all the time, but if there is a degree 2, in addition to continuing the original node, there will be one more node to be maintained. So in the end, there will be an extra leaf.

3. There are at most 2 ^ (iMel 1) nodes in the non-empty layer I.

4. A tree with a height of h has at most (2 ^ h)-1 node (proportional summation).

Binary trees are generally stored in chains, so memory utilization is higher, but binary trees can also be stored in arrays (often encountered), and the subscripts corresponding to each node can be calculated, so take a complete binary tree from left to right, numbered from top to bottom as shown in the figure:

Position correspondence of binary tree nodes

Binary sort (search) tree concept

With so much bedding in front, let's get down to business and explain and implement a binary sort tree. The binary search tree has the nature of a binary tree and has some rules of its own:

First of all, you need to understand the rules of the binary sort tree: starting from any node, the node value on the left side of the node is always smaller than the value on the right side of the node.

For example, if a binary sort tree is inserted successively into 15, 6, 23, 7, 4, 71, 5, 50, the following sequence will be formed.

A binary sort tree

Construction

A binary sort tree is made up of several nodes (node), and these attributes are required for node: left,right, and value. Where left and right are left and right pointers to the left and right child subtrees, while value is the stored data, which uses the int type.

The node class is constructed as follows:

Class node {/ / Node public int value; public node left; public node right; public node () {} public node (int value) {this.value=value; this.left=null; this.right=null;} public node (int value,node lancer node r) {this.value=value; this.left=l; this.right=r;}}

Now that the node is constructed, other information such as the node is needed to construct a tree. With the experience of linked list construction, it is easy to know that the most important part of a tree is the root root node.

So the structure of the tree is:

Public class BinarySortTree {node root;// Root public BinarySortTree () {root=null;} public void makeEmpty () / empty {root=null;} public boolean isEmpty () / / check whether it is empty {return root==null;} / / various methods}

You can use a diagram to represent this structure:

Main methods

Now that you have constructed a tree, you need to implement the main method, because each node in the binary sort tree can be treated as a tree. So it's time to add node parameters when we create a method (to make it easier to call recursively)

Findmax (), findmin ()

Findmin () finds the smallest node:

Because the minimum of all nodes is to insert to the left, you only need to find the leftmost return, which can be implemented using either a recursive or non-recursive while loop.

Findmax () finds the largest node:

Because all the large nodes are inserted to the right, you only need to find the right-most return, which is consistent with the findmin () method.

The code uses recursive functions

The minimum return value of public node findmin (node t) / / lookup is node. You need .value {if (t==null) {return null;} else if (t.left==null) {return t;} else return (findmin (t.left));} public node findmax (node t) / / find maximum {if (t==null) {return null;} else if (t.right==null) {return t;} else return (findmax (t.right));}

The process of finding the maximum and minimum in a diagram is as follows:

Search process

IsContains (int x)

What this means is to find whether there is a node with a value of x in the binary search tree.

In the specific implementation, look down according to the smaller left side and larger right side of the binary sort tree. If you find a node with a value of x, you will return true. If you cannot find it, you can return false. Of course, you can use recursion or non-recursion in implementation. I use a non-recursive method here.

Public boolean isContains (int x) / / whether there is {node current=root; if (root==null) {return false;} while (current.valueroomroomxinvalid currentcake null) {if (xcurrent.value) {current=current.right;} if (current==null) {return false } / / determine if the ultra-direct return} / / if it is empty at this position will cause the current.value to report no if (current.value==x) {return true;} return false;} insert (int x)

The idea of insertion is similar to the previous isContains (int x), find your own location (empty position) to insert.

But there is something to pay attention to in the specific implementation. We need to go to the node one layer above the position to be inserted. You may wonder why you don't just find the last empty, and then assign the current to current=new node (x). This current is equivalent to pointing to a new node (x) node, which is disconnected from the original tree (the original tree is equivalent to nothing), so you need to determine whether the location is empty through the parent node in advance. Find the appropriate location to point to the newly created node through the left or right node of the parent node to complete the insertion.

Public node insert (int x) / / insert t is a reference to root {node current = root; if (root = = null) {root = new node (x); return root;} while (current! = null) {if (x)

< current.value) { if (current.left == null) { return current.left = new node(x);} else current = current.left;} else if (x >

Current.value) {if (current.right = = null) {return current.right = new node (x);} else current = current.right;}} return current;// where not used}

For example, the tree above inserts nodes with a value of 51.

Insert nodes with a value of 51

Delete (int x)

The deletion operation is a relatively difficult operation to understand, because the point to be deleted may be in different locations, so the specific processing methods are also different. If it is a leaf, it can be deleted directly, and a child node can be replaced with a child node. Those with two child nodes should first find the point whose value is closest to the node to be deleted (the maximum point of the left subtree or the minimum point of the right subtree). Replace the value and recursively delete the replaced node in the subtree. Of course, if there is no specific analysis, please see the following:

The deleted node has no descendants:

You don't need to consider this situation, just delete it (node = null) (all the red dots in the figure are in this way).

The node to be deleted is a leaf node

One child node is empty:

In this case, it is also easy to put the child nodes of the deletion point directly into the deleted location.

There is 1 child on the node to be deleted

The left and right nodes are not empty.

The situation that the left and right child nodes are not empty is relatively complicated, because one of the child nodes cannot directly replace the current node (can not be put down, if the child node also has two children, then one node cannot be placed, for example, replace with the following 71 nodes)

The node to be deleted has two children.

If you fill it with 19 or 71 nodes. Although part of the side can be guaranteed to be larger than the node, it will cause confusion in the merger. For example, if you use 71 instead of 23 nodes. Then you need to consider how to deal with the three nodes (19re50 and 75), as well as whether they are full and whether they have children. This is a complex process and is not suitable for consideration.

So, we want to analyze the attribute of the point we want: if we can guarantee that the point still satisfies the properties of the binary search tree at this location (find the nearest value), which node in the subtree satisfies such a relationship?

Either the rightmost node in the left subtree or the leftmost node in the right subtree is satisfied. We can choose a node to replace the value of the node to be deleted (here, replace it with the rightmost node of the left subtree).

What should I do after this point is replaced? It is very simple, the binary tree uses the recursive idea to solve the problem, and then call the delete function to delete the replacement node in the left subtree.

Replace the value first and then recursively delete 18 nodes in the subtree

The demonstration here is to select the largest node of the left subtree (the rightmost) instead, of course, using the smallest node of the right subtree can also satisfy the size relationship to be deleted here, the principle is the same. The whole process of deletion algorithm is:

Delete proc

The code for this part of the operation is:

Public node remove (int x, node t) / / Delete node {if (t = = null) {return null;} if (x

< t.value) { t.left = remove(x, t.left); } else if (x >

T.value) {t.right = remove (x, t.right);} else if (t.left! = null & & t.right! = null) / / the left and right nodes are not empty {t.value = findmin (t.right). Value;// finds the minimum value on the right to replace t.right = remove (t.value, t.right) } else / / left or right empty {if (t.left = = null & & t.right = = null) {t = null;} else if (t.right! = null) {t = t.right.} else if (t.left! = null) {t = t.leftt;} return t;} return t;} complete code

This complete code was written by the author in his junior year, there may be a lot of omissions or irregularities, just for learning reference, if there are any omissions, please correct them.

The complete code of the binary sort tree is:

At this point, I believe you have a deeper understanding of "what is a binary search tree". You might as well do it in practice. 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.