# preface

The previous introduction to learning is mostly linear table related content, the pointer to understand the fact that there is no difficulty. The rules are relatively simple.

Is a data structure tree in data structure, figure again iconic products, (mostly off-the-shelf API can use linear table), because of the difficulty of the tree are bigger than linear table and tree expand sex is very strong, you know the tree, binary tree and binary sort tree and AVL tree, clues to the binary tree, the red and black tree, the number of B, the line segment tree, and so on advanced data structure. However, the binary sort tree is the foundation of everything, so it is important to understand the binary sort tree thoroughly.

# The tree

Refer to the King’s data structure

A binary tree is a tree, and a binary sort tree is a binary tree.

- A tree is
`recursive`

Any node of the tree and the nodes under the node can be combined into one`A new tree`

. And many operations are done recursively. **The root node:**The top node (root) is the root node`There are no precursor nodes`

, has only child nodes (0 or more can be used)**Layer:**The root node is generally considered to be`Level 1`

(Some also say layer 0). The height of the tree is the number of layers of the node with the highest number of layers (starting with 1)**Node relationship:**`The parent node`

: is the node at the upper level of the link node,`Child node:`

Corresponds to the parent node, up and down. while`Ancestor nodes`

Is the parent (or ancestor) node of the parent node.`Sibling nodes:`

Nodes with the same parent!**C:**The degree of a node is the possession of a node`The child node`

And the degree of the tree (maximum) the degree of the node. At the same time, if the degree is greater than 0, theta becomes theta`Branch node`

Theta equals zero, theta equals zero`A leaf node`

(No descendants).

Related properties:

- Number of nodes in a tree = degree of all nodes +1.
- A tree of degree m has at most m^ I -1^ nodes at level I. (i>=1)
- H has a maximum of (m ^h^-1) /(m-1) nodes (
`Sum of geometric sequence`

) - Minimum height of N nodes in m-tree [log~m~(n(m-1)+1)]

# Binary tree

Binary tree is a kind of tree, but more applications, so need to learn in depth. Each node of a binary tree has a maximum of two nodes.

Difference between binary tree and tree of degree 2:

- A tree of degree 2 must have more than three nodes, and the binary tree can be empty.
- Two: the degree of binary trees is not 2: for example, inclined trees.
- Three: a binary tree has left and right nodes, while a tree of degree 2 has no left and right nodes.

**Some special binary trees:**

- Full binary tree. A full binary tree of height n has 2^n^-1 nodes

- Complete binary tree: the top layer is full and the bottom layer is arranged from left to right

- Binary sort tree: the tree inserts sorts according to certain rules.
- Balanced binary tree: The depth difference between the left and right subtrees of any node in the tree is no more than 1.

Properties of binary trees: Compared to trees, properties of binary trees are more specific.

- Number of non-empty binary tree leaf nodes =
`Node tree of degree 2 +1`

Originally, if the degree of a node is 1, there will be a leaf for continuous continuation, but if there is a degree of 2, in addition to continuing the original node, there will be another node to maintain. So to`You end up with an extra leaf`

. - The non-empty i-level has at most 2^ I -1^ nodes.
- A tree of height H has at most 2^ H ^-1 nodes (sum of equal proportions).
`Complete binary tree`

If from left to right, numbered from top to bottom as shown below:

# Binary sort (search) tree

## concept

So much foreshadowing, let’s get down to business, detailed implementation of a binary sorting tree. First, we need to understand the rules of binary sorting trees:

**Starting at any node, the value of the node to the left of the node is always smaller than the value of the node to the right.**For example. A binary sort tree is inserted in sequence`15，6，23，7，4，71，5，50`

This will form the following order

## structure

First, the binary sorting tree is composed of several nodes.

- These attributes are required for Node:
`Left, right, and Value`

. Left and right are left and right Pointers, and value is the stored data.

The node class is constructed as:

