Binary tree:
Binary treeBaike.baidu.com/item/%E4%BA…
Dynamically generated websites:www.cs.usfca.edu/~galles/vis…
features
1. As shown in the figure, we can see the characteristics of binary tree: if the value of the new node is smaller than that of the parent node, it will be placed on the left of the parent node and on the right of the parent node.
-
For example, the value 0009 is found to be smaller than 0010 and placed on the left, and the left node is larger than 0006 and placed on the right of 0006
-
But there is a situation where the binary tree behaves like a linear table.
-
Example 1:
-
Example 2:
2. If a node is deleted, all its children are attached to the parent node of the node. Not all of them.Copy the code- If the value is greater than the parent node, search for the left and smaller than the parent node search for the right, and so on. If the tree structure is a linear table, the query effect is the same as that of a linear table. In general, the query efficiency is higher than that of linear tables.
Red black tree (also called balanced binary tree)
Features: 1. On the basis of binary tree will do tree balance. 2. Each node stores one index
2 to the n is equal to the amount of data
When the data pairs are larger, the height of the tree is higher
In this way, the height of the tree is controlled to reduce the number of queries and improve the efficiency of queries
B Tree
B+ tree (multi-fork equilibrium tree)
baike.baidu.com/item/B+%E6%…
1170 nodes can fit under one node [maximum]
Total memory capacity = 1170117016; 1170 to the n minus 1 times 16
This article is from: Song Wenchao Super, exclusive platform CSDN, SegmentFault, Jianshu, OSChina, Nuggets, please indicate the source of reprint.