Data Structure - Find FullSearch

For examination/final examination, covering all core knowledge points of the data structure section

Contents

1. 基本概念
2. 顺序查找
3. 二分查找
4. 分块查找
5. 二叉排序树 BST
6. 平衡二叉树 AVL
7. 红黑树
8. B 树 / B+ 树
9. 哈希查找
10. 查找算法对比总结
11. 常见考题类型

1. Basic concepts

1.1 Definition of search

** Search**: the process of finding data elements in the data set that meet certain conditions.

1.2 Basic terms

| Terminology |------|------| | Figure of data elements of the same type | ** Key The only data item in the data element that identifies this element | ** Looking for success** | Found data elements that meet the conditions in the search table | ** Failed to find** data elements that meet the conditions do not exist in the search table | ** Average length of search (ASL)** Core indicator to measure efficiency of search algorithms

1.3 Average length of search ASL

** ASL (Average Search Length)**: average number of keyword comparisons during search.

ASL Success: $$ASL_{成功} = \sum_{i=1}^{n} P_i \cdot C_i$$

• $P_i$: Find No. $i$ Probability of an element
• $C_i$: Found No. $i$ Number of comparisons required for individual elements

ASL failed: $$ASL_{失败} = \sum_{j=1}^{m} P_j \cdot C_j$$

• $P_j$Other Organiser $j$ Probability between sectors
• $C_j$: Number of comparisons required to determine failure in the zone

1.4 Classification of the search tables

• ** Static Search Table**: search and search only (sequence, double search)
• ** Dynamic search table**: Query + Insert + Delete (two fork sort tree, Hash table)

2. Order of search

2.1 Basic thinking

From the end of the table, the key word by word is compared until the target is found or a complete table is passed.

2.2 Algorithmic realization

// 带哨兵的顺序查找
int SeqSearch(int a[], int n, int key) {
    a[0] = key;           // 设置哨兵
    int i = n;
    while (a[i] != key)   // 从后往前找
        i--;
    return i;             // i=0 表示查找失败
}

Sentry role: every loop judgement omitted i >= 1 Border conditions and efficiency gains.

2.3 Performance analysis

| Indicator Value |------|-----| | ASL Success (Equal Probability) $\frac{n+1}{2}$ | | ASL failed $n+1$(no sentry)/ $n$(Sentry guard) | Time complexity $O(n)$ | | Space complexity $O(1)$ |

2.4 Applicable scenes

• Linear tables (both sequential or chain storage)
• Table element disorder
• Small data volume

2.5 Order of the chart search

If the sequence is orderly, the search does not need to go through the end:

• ASL Failed = $\frac{n}{2} + \frac{n}{n+1}$ ≈ $\frac{n}{2}$

3. Two-point search

** Also known as**: half search

3.1 Preconditions

• ** For an orderly sequence only**
• ** Not applicable to chain tables** (link tables cannot access intermediate elements at random)

3.2 Basic thinking

The target value is compared to the middle element at half a time between the search areas:

• Equal poignant search success
• Target < Median ~ Continue searching in the left half.
• Target > Median

3.3 Algorithms achieved

int BinarySearch(int a[], int n, int key) {
    int low = 0, high = n - 1, mid;
    while (low <= high) {
        mid = low + (high - low) / 2;  // 防止溢出
        if (a[mid] == key)
            return mid;                 // 查找成功
        else if (a[mid] > key)
            high = mid - 1;             // 左半区
        else
            low = mid + 1;              // 右半区
    }
    return -1;                          // 查找失败
}

3.4 Determination of trees

The binary search process can be described as a balanced fork tree, known as ** decision tree**.

** Nature of the tree**:

• It’s a balanced fork tree.
• Yes. $n$ A node to determine tree height $\lceil \log_2(n+1) \rceil$
• Number of comparisons when finding success = depth of the corresponding node in the determination tree
• Number of comparisons when finding failure = parent node depth corresponding to an empty pointer

3.5 Performance analysis

| Indicator Value |------|-----| | ASL Success $\frac{n+1}{n}\log_2(n+1) - 1 \approx \log_2(n+1) - 1$ | | Time complexity $O(\log n)$ | | Space complexity $O(1)$ |

3.6 Example of ASL calculation