```
class node {/ / node
public int value;
public node left;
public node right;
public node(a)
{}public node(int value)
{
this.value=value;
this.left=null;
this.right=null;
}
public node(int value,node l,node r)
{
this.value=value;
this.left=l;
this.right=r; }}Copy the code
```

Now that the nodes are constructed, other information, such as nodes, is needed to construct the tree. With experience in list construction, it’s easy to know that a tree’s primary root node is the root node. So the structure of the tree is:

```
public class BinarySortTree {
node root;/ / root
public BinarySortTree(a)
{root=null; }public void makeEmpty(a)/ / is empty
{root=null; }public boolean isEmpty(a)// Check whether it is null
{return root==null; }// Various methods
}
Copy the code
```

## The main method

- Now that you have constructed a tree, you need to implement the main methods. Because the binary sort tree
**Each node can be viewed as a tree**. So it’s time for us to create the method plus`Node parameter`

(i.e.`The function is valid for each node`

)

### findmax(),findmin()

**Findmin () finds the smallest node:**

- Because the minimum of all nodes is inserted to the left, you only need to find the left-most return.

**Findmax () finds the maximum node:**

- Since all large nodes are inserted to the right, you only need to find the right-most return. The code uses recursive functions

```
public node findmin(node t)// Find the minimum return value is node, the call to view the result requires. Value
{
if(t==null) {return null; }else if(t.left==null) {returnt; }else return(findmin(t.left));
}
public node findmax(node t)// Find maximum
{
if(t==null) {return null; }else if(t.right==null) {returnt; }else return(findmax(t.right));
}
Copy the code
```

### isContains(int x)

So what we’re saying here is we’re looking for x in the binary search tree.

**So let’s say we let’s insert x**, so if there is x we must be looking for inserts`I encounter x in the path`

. Because you can if the points that already exist,**And then in front of it will do the same thing**. In other words, if the front is fixed,`If I do x 1w times, x will always get to this position`

. So we can directly search for comparison!

```
public boolean isContains(int x)// Does it exist
{
node current=root;
if(root==null) {return false; }while(current.value! =x&¤t! =null)
{
if(x<current.value) {current=current.left; }if(x>current.value) {current=current.right; }if(current==null) {return false; }// Check if the superdirect returns inside
}
// Current. Value does not exist if the value is null
if(current.value==x) {return true; }return false;
}
Copy the code
```

### insert(int x)

The idea of insertion is similar to isContains. Find your own position (empty position) to insert. But not quite the same. You might wonder why not just find the last null and assign current to current=new node(x). This is equivalent to pointing to a new node(x) node. And the tree is disconnected, so you need to check in advance if it’s empty, and if it’s empty, you can assign its left or right value.

```
public node insert(int x)// Insert t as 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 = newnode(x); }elsecurrent = current.left; }else if (x > current.value) {
if (current.right == null) {
return current.right = newnode(x); }elsecurrent = current.right; }}return current;// You can't use it
}
Copy the code
```

- Let’s say the top structure
`Insert the 51`

### delete(int x)

The delete operation is a relatively difficult operation to understand. Rule for deleting a node:

- Let’s find this point right here. The point populates the point with points that can be filled by the point’s subtree, then removes the alternative child node starting at the point (calls recursion) and then adds to the last case (only one branch, etc.).
- First you have to find where you remove it, and then you remove that point
`Classification of discussion`

If you have two sons, choose`The far left dot of the son on the right`

And then`The subtree deletes the point substituted`

. If it is a node, determine whether it is left or right empty and place the point`Point to the one that's not empty`

. The one that’s not empty replaces this node. If the left and right sides are empty, then he becomes empty and null is deleted.

**The deleted node has no descendants:**

- You don’t need to consider this case, just delete it. (Red dot en route). On the other
`Node = null`

Can.

**Left node is empty, right node is empty:**

- In this case, it’s easy
`The child node of the delete point is placed at the deleted location`

Can.

**The left and right nodes are not empty**

- The situation is relatively complex. Because of this
`involving`

