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

This article shows you what is a tree, binary tree and binary search tree, the content is concise and easy to understand, can definitely brighten your eyes, through the detailed introduction of this article, I hope you can get something.

Speaking of trees, we are no stranger, after all, it is a common thing in daily life. But today's protagonist is not trees, let's talk about trees, binary trees and binary search trees in data structures, and their basic operations!

First, trees and binary trees

1.1 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.

A tree is a data structure that consists of nodes and edges and does not have a ring. Through the following picture, we can more intuitively understand the structure of the tree.

The tree satisfies the property of recursive definition. In other words, if a data structure is a tree structure, then after removing the root nodes, several substructures are also trees, which are usually called subtrees.

In a tree, the names of nodes are different according to the hierarchical relationship between nodes. Let's take a look at the following tree, as shown in the following figure:

The relationship and address of different nodes are as follows:

A node is the superior of B node and C node, then An is the parent node of B and C, and B and C are the child nodes of A.

B and C are the "children" of An at the same time, then B and C can be called sibling nodes.

If A has no parent node, then A can be called the root node.

G, H, I and F nodes have no sub-nodes, so G, H, I and F are called leaf nodes.

When you have a tree, you also need to use depth and layers to describe the location of the nodes in the tree. As shown in the above figure, the hierarchy of the node is calculated from the root node:

The root is the first layer, for example: a

The "child" of the root is the second layer, such as B and C.

The "child" of the root "child" is the third layer, such as D, E, F

And so on, the fourth layer (last layer) is: G, H, I

The maximum number of levels of nodes in a tree is the depth of the tree (called depth, also known as height), so this is a tree with a depth of 4.

1.2 what is a binary tree?

In the big family of trees, there is a special kind of tree that is used at high frequency, which is binary tree. In a binary tree, each node has at most two branches, that is, each node has at most two sub-nodes, which are called left sub-nodes and right sub-nodes respectively.

In the binary tree, there are two of the most special types, as shown in the following figure:

Full binary tree is defined as all nodes have 2 sub-nodes except leaf nodes.

A complete binary tree is defined as the maximum number of nodes in all layers except the last layer, and the leaf nodes in the last layer are arranged on the left.

You may be confused that a complete binary tree doesn't look complete, but why do you call it that? This actually has something to do with the storage of the binary tree. There are two ways to store binary trees, one is pointer-based chain storage, and the other is array-based sequential storage.

Chain storage, that is, like a linked list, each node has three fields, one to store data, and the other two to store pointers to the left and right child nodes, as shown in the following figure:

The sequential storage method is to store the nodes in the array according to the rule, as shown in the following figure, in order to facilitate the calculation, we will agree to put the root node in the position with the subscript 1. Then, node B is stored in the position with subscript 2, node C is stored in the position with subscript 3, and so on.

The reason why it is called complete binary tree is from the perspective of storage space utilization efficiency. For a complete binary tree, only the storage location with the subscript 0 is wasted. If it is an incomplete binary tree, it will waste a lot of storage space.

The incomplete binary tree shown in the following figure needs to reserve positions of 5 and 6. At the same time, it is necessary to retain the positions of the two child nodes 10 and 11 of 5 and the positions of the two sub-nodes 12 and 13 of 6. Such a binary tree does not make full use of the storage space of the array.

2. Traversal of pre-order, middle-order and post-order of trees

Next, we take the binary tree as an example to introduce the operation of the tree, the operation of other types of tree is basically similar to the binary tree.

We can find that the data structures we have learned before are all "one-to-one" relationships, that is, the previous data is connected to only one of the following data, such as linked lists, stacks, queues, and so on. On the other hand, the tree structure is a "one-to-many" relationship, that is, the previous parent node has a connection with the following child nodes.

In a "one-to-one" structure, the lookup has a numeric value, and each piece of data can be traversed directly in order. However, the tree is an one-to-many relationship, so in what order should it be traversed?

