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

This article introduces the relevant knowledge of "what is a binary tree". In the operation of actual cases, many people will encounter such a dilemma. Then 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!

What is a binary tree:

The binary tree has two nodes, the left child node and the right child node.

In the binary tree, the leaf nodes are all at the bottom, and each node except the leaf node has two left and right child nodes. this kind of binary tree is called full binary tree.

The leaf nodes are in the bottom two layers, and the leaf nodes in the last layer are arranged on the left, and the number of nodes in other layers is the largest except the last layer. this kind of binary tree is called complete binary tree.

=

How to store (represent) a binary tree?

1 chain storage: each node has three fields, one of which stores data and the other two pointers to the left and right child nodes.

2Sequential storage method based on array: the root node is stored in the location of subscript 1, the left child node is stored in the location of subscript 2*i=2, and the right child node is stored in the location of 2*i+1=2*2+1=5. So node x stores the location of subscript I in the array, the location of subscript 2 subscript I stores the left child node, and the location of subscript 2*i+1 stores the right child node.

So if the binary tree is a complete binary tree, then using an array to store is the most memory-saving way, because array storage does not need to store extra pointers of left and right child nodes like chain storage. that's why the full binary tree is listed separately.

The traversal of binary tree includes preorder traversal, mid-order traversal and post-order traversal. Traversing a binary tree is actually a recursive process. The time complexity of traversal is O (n).

=

Binary search tree: binary search tree is to achieve fast search, not only can quickly find a data, but also support fast insertion and deletion of a data.

Binary tree search operation: we first take the root node, if it is equal to the data we are looking for, then return, if the data we are looking for is smaller than the value of the root node, then search recursively in the left subtree. If the data you are looking for is larger than the value of the root node, look for it recursively in the right subtree.

Binary tree insertion operation: if the data to be inserted is larger than the node data, and the right subtree of the node is empty, the new data is directly inserted into the location of the right child node. If it is not empty, it traverses the recursive right subtree to find the insertion location. Similarly, if the data to be inserted is smaller than the node value, and the node's left subtree is empty, the new data is inserted into the left subtree, and if it is not empty, traverse the left subtree to find the insertion location.

Delete operation of binary tree: there are three cases: 1 if the node to be deleted does not have a child node, you only need to set the pointer in the parent node to null to the node to be deleted. 2 if the node to be deleted has only one child node, just update the pointer in the parent node to the node to be deleted so that it points to the child node of the node to be deleted. 3 if the node to be deleted has two children, we need to find the smallest node in the right subtree of this node, replace it with the node to be deleted, and then delete the smallest node, because the smallest node certainly does not have a left child node.

Time complexity: whether it is insert, delete or search, the time complexity is proportional to the height of the tree, that is, O (height). This problem translates into how to find the height of a complete binary tree with n nodes. The height of the tree is the maximum number of layers minus one, in order to facilitate calculation, converted to layers to represent. In a complete binary tree, there are 1 node in the first layer, 2 nodes in the second layer, and 4 nodes in the third layer. The number of nodes in the lower layer is twice as many as the previous one, and the k layer contains 2 ^ (kmur1) nodes. The number of nodes in the last layer is between 1 and 2 ^ (Lmur1). The height of the balanced binary tree is close to logn, so the time complexity of the insert and delete search operation is relatively stable, which is O (logn).

=

Red and black tree

Balanced binary tree: the height difference between the left and right subtrees of any node in the binary tree cannot be greater than 1. Complete binary trees, full binary trees are balanced binary trees.

The meaning of balance in a balanced binary tree is to make the whole tree look symmetrical and balanced so that the left subtree is very tall and the right subtree is very short. In this way, the height of the whole tree can be relatively lower, and the corresponding insertion, deletion, search and other operations are more efficient.

Red-black tree definition: 1 root node is black

2 each leaf node is a black empty node, that is to say, the leaf node does not store data

3 No adjacent node can be red at the same time, and the red node is separated by the black node.

4 all paths from that node to its leaf node contain the same number of black nodes.

Why do all projects like to use red and black trees?

In most cases, the operation efficiency of heap and stack is very high, but it can not avoid the degradation of time complexity in extreme cases. Although the probability is small, ALV tree is a highly balanced binary tree, and the search efficiency is very high, but it has both advantages and disadvantages. In order to maintain this height balance, ALV tree has to pay a high price. Every insertion and deletion will be adjusted, which will be more complex and time-consuming. So it is more expensive to use ALV tree for data sets with frequent inserts, deletions and other operations in the heap. On the other hand, the red-black tree only achieves an approximate balance rather than a real balance, so the maintenance cost is lower than the ALV tree. Therefore, the red-black tree insertion, deletion, search and other operations are relatively stable, in the project need to face a variety of situations, so it is more inclined to this stable binary search tree.

This is the end of what is a binary 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.