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.

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.

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)

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)

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

Depends on the height of the tree, best O(log n), worst O(n)

Calculation of average search length

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.

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 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)

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

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)

① 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 it's Uncle Hei: rotate and dye

If it is Uncle Hong; dyeing makes it new: Uncle dyes and turns into a new node

Important test points

It’s too difficult to delete. I bet you he won’t take the exam.

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

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)

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.

non-terminal node keyword

terminal node Keywords

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.

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.

H(key) = key % p, p is a prime number not larger than the table length

H(key) = key or H(key) = a*key b

Select a number of bits with a relatively even distribution of numbers as the hash address

Take the middle digits of the squared value of the keyword as the hash address

Linear detection method

square detection method

pseudorandom sequence method

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: