Hello everyone , I'm Xiaoyu .

During this period, I also met a lot of big men in the circle , What we can see from them is that they have a successful career , Emotional happiness , They're young . Can not help but sigh , Young people have such a plan , Become the winner of life in other people's eyes . I don't think you should pay too much attention to horizontal comparison with others , More should be compared with their own vertical . Because there are more ordinary people , We're all working for 、 People who work hard in life . This sentence is more to give some attention to my number , Now I'm a little anxious partner , You have to believe that as long as you work hard , Nothing is impossible .

Today I'm going to introduce some common data structures , Mainly for some just started data structure and need to review the data structure of the system partners ！ As programmers, we , Dealing with different data every day . So you really know the data structure ？

Xiaoyu from the definition of each data structure 、 characteristic 、 Use and method implementation to introduce to you . Each is illustrated with pictures and texts , Help you to better grasp the corresponding knowledge . If you're confused about this , Come and have a look ~

### Stack  stack

Stack （stack） Is to restrict the insertion and deletion of tables that can only be performed in one location , This position is the end of the table , It's called the top of the stack （top）. It's last in, first out （LIFO） Of . The basic operation of the stack is push（ Into the stack ） and pop（ Out of the stack ） Two kinds of , The former is equivalent to inserting , The latter is equivalent to deleting the last element . ### queue  queue

A queue is a special kind of linear table , What's special about this is that it's only allowed at the front of the table （front） Delete operation , And at the back end of the table （rear） Insert operation , Like the stack , A queue is a linear table with restricted operations . The end of the insertion operation is called the tail of the queue , The end of the delete operation is called the queue head . A linked list is a data structure , Same as array . such as ,Java We use ArrayList, The principle is array . and LinkedList The realization principle of is linked list . The chain list is not efficient in loop traversal , but The advantages of insertion and deletion are obvious . ### Hash table Hash Table

Hash table （Hash table, Also called hash table ） It's a search algorithm , With the list 、 Tree algorithm is different from , Hash table algorithm does not need to do a series of search and keyword search （ A keyword is the value of a data item in a data element , To identify a data element ） Comparison operation of .

Hash table algorithm wants to be able to do as much as possible without any comparison , You can get the data elements you are looking for in one access , Therefore, the storage location of the data element and its keyword must be specified （ You can use key Express ） Build a A definite correspondence , Make each keyword correspond to a unique storage location in the hash table . So in the search , Just find the position of the given keyword in the hash table according to the corresponding relationship . This correspondence is called a hash function ( You can use h(key) Express ).

The methods used to construct hash functions are ：

direct addressing ： Take the key or a linear function value of the key as the hash address . namely ：h(key) = key or h(key) = a * key + b, among a and b Constant .

Digital analysis ： Digital analysis is also called digital selection , The method is to collect all possible key values , Line up , Analyze every bit of the key value , Select a number of evenly distributed bits to form a hash address .

The square method ： Take the middle digits after the square of the keyword as the hash address .

Folding method ： Divide keywords into parts with the same number of digits , Then take the sum of these parts as the hash address .

Division and remainder ： The keyword is not longer than the hash table m Number of numbers p The remainder after division is the hash address , namely ：h(key) = key MOD p p ≤ m

Random number method ： Choose a random function , Take the random function value of the keyword as its hash address , namely ：h(key) = random(key) ### Sort binary trees

First of all, if every node of a normal binary tree satisfies ： All nodes in the left subtree are less than their root nodes , And the value of all nodes in the right subtree is greater than the value of its root node , Then such a binary tree is a sort binary tree .

The insert

First, start from the root node and find the location you want to insert （ The parent of the new node ）; The specific process is ： Compare the new node with the current node , If it is the same, it means that it already exists and cannot be inserted repeatedly ; If it is smaller than the current node , Go to the left subtree to find , If the left subtree is empty, the current node is the parent node to be found , The new node can be inserted into the left subtree of the current node ; If it is larger than the current node , Then go to the right subtree to find , If the right subtree is empty, the current node is the parent node to be found , The new node can be inserted into the right subtree of the current node . Delete operation

There are three main types of deletion operations , That is, the node to be deleted has no children , The node to be deleted has only one child , The node to be deleted has two children .