** Example: Order table [7, 14, 18, 21, 23, 29, 31, 35, 38], two points to find successful ASL.

Construct a determination tree (number in nodes is a subscript, not a value):

              4(23)
           /       \
        1(14)      6(31)
       /    \      /    \
     0(7)  2(18) 5(29) 7(35)
       \     \           \
       1*    2*          8(38)
                          \
                          8*

• Finds 1 success: 1 node $1 \times 1 = 1$
• Find 2 success: 2 nodes $2 \times 2 = 4$
• Find 3 success: 4 nodes $3 \times 4 = 12$
• Find 4 success: 2 nodes $4 \times 2 = 8$

$$ASL_{成功} = \frac{1+4+12+8}{9} = \frac{25}{9} \approx 2.78$$

4. Segment search

** Also known as **: Index Order Search

4.1 Basic thinking

1. Division of data into several ** blocks**, in an disorderly and orderly manner
2. Create ** Index Table,** where the maximum keywords and starting address of each block are recorded
3. First check the index table to identify blocks, then find them in the block order.

4.2 Performance analysis

Existing $n$ A record. $b$ All of them. $s$ Notes$n = b \times s$）：

$$ASL = L_{索引} + L_{块内}$$

• Index order search:$ASL = \frac{b+1}{2} + \frac{s+1}{2}$
• Index 2nd find:$ASL = \log_2(b+1) - 1 + \frac{s+1}{2}$

Best segment:$s = \sqrt{n}$ I don’t know.$ASL_{min} = \sqrt{n} + 1$

5. Trident sorting tree BST

** Also known as **: fork finding tree, fork searching tree

5.1 Definitions

Fork sort tree is empty or meets the following characteristics:

1. If the left tree is not empty, the value of all nodes on the left tree** is less than the value of the ** node
2. If the right sub-tree is not empty, the value of all nodes on the right sub-tree** is greater than the value of the ** node
3. The left and right trees are each a fork sort.

** Focus of the examination**: Medium Sequence BST has an incremental sequence

5.2 Finding Operations

BSTNode* BSTSearch(BSTNode* root, int key) {
    if (root == NULL || root->key == key)
        return root;
    if (key < root->key)
        return BSTSearch(root->left, key);
    else
        return BSTSearch(root->right, key);
}

** Search process**: from root to root if it is successful; less than root if left; more than root if right.

5.3 Insert Operations

Insert a new node** Must be a leaf node**.

BSTNode* BSTInsert(BSTNode* root, int key) {
    if (root == NULL) {
        BSTNode* node = (BSTNode*)malloc(sizeof(BSTNode));
        node->key = key;
        node->left = node->right = NULL;
        return node;
    }
    if (key < root->key)
        root->left = BSTInsert(root->left, key);
    else if (key > root->key)
        root->right = BSTInsert(root->right, key);
    return root;  // key 已存在则不插入
}

5.4 Delete Operations

Situation Analysis (set to delete node as p）：

** Centred forward**: bottom right of the left tree
** In the middle order follow**: bottom left node in the right subtree

5.5 ASL Analysis

• ** Best case** (balanced):$ASL = O(\log n)$
• ** Worst case** (unilateral slash):$ASL = O(n)$

The insertion order affects the shape of the BST, which leads to balancing the need for a fork tree.

6. Balance fork tree AVL

6.1 Definitions

** Balance fork tree**: ** The absolute value of any node ** the difference between the height of the left and right **.

** Balance factor** = height of left subtree - height of right subtree, value: 1, 0, 1

6.2 The smallest imbalance subtree

During the insertion, the sub-tree is rooted on the node of ** the nearest ** balance factor to the absolute value > 1.

6.3 Four types of adjustments

6.4 Rotation diagram

L (right single):

      A               B
     / \             / \
    B   Ar   =>    C     A
   / \            / \   / \
  C   Br        Cl  Cr Br  Ar
 / \
Cl  Cr

R type (single left):

    A                 B
   / \               / \
  Al  B     =>      A   C
     / \           / \  / \
    Bl  C        Al Bl Cl Cr
       / \
      Cl  Cr

LR type (left to right):

      A                 A               C
     / \               / \             / \
    B   Ar   左旋B    C   Ar  右旋A   B     A
   / \        =>    / \        =>    / \   / \
  Bl  C            B   Cr          Bl  Cl Cr  Ar
     / \          / \
    Cl  Cr       Bl  Cl

RL type (right after left): symmetry with LR.

6.5 AVL Performance

| Indicator Value |------|-----| | Find | $O(\log n)$ | | Insert | $O(\log n)$ | | Delete | $O(\log n)$ | | Height$n$ Node) $O(\log n)$ |

