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

### Linked list Link

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”

add to

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

Recommended reading

Don't look down on Log journal , It baffled the architects in our group

Speak true , This new year's gift 【 Interview tips 】 I hate to give you

Graphic, ： Ali's favorite 【 Little rabbit 】RabbitMQ How to cultivate students

I told my girlfriend about encryption algorithm over the weekend , little does one think …