To a**Strategy problem**.

- If you take
`19 or 71`

Node fill. Although the partial side can be guaranteed to be greater than or less than the node, it will cause`The chaos of the merger`

. For example, if you replace node 23 with node 71. So you need to think about three nodes`,50,75 (19)`

How to deal with, but also consider whether they are full, whether they have children. It’s an extremely complicated process. - First of all,
**We’re going to analyze the properties of the point that we want**: to be able to**Inherits all attributes of the deleted point**. If you take the left node (for example, 17) then first of all**All the right nodes are bigger than him**(The right side is larger than the left). So I’m going to go this way`Pick the largest point`

Make the left half smaller than it. Our analysis`The point with the largest left branch`

It must be`Most right hand side of the subtree`

! - If this node is
**The bottom**It’s easy for us to think. Yes`Replace the value directly, and then delete the lowest point`

Can. but`if`

This node`Have left branch`

. What should we do? - It’s not too hard to analyze, just recursively. Let’s delete this node, and we can use
`Satisfies node replacement`

. What are the consequences?

- I have 19 extra nodes that I used,
**To convert the**In the left subtree`19`

The point! The problem then becomes the problem of deleting nodes, looking for alternatives in the left subtree`19`

At this point.

Therefore, the entire deletion algorithm flow is as follows:

```
public node remove(int x, node t)// Delete a 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;// Find the minimum substitution on the right
t.right = remove(t.value, t.right);
} else // Either left or right is 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.left;
}
return t;
}
return t;
}
Copy the code
```

## The complete code

The complete code of binary sort tree is:

```
packageBinary tree;import java.util.ArrayDeque;
import java.util.Queue;
import java.util.Stack;
public class BinarySortTree {
class node {/ / node
public int value;
public node left;
public node right;
public node(a) {}public node(int value) {
this.value = value;
this.left = null;
this.right = null;
}
public node(int value, node l, node r) {
this.value = value;
this.left = l;
this.right = r;
}
}
node root;/ / root
public BinarySortTree(a) {
root = null;
}
public void makeEmpty(a)/ / is empty
{
root = null;
}
public boolean isEmpty(a)// Check whether it is null
{
return root == null;
}
public node findmin(node t)// Find the minimum return value is node, the call to view the result requires. 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));
}
public boolean isContains(int x)// Does it exist
{
node current = root;
if (root == null) {
return false;
}
while(current.value ! = x && current ! =null) {
if (x < current.value) {
current = current.left;
}
if (x > current.value) {
current = current.right;
}
if (current == null) {
return false;
} // Check if the superdirect returns inside
}
// Current. Value does not exist if the value is null
if (current.value == x) {
return true;
}
return false;
}
public node insert(int x)// Insert t as 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 = newnode(x); }elsecurrent = current.left; }else if (x > current.value) {
if (current.right == null) {
return current.right = newnode(x); }elsecurrent = current.right; }}return current;// You can't use it
}
public node remove(int x, node t)// Delete a 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;// Find the minimum substitution on the right
t.right = remove(t.value, t.right);
} else // Either left or right is 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.left;
}
return t;
}
returnt; }}Copy the code
```

# conclusion

- Here we first learned the basic structure of trees, binary trees, and binary search trees. For binary search trees
`Insert lookups are easier`

Understand but implement the function to pay attention to the argument reference and so on. It needs serious consideration. - The more difficult thing is to delete binary trees, using a recursive idea, to find special cases and common cases, recursion to some extent
`Problem transformation`

(**Turn to the same problem, the scope is reduced**) Need to think. - The following will also introduce the three-order traversal of binary search trees (
`Recursive and non-recursive`

). And sequence traversal. Friends in need, please continue to pay attention. In addition, my data structure column welcomes ward rounds. ! - If the
`Back end, crawler, data structure algorithm`

Welcome to pay attention to my personal public account communication:`bigsai`

. reply**The crawler**.**The data structure**Wait for a beautiful information.