1. For the node to be deleted, there is no child node that can be deleted directly , That is, let its parent node leave the child node empty .

2. There is only one child node for the node to be deleted , Then replace the node to be deleted with its child .

3. There are two child nodes for the node to be deleted , First find the replacement node of this node （ The smallest node in the right subtree ）, Then replace the node to be deleted with the replacement node , Then delete the replacement node . Query operation

The main process of search operation is ： Compare with the root node first , If it's the same, go back to , If it is less than the root node, it will look up recursively in the left subtree , If it is larger than the root node, it will recursively search in the right subtree . So it's easy to get the maximum... In the sorted binary tree （ The deepest child node on the right ） And minimum （ The deepest child node on the left ） value .

### Red and black trees

R-B Tree, The full name is Red-Black Tree, Also known as “ Red and black trees ”, It's a special binary search tree . Every node of the red black tree has The memory bit represents the color of the node , It can be red (Red) Or black (Black).

Properties of red-black trees

1. Each node is either black , Or red .

2. The root node is black .

3. Every leaf node （NIL） It's black .[ Be careful ： Here is the leaf node , It means empty (NIL or NULL) Leaf node of ！] （4） If a node is red , Then its child nodes must be black .

4. All paths from a node to its children contain the same number of black nodes .

left-handed

Yes x To carry on the left-hand , signify , take “x The right child ” Set to “x The father node of ”; namely , take x It becomes a left node (x Become for z The left child )！. therefore , In the left “ Left ”, signify “ The node being rotated will become a left node ”. ```LEFT-ROTATE(T, x)
y ← right[x] //  Premise ： It is assumed that  x  The right child of  y. Let's start the formal operation
right[x] ← left[y] //  take  “y  The left child ”  Set to  “x  The right child ”, namely   take β Set to  x  The right child
p[left[y]] ← x //  take  “x”  Set to  “y  The father of the left child ”, namely   take β My father is set as  x
p[y] ← p[x] //  take  “x  Father ”  Set to  “y  Father ”
if p[x] = nil[T]
then root[T] ← y //  situation  1： If  “x  Father ”  It's an empty node , Will  y  Set as root
else if x = left[p[x]]
then left[p[x]] ← y //  situation  2： If  x  It's the left child of its parent node , Will  y  Set to “x  Parent node
The left child ”
else right[p[x]] ← y //  situation  3：(x  It's the right child of its parent )  take  y  Set to “x  The right child of the parent node of
Son ”
left[y] ← x //  take  “x”  Set to  “y  The left child ”
p[x] ← y //  take  “x  Parent node ”  Set to  “y``` Right hand

Yes x To carry on the right hand , signify , take “x The left child ” Set to “x The father node of ”; namely , take x It becomes a right node (x Become for y The right child )！ therefore , On the right “ Right ”, signify “ The node being rotated will become a right node ”. ``` RIGHT-ROTATE(T, y)
x ← left[y] //  Premise ： It is assumed that  y  The left child of  x. Let's start the formal operation
left[y] ← right[x] //  take  “x  The right child ”  Set to  “y  The left child ”, namely   take β Set to  y  The left child
p[right[x]] ← y //  take  “y”  Set to  “x  The father of the right child ”, namely   take β My father is set as  y
p[x] ← p[y] //  take  “y  Father ”  Set to  “x  Father ”
if p[y] = nil[T]
then root[T] ← x //  situation  1： If  “y  Father ”  It's an empty node , Will  x  Set as root
else if y = right[p[y]]
then right[p[y]] ← x //  situation  2： If  y  It's the right child of its parent , Will  x  Set to “y  My father's Day
The left child of the dot ”
else left[p[y]] ← x //  situation  3：(y  It's the left child of its parent node )  take  x  Set to “y  The left child of the parent node of
Son ”
right[x] ← y //  take  “y”  Set to  “x  The right child ”
p[y] ← x //  take  “y  Parent node ”  Set to  “x”```

First step : Look up the red black tree as a binary tree , Insert the node into .

The second step ： Coloring the inserted node to " Red ". Depending on the parent of the inserted node , Can be " When node z Colored as a red node , And insert the binary tree " There are three situations to deal with .

When the inserted node is the root node time , Paint this node black directly .