AVL finds the most efficient, but inserts/delets maintenance costs are higher.

Red and black trees

7.1 Definitions

Red and black tree is a binary sorted tree that meets the following characteristics:

1. Each node is** red** or** black**
2. ** Roots** Black
3. ** Leaf Node (NIL)** Black
4. ** Can’t have two consecutive red nodes**
5. Path from either node to each of its leaves,** the same number of black nodes** (the same black height)

7.2 Red and Black Tree vs AVL Tree

| AVL tree, twilight tree, twilight tree. |----------|--------|--------| | Balancing conditions | Tight (high difference 1) Easier (black height equal) | | Look for efficiency. | Insert/delegate | Number of rotations | Apply scenes | Find intensive | Insert/delegate intensive | | Practical application | Theoretical scenes are numerous | STL Map/set, Java TreMap |

7.3 Nature extrapolation

1. The longest path from root to leaf two times the shortest path
2. Height of the red and black tree $h \leq 2\log_2(n+1)$
3. Find Time Complexity $O(\log n)$

8. B / B + tree

B Tree = Multi-road balance search tree, often used for indexing file systems and databases

8.1 B Definition of Trees$m$ Step

1. Up to each node** $m$ Tree**
2. Roots at least 2 subtrees (non-leaf)
3. Non-root nodes** at least $\lceil m/2 \rceil$ Tree**
4. All the leaves are on the same floor.
5. Each node contains**$n$ A key word.$n+1$ A tree** with orderly keywords
6. Number of keywords per non-root**:$\lceil m/2 \rceil - 1 \le n \le m - 1$

8.2 5 Step B Tree Example

              [20, 40]
            /    |     \
    [5,10,15]  [25,30,35]  [45,50,55,60]
    / | |  \   / |  |  \   / |  |  |  \
   ...叶子都在同一层...

8.3 B Tree height

Set $m$ Step B. Trees have $n$ Keyword: $$h \leq \log_{\lceil m/2 \rceil}\left(\frac{n+1}{2}\right) + 1$$

8.4 Characteristics of B+ trees

B+ tree is the variant of B tree, the main difference:

| Distinction B Tree B+ Tree |------|------|-------| | Key-word storage | Keywords and records for each node | Leaf nodes No links ** Leaf nodes linked by keyword** | Find the path, the luminum, you can find it on any level. | ** Support for efficient scope queries** | Application | Less ** Database Index (MySQL InnoDB)** |

8.5 B+ tree structure

            [20, 40]           ← 非叶（仅索引）
           /    |    \
    [5,10]  [25,30]  [45,60]   ← 非叶（仅索引）
    /  |  \  /  |  \  /  |  \
   ○ ↔ ○ ↔ ○ ↔ ○ ↔ ○ ↔ ○ ↔ ○   ← 叶子（全记录 + 链表）
   ↓   ↓   ↓   ↓   ↓   ↓   ↓
  记录 记录 记录 记录 记录 记录 记录

9. Hashi Search

** Also known as **: hash search

9.1 Basic concepts

| Terminology |------|------| | Hashi function $H(key)$ A function that maps key words to a storage address | Hashi Table | Storage structure established through the Hashi function | ** Synonym** | Different keywords map to the same address by the same Hash function | ** Conflict ( Collision)** Address by synonym

9.2 tectonic approach to the Hashi function

| Methodologies Formulae Characteristics |------|------|------| | ** Save balance** $H(key) = key \bmod p$ | $p$ Not larger than the surface. | Direct location $H(key) = a \cdot key + b$ ♪ No conflict, no space ♪ | Numerical analysis, | take a number of places evenly distributed, | suitable for known keyword collections, | | Square medium for the middle of |key2 | Collapse, fold, insert, fold, fit for longer keywords

** Focus**: Saved balance $p$ A maximum base figure of not more than the length of the table should be taken to reduce conflict.