In fact, there are three classic methods for traversing a tree, namely, pre-order traversal, mid-order traversal, and post-order traversal. The order here refers to the traversal order of the parent node, the pre-order is to traverse the parent node first, the middle order is to traverse the parent node in the middle, and the post-order is the last traversal of the parent node.

No matter which kind of traversal, it is done through recursive calls. As shown in the following figure:

Preorder traversal, for any node in the tree, first print the node, then preorder traverse its left subtree, and finally preorder traverse its right subtree.

Traversal in the middle order, for any node in the tree, first traverses its left subtree, then prints the node, and finally traverses its right subtree.

Post-order traversal, for any node in the tree, traverses its left subtree, then traverses its right subtree, and finally prints itself.

3. Characteristics of binary search tree

For binary trees without any special properties, apart from the time complexity of traversal, the time complexity of real add and delete operations is O (1). The search operation of tree data is the same as the linked list, which needs to traverse each data to judge, so the time complexity is O (n).

However, when the binary tree has some features (such as binary search tree), we can use these features to reduce the time complexity.

A binary search tree (also known as a binary search tree) has the following characteristics:

In any node in the binary search tree, the value of each node in the left subtree is less than the value of this node, and the value of each node in the right subtree is greater than the value of this node.

In a binary search tree, the situation where the values of two nodes are equal is avoided as much as possible.

By traversing the binary search tree in middle order, you can output an ordered data queue from small to large. As shown in the following figure, the result of traversal in the middle order is 10, 13, 15, 16, 20, 21, 22, 26.

So the binary search tree can simply be thought of as a binary tree sorted according to the rules.

4. Add, delete and delete search operation of binary search tree 3.1 search operation

When performing a lookup operation using a binary lookup tree, we can make the following judgment:

First determine whether the root node is equal to the data you want to find, and if so, return.

If the root node is larger than the data to be found, the lookup action is performed recursively in the left subtree until the leaf node.

If the root node is smaller than the data to be found, the lookup action is performed recursively in the right subtree until the leaf node.

The time complexity of such a binary search can be reduced to O (logn). As for binary search, we will talk about it later in the algorithm section.

3.2 insert operation

It is also easy to perform an insert in a binary lookup tree. Starting from the root node, if the data to be inserted is larger than that of the root node, and the right child node of the root node is not empty, continue to attempt the insert operation in the right subtree of the root node. Until an empty child node is found to perform the insert action.

As shown in the following figure, if you want to insert data X with a value of 14, you need to determine the size relationship between X and the root node:

Since 14 is less than 16, focus on its left subtree and continue to judge the relationship between X and 13.

Because 14 is greater than 13, focus on its right subtree and continue to judge the relationship between X and 15.

Since 14 is less than 15, focus on its left subtree.

Because the left subtree is empty at this time, the insertion action is completed by directly establishing the relationship between the left pointer of 15 nodes and node X.

The time complexity of binary search tree inserting data is O (logn). But that doesn't mean it's more complex than an ordinary binary tree. The reason is that the time complexity here is more wasted on traversing the data to find the location, and the time complexity of performing the insert action is still O (1).

3.3 Delete operation

The deletion operation of the binary search tree will be more complex, because the tree after deleting a node still has to meet the nature of the binary search tree. We are divided into the following three situations.

(1) if the node to be deleted is a leaf node, delete it directly and point the pointer of its parent node to null.

(2) if the node to be deleted has only one child node, it is only necessary to replace the pointer of the child node pointed to by the parent node with the pointer of the child node.

(3) if the node to be deleted has two child nodes, there are two feasible modes of operation.

First, find the largest node in the left subtree of this node and replace the node to be deleted.

Second, find the smallest node in the right subtree of this node and replace the node to be deleted.

What are trees, binary trees and binary search trees? have you learned any knowledge or skills? If you want to learn more skills or enrich your knowledge reserve, you are welcome to follow the industry information channel.

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.