When the parent of the inserted node is black , Nothing needs to be done . After the node is inserted , It's still the red and black tree .

When the parent of the inserted node is red . In this case , The inserted node must have a non empty grandparent node ; Go further , The inserted node must also have an uncle node ( Even if the uncle node is empty , We also see it as being , An empty node itself is a black node ). After understanding this , We rely on " Uncle node ", Divide this situation into 3 In this case (Case). The third step : Through a series of Rotation or coloring, etc , Make it a red and black tree again .

Delete

First step ： Look up the red black tree as a binary tree , Delete node .

This sum " The method of deleting nodes in a regular binary search tree is the same ". branch 3 In this case ：

1.  Deleted node has no son , This is the leaf node . that , Delete the node directly OK 了 .

2.  The deleted node has only one son . that , Delete the node directly , And replace its position with the only child of the node .

3.  The deleted node has two sons . that , First, find out its subsequent nodes ; And then put “ The content of its successor node ” Copy to “ The content of this node ”; after , Delete “ Its successor node ”.

The second step ： adopt " Rotate and recolor " Wait a series to fix the tree , Make it a red and black tree again .

because " First step " After deleting the node in , It may violate the characteristics of the red black tree . So you have to go through " Rotate and recolor " To fix the tree , Make it a red and black tree again . Choose recolor 3 In this case .

When x yes “ red + black ” node , Put... Directly x Set to black , end . At this time, all the properties of the red black tree are restored .

When x yes “ black + black ” node , And x It's a root , Don't do anything? , end . At this time, all the properties of the red black tree are restored .

When x yes “ black + black ” node , And x It's not a root , This situation can be divided into 4 Seed situation . this 4 The seeds are shown in the table below ： ### B-TREE

B-tree Also called balanced multiple search tree . A tree m Step B-tree (m Fork tree ) Its characteristics are as follows （ among ceil(x) It's a function with an upper bound ）：

1. Every node in the tree has at most m A child ;

2. Except for root and leaf nodes , Every other node has at least ceil(m / 2) A child ;

3. If the root node is not a leaf node , At least 2 A child （ A special case ： No child's roots , That is, the root node is the leaf node , The whole tree has only one root node ）;

4. All leaf nodes appear in the same layer , Leaf node does not contain any keyword information ( It can be regarded as an external node or a node with query failure , In fact, these nodes do not exist , The pointers to these nodes are null);

5. Each non terminal node contains n Keyword information ：(n,P0,K1,P1,K2,P2,……,Kn,Pn). among ：

`Ki` (i=1…n) Keyword , And the keywords are sorted in order K(i-1)< Ki.

`Pi` To point to the root of a subtree , And the pointer P(i-1) The keywords pointing to all nodes of the sub tree species are less than Ki, But they are greater than K(i-1).

Number of keywords `n` Must satisfy ：ceil(m / 2)-1 <= n <= m-1 A tree m Step B+tree and m Step B-tree The difference is ：

1. Yes n The knot of Kezi tree contains n Key words ;(B-tree yes n Kezi tree has n-1 Key words )

2. All the leaf nodes contain all the keyword information , And a pointer to the record containing these keywords , And the leaf node itself is linked in order of the size of the keyword .(B-tree The leaf node of does not include all the information to be searched )

3. All non terminal nodes can be regarded as index parts , The node contains only its subtree, and the root node contains the largest （ Or the smallest ） keyword .(B-tree The non terminal node of the also contains the valid information to be searched ) ### Bitmap

The principle of bitmap is to use a bit To identify whether a number exists , Use a bit To store a piece of data , So this can It saves a lot of space .bitmap It's a very common data structure , For example, for Bloom Filter in ; For sorting of non repeating integers and so on .bitmap It's usually based on arrays , Each element in an array can be thought of as a series of binary numbers , All elements make up a larger binary set .

for example ：unsigned int bit[N], In this array , Can be stored N * sizeof(int) * 8 Data , But the biggest number is N * sizeof(int)  * 8 - 1. If , The range of data we want to store is 0-15, Then we just need to make N=1, So you can put the data in . Here's the picture ： The data is 【5,1,7,15,0,4,6,10】, Then the case of saving in this structure is 