9.3 Conflict approach

I. Open location law

When a conflict occurs, the next vacant address is detected.

Mathematic formula:$H_i = (H(key) + d_i) \bmod m$

(1) Linear detection:$d_i = 0, 1, 2, …, m-1$

• ** Advantages**: achieving simplicity
• ** Shortcomings**:** concentration** (symphony and non-symmetry at the same address)

(2) Square detection method:$d_i = 0, 1^2, -1^2, 2^2, -2^2, …$

• Avoiding concentration
• Requesting Chief $m$ It’s like $4k+3$ Number of primes

(3) Double-hash method:$d_i = i \times H_2(key)$

• Calculate increment using the second Hash function

(4) The pseudo-random sequence method

ii. Chain Address Law (Classic Law)

Stores all synonyms in the same chain table.

哈希表：
[0] → K0 → K10 → K20 → NULL
[1] → K1 → NULL
[2] → K2 → K12 → NULL
[3] → NULL
[4] → K4 → NULL
...

9.4 Spreadlist Find ASL

Average length of search with ** filling factor** $\alpha$ Directly related: $$\alpha = \frac{\text{表中已有记录数}}{\text{表长度}}$$

$\alpha$ The smaller the conflict, the smaller the ASL, the greater the waste of space.

9.5 Hash looked for examples of ASL calculations

** Example**: Keyword series {19, 14, 23, 01, 68, 20, 84, 27, 55, 11, 10, 79}Hash function $H(key) = key \bmod 13$Chief. $m=13$。

** The conflict is handled using linear detection methods** to construct the Hashi table and calculate ASL.

| Key (key) |-----|--------|-------|----------| | 19 |6 | 6 | | 14 |1 | 1 | | 23 |10 |10 | | |1 conflict 2 | 68 |3 |3 | | 20 |7 |7 | | 84 |6 | Conflict 8 | | 27 |1 conflict 4 | | 55 | 3 | Conflict 5 | | 11 | 11 | 11 | | 10 | Conflict 12 | | 79 |1 conflict 0 |

Hashi Table End state:

[0] 79  [1] 14  [2] 01  [3] 68  [4] 27  [5] 55
[6] 19  [7] 20  [8] 84  [9] —   [10] 23 [11] 11  [12] 10

ASL Success:

$$ASL_{成功} = \frac{1+1+1+2+1+1+3+4+3+1+3+9}{12} = \frac{30}{12} = 2.5$$

10. Summary of comparison of search algorithms

11. Types of common subjects

Type I: Construct the award tree, calculate ASL

A table of sequences is given, a two-point determination tree is drawn (rounded nodes + equation failed), and ASL is calculated.

Type II: Insert and Delete BST

Gives a key-word sequence, constructs the BST step by step, drawing the tree after each step.

Type III: AVL balance adjustment

Gives a sequence of insertions to construct the AVL tree, indicating the type of adjustment (LL/RR/LR/RL).

Topic IV: Inserting and Removing B Trees

Organisation $m$ Step B tree, insert/delete keywords in turn, and draw the final tree.

+ ASL calculation

The given keyword +Hashi function +conflict method to construct the Hashi table and calculate ASL.

Topic VI: Hash function design + ASL calculation

Hash table construction and ASL analysis under chain address method.

Appendix: Summary of the core formula

1. Sequenced search$ASL_{成功} = \frac{n+1}{2}$

2. ** Two-point search to determine tree height**:$\lceil \log_2(n+1) \rceil$

3. ASL**:$\frac{n+1}{n}\log_2(n+1) - 1$

4. ** The best part finding**:$s = \sqrt{n}$，$ASL_{min} = \sqrt{n} + 1$

5. ** AVL balance factor**: left height - right height, only -1, 0, +1

6. $m$ Step B Keywords:$\lceil m/2 \rceil - 1 \le n \le m - 1$

7. ** Filling factor**:$\alpha = \frac{记录数}{表长}$

8. Hashi ASL (chain address successful):$1 + \frac{\alpha}{2}$

** Preparatory proposal**: Focus on two-point search (determinating tree + ASL), four adjustments to AVL tree, differences in B/B+ tree, construction of the Hashi watch and conflict management, four parts of which are high frequency test points.