MindMap Gallery Data structure search mind map
The mind map of Chapter 7 of Data Structure mainly includes basic concepts, order and halves, tree search, B-tree and B-tree, comparison between B-tree and B-tree, hash search, etc.
Edited at 2022-10-23 16:33:27Avatar 3 centers on the Sully family, showcasing the internal rift caused by the sacrifice of their eldest son, and their alliance with other tribes on Pandora against the external conflict of the Ashbringers, who adhere to the philosophy of fire and are allied with humans. It explores the grand themes of family, faith, and survival.
This article discusses the Easter eggs and homages in Zootopia 2 that you may have discovered. The main content includes: character and archetype Easter eggs, cinematic universe crossover Easter eggs, animal ecology and behavior references, symbol and metaphor Easter eggs, social satire and brand allusions, and emotional storylines and sequel foreshadowing.
[Zootopia Character Relationship Chart] The idealistic rabbit police officer Judy and the cynical fox conman Nick form a charmingly contrasting duo, rising from street hustlers to become Zootopia police officers!
Avatar 3 centers on the Sully family, showcasing the internal rift caused by the sacrifice of their eldest son, and their alliance with other tribes on Pandora against the external conflict of the Ashbringers, who adhere to the philosophy of fire and are allied with humans. It explores the grand themes of family, faith, and survival.
This article discusses the Easter eggs and homages in Zootopia 2 that you may have discovered. The main content includes: character and archetype Easter eggs, cinematic universe crossover Easter eggs, animal ecology and behavior references, symbol and metaphor Easter eggs, social satire and brand allusions, and emotional storylines and sequel foreshadowing.
[Zootopia Character Relationship Chart] The idealistic rabbit police officer Judy and the cynical fox conman Nick form a charmingly contrasting duo, rising from street hustlers to become Zootopia police officers!
Find
basic concept
lookup table
Static lookup table: only lookup operations are required
Dynamic lookup table: In addition to lookup, you also need to add/delete data elements
Efficiency evaluation of search algorithms
Average search length ASL (average number of keyword comparisons across all searches)
ASL is usually considered in two cases: successful search and failed search.
order and halves
sequential search
Sequential search, also called "linear search", is usually used in linear tables. Algorithm idea: search from head to jio one by one (or vice versa is OK)
Search efficiency analysis
Time complexity: O(n)
half search
Half search, also known as "binary search", is only applicable to ordered sequence lists.
Find decision tree
The decision tree of the binary search is a balanced binary sorting tree (left < middle < right)
If the lookup table has n keywords, then there are n 1 failed nodes.
Block search
Block search, also called index sequence search, the algorithm process is as follows: ① Determine the block to which the record to be searched belongs in the index table (can be sequential or halved) ② Search sequentially within the block
Search efficiency analysis: Assume that the average search lengths of index search and intra-block search are Li and Ls respectively, then the average search length of block search is ASL=Li Ls
Use sequential search to look up the index table,
Use half search to look up the index table,
When performing a half search on the index table, if the index table does not contain the target keyword, the half search will eventually stop at low>high, and the search will be in the block pointed to by low.
tree search
Binary sorting tree
definition
Left subtree node value < root node value < right subtree node value
Perform in-order traversal to obtain an increasing ordered sequence.
Different keyword sequences may result in the same binary sorting tree.
Find
If the tree is not empty, compare the target value with the value of the root node: if they are equal, the search is successful; If it is less than the root node, search on the left subtree, otherwise search on the right subtree. If the search is successful, the node pointer is returned; if the search fails, NULL is returned.
Worst space complexity O(h)
insert
If the original binary sorting tree is empty, insert the node directly; otherwise, if the key k is less than the root node value, insert it into the left subtree; if the key k is greater than the root node value, insert it into the right subtree
Worst space complexity O(h)
delete
The deleted node is a leaf and is deleted directly.
If the deleted node has only left or only right subtree, replace its position with its subtree.
The deleted node has left and right subtrees
It can be replaced by its successor node, and then the successor node can be deleted.
Or replace it with its predecessor node, and then delete the predecessor node.
Search efficiency analysis
Depends on the height of the tree, best O(log n), worst O(n)
Calculation of average search length
Find successful cases
Find the failure situation (need to supplement the failure node)
balanced binary tree
Balanced binary tree: suitable for scenarios where search is the main task and insertion/deletion is rare
The depth difference between the left subtree and the right subtree of any node in the tree does not exceed 1.
Insertion: Will cause the tree to be unbalanced
Adjust imbalance
Find the minimum unbalanced subtree and adjust it. Remember the root of the minimum unbalanced subtree as A.
LL: Inserting into the left subtree of A's left child causes A to be unbalanced, and the left child of A is rotated to the right.
RR: Inserting into the right subtree of A's right child causes A to be unbalanced, and the right child of A is left top-rotated.
LR: Inserting into the right subtree of A's left child causes A to be unbalanced. The right child of A's left child is rotated first to the left and then to the right.
RL: Inserting into the left subtree of A's right child causes A to be unbalanced. The left child of A's right child is first rotated right and then left.
Search efficiency analysis
Test point: How many nodes does a balanced binary tree with height h have at least - recursive solution
The maximum depth of a balanced binary tree is O(log n), and the average search length/time complexity of the search is O(log n).
delete
①Delete nodes (the method is the same as "binary sorting tree") ·If the node to be deleted is a leaf, delete it directly. ·If the deleted node has only one subtree, use the subtree to replace the deleted location ·If the deleted node has two subtrees, replace it with the predecessor (or successor) node and convert it into deletion of the predecessor (or successor) node.
② Go all the way north to find the smallest unbalanced subtree. If you can’t find it, end it.
③Find the tallest son or grandson under the smallest unbalanced sub-tree
④Adjust the balance (LL/RR/LR/RL) according to the position of the grandson. The grandson is in LL: the son rotates right. ·The grandson is in RR: The son has a left-sided spin ·Sun Tzu is in LR: Sun Tzu first turns left, then right. · Sun Tzu is in RL: Sun Tzu first turns right, then left.
⑤ If the imbalance is conducted upward, continue ② Rotation of the minimally unbalanced subtree may cause the tree to become shorter, resulting in an imbalance in the upper ancestors (imbalance is propagated upward)
Balanced binary tree deletion operation time complexity = O(log2n)
red black tree
Red-black tree: suitable for frequent insertion and deletion scenarios, more practical
The requirements for a red-black tree: the left root is right, the roots and leaves are black; not red, the black path is the same
Requirements for red-black trees
①Each node is either red or black
②The root node is black
③Leaf nodes (external nodes, NULL nodes, failed nodes) are all black
④ There are no two adjacent red nodes (that is, the parent node and child node of the red node are both black)
⑤For each node, the simple path from the node to any leaf node contains the same number of black nodes.
nature
The longest path from the root node to the leaf node is not greater than 2 times the shortest path
The height of a red-black tree with n internal nodes is h≤ 2log2(n+1)
Red-black tree search operation time complexity = O(log2n) search efficiency is the same order of magnitude as AVL tree
Find
① First search, determine the insertion position (the principle is the same as the binary sort tree), and insert the new node
②The new node is the root - dyed black
②The new node is not the root - dyed red
If the red-black tree definition is still satisfied after inserting the new node, the insertion ends
If the red-black tree definition is not satisfied after inserting a new node, it needs to be adjusted so that it meets the red-black tree definition again.
If it's Uncle Hei: rotate and dye
Type LL: right unirotation, father changes father, dyeing
Type RR: left monorotation, father changes father, dyeing
LR type: left and right double rotation, son to father, dyeing
RL type: right and left double rotation, son to father, dyeing
If it is Uncle Hong; dyeing makes it new: Uncle dyes and turns into a new node
delete
Important test points
①The time complexity of red-black tree deletion operation = O(log2n)
②The processing method of deleting nodes in red-black tree is the same as "deletion of binary sorting tree"
③ After pressing ② to delete the node, the "red-black tree characteristics" may be destroyed. At this time, the color and position of the node need to be adjusted to make it meet the "red-black tree characteristics" again.
It’s too difficult to delete. I bet you he won’t take the exam.
B-tree and B-tree
B-tree
B-tree, also known as multi-way balanced search tree, the maximum number of children of all nodes in the B-tree is called the order of the B-tree, usually represented by m.
A B-tree of order m is either an empty tree or an m-ary tree that satisfies the following characteristics:
1) Each node in the tree has at most m subtrees, that is, it contains at most m-1 keywords.
2) If the root node is not a terminal node, there are at least two subtrees.
3) All non-leaf nodes except the root node have at least "ml2] subtrees, that is, they contain at least "m/2]-1 keywords.
4) The structure of all non-leaf nodes is as follows: Among them, Ki (i = 1, 2.., n) is the keyword of the node and satisfies K1<K2<...<Kn; Pi (i=0,1., n) points to the root node of the subtree Pointer to point, and the keys of all nodes in the subtree pointed to by pointer Pi-1 are less than Ki, and the keys of all nodes in the subtree pointed to by Pi are greater than Ki,n([m/2]-1≤ n≤m -1) is the number of keywords in the node.
5) All leaf nodes appear at the same level and carry no information (can be regarded as external nodes or search failure nodes similar to the binary search decision tree. In fact, these nodes do not exist and point to these nodes. pointer is null).
The core characteristics of m-order B-trees:
1) The number of subtrees of the root node ∈ [2, m], and the number of keywords ∈ [1, m-1]. The number of subtrees of other nodes ∈ [[m/2], m]; the number of keywords ∈ [[ml21-1, m-1]
2) For any node, all its subtrees have the same height
3) Keyword value: subtree O<keyword 1<subtree 1<keyword 2<subtree 2<....(analogous to binary search tree left<middle<right)
Question: What are the minimum height and maximum height of an m-order B-tree containing n keywords?
insert
Determine the insertion position through "search" (must be at the terminal node)
If the number of node keywords after insertion does not exceed the upper limit, no other processing is required.
If the number of keywords exceeds the upper limit after insertion, the middle element of the current node needs to be placed in the parent node, and the current node is split into two parts; this operation will result in the number of keywords in the parent node being 1. If the parent node is key If the number of characters also exceeds the upper limit, it needs to be split further; The split of the root node will cause the height of the B-tree to be +1.
delete
non-terminal node keyword
Replace its position with its direct predecessor or direct successor, which translates into deletion of the "terminal node"
Immediate predecessor: the "lower-right" element in the subtree pointed to by the pointer to the left of the current keyword
Direct successor: the "lower-left" element in the subtree pointed to by the pointer to the right of the current keyword
terminal node Keywords
After deletion, the number of node keywords does not fall below the lower limit and does not require any processing.
below the lower limit
If the right brother is enough to borrow, then the successor of the current node and the successor of the successor will replace the vacancy in turn.
If the left brother has enough to borrow, then the predecessor of the current node and the predecessor of the predecessor will be used to replace the vacancy.
If the left (right) brothers are not enough to borrow, it needs to be merged with the keywords in the parent node and the left (right) brothers. After merging, the number of parent node keywords will be -1, and merging may need to continue.
B-tree
To meet the conditions
1) Each branch node has at most m subtrees (child nodes).
2) The non-leaf root node has at least two subtrees, and each other branch node has at least "m/2] subtrees - which can be understood as: the pursuit of "absolute balance", that is, the height of all subtrees must be the same
3) The number of subtrees of a node is equal to the number of keywords.
4) All leaf nodes contain all keywords and pointers to corresponding records. The keywords are arranged in size order in the leaf nodes, and adjacent leaf nodes are linked to each other in size order.
5) All branch nodes only contain the maximum value of the keywords in each of its child nodes and pointers to its child nodes.
In the B-tree, no matter whether the search is successful or not, you must eventually reach the bottom node.
m-order B-tree
1) n keywords in the node correspond to n 1 subtrees
2) The number of keywords of the root node n=[1, m]The number of keywords of other nodes n∈[ [m/2], m]
3) In the B-tree, the keywords contained in each node are not repeated.
4) In the B-tree, leaf nodes contain information, and all non-leaf nodes only serve as indexes. Each index item in a non-leaf node only contains the maximum keyword of the corresponding subtree and a pointer to the subtree. The storage address of the record corresponding to this keyword is not included.
4) The nodes of the B-tree all contain the storage address of the record corresponding to the keyword.
Comparison between B-tree and B-tree
B-tree
Analogy: Evolution of Binary Search Tree -> m-fork search tree
Keywords and bifurcation: n keywords correspond to n 1 bifurcations (subtrees)
Information contained in nodes: All nodes contain recorded information
Search method: Sequential search is not supported. When the search is successful, it may stop at any node in the search mode, and the search speed is "unstable"
B-tree
Analogy: Evolution of block search-->Multi-level block search
Keywords and forks: n keywords correspond to n forks
Information contained in nodes: Only the lowest leaf node contains recorded information (can make the tree shorter)
Search method: Supports sequential search. Whether the search succeeds or fails, it will reach the bottom node, and the search speed is "stable"
Same point
In addition to the root node, there are at least "m/2] branches (to ensure that the node is not too "empty") and the subtree of any node must be the same height (to ensure "absolute balance")
Hash lookup
definition
Hash Table, also known as hash table. It is a data structure characterized by: the keywords of data elements are directly related to their storage addresses.
If different keywords are mapped to the same value through a hash function, they are called "synonyms". If other elements are already stored at the location determined by the hash function, this situation is called a "conflict"
Common hash functions
division leaving remainder method
H(key) = key % p, p is a prime number not larger than the table length
direct addressing method
H(key) = key or H(key) = a*key b
digital analytics
Select a number of bits with a relatively even distribution of numbers as the hash address
Square-Medium Method
Take the middle digits of the squared value of the keyword as the hash address
How to handle conflicts
Use the zipper method (also known as the link method and the chain address method) to deal with "conflicts": store all "synonyms" in a linked list
Open addressing method (H=(H(key) d)%m)
Linear detection method
square detection method
pseudorandom sequence method
rehashing
Re-hash method (re-hash method): In addition to the original hash function H (key), prepare several more hash functions. When the hash functions conflict, use the next hash function to calculate a new address. Until there is no conflict:
Search efficiency
Depends on the hash function, the method of handling collisions, and the filling factor α - the filling factor α = the number of records in the table/the length of the hash table