Features
Features:

Product Tour >

Edraw AI >

Paid Plans:

Individuals >

Business >

Eduaction >
Resources
Blog

History

How-tos & Tips

Discovery

Biography

Business Analysis

Examples

AI concept Map

Free AI Mind Map Generator

Onenote Mind Map

Bcg Matrix Examples

Nike Marketing Strategy

Unilever SWOT Analysis

Make Mind Maps in Google Docs

Guide

FAQs

What's New

Resource Center
Templates
All Templates

Brain Storming Templates

Strategy and Planning Templates

Project Management Templates

Product Management Templates

Human Resources Templates

Agile Workflow Templates

Marketing Templates

Education Templates

Fun and Games Templates

User Gallery
Download
Pricing
Enterprise

MindMap Gallery Study notes on basic algorithms of data structures

Study notes on basic algorithms of data structures

Full of knowledge points! Sharing useful study notes and mind maps! This mind map explains in detail the search and sorting of basic computer data algorithms. It will allow you to learn more quickly and conveniently. It is recommended to collect and study!

Edited at 2019-09-05 15:10:40

PlotWizard

Recent works View more works>>

Study notes on basic algorithms of data structures

PlotWizard

Recent works View more works>>

Recommended to you
Outline

Data structure basic algorithms

Find

Basic search methods

Sequential search method: sequentially scan the linear table starting from one end of the table, and compare the scanned keywords with the given values in sequence.

Half search method: The search requires that the linear table must adopt a sequential storage structure, and the elements in the table must be arranged in order by keywords. Compare the keyword recorded in the middle position of the table with the search keyword. If the two are equal, the search is successful; otherwise, use the middle position record to divide the table into the first and last sub-tables. If the keyword recorded in the middle position is greater than the search keyword, Then further search the previous sub-table, otherwise further search the next sub-table

Block search method: Divide the linear table into several blocks, and require that the largest keyword in the previous block must be smaller than the next block. Create an index table, use the maximum key value in each block as the key value of the index table, and store it in an auxiliary array in the order of the blocks. When searching, first search in the index table to determine where the node you are looking for is located. of blocks. Since the index table is sorted, the index table can be searched using sequential search or binary search; then, the corresponding node can be found by sequential search in the corresponding block, which is a combination of the first two methods.

Data structures suitable for lookups

Binary tree

Binary sorting tree

Basic property: If the left subtree is not empty, then the values of all nodes on the left subtree are less than the value of its root node; if the right subtree is not empty, then the values of all nodes on the right subtree are greater than its root node. value; there are no nodes with equal key values

Basic operations

Search: Search downward from the root node

Insertion: For a keyword that does not exist in the binary sorting tree, the position where the search fails is the insertion position.

Delete: If it is a leaf node, it can be deleted directly. If the node has only one of the left and right subtrees, delete the modified point and directly connect its subtree to its parent node. If the node has both left and right subtrees, Then search for a node that can replace its position in its left subtree or right subtree.

balanced binary tree

Basic properties: It is an empty tree or the absolute value of the height difference between its left and right subtrees does not exceed 1, and both left and right subtrees are balanced binary trees.

Construction method: Put the elements of the array into the tree one by one. If there is a node with a negative BF value, and if its left subtree is lower than the right subtree, rotate counterclockwise around the node to change the root node of the current level. After fine-tuning, if its right subtree is lower than the left subtree, rotate clockwise around the node to change the root node of the current level and then fine-tune

multi-tree

B-tree (B-tree)

Basic properties: If it is an m-ary tree, the root node has at least two branches, and the non-root and non-leaf nodes have at least [m/2] ([] is the rounding function) branches; each node can have multiple branches. keywords, m-ary tree nodes can accommodate up to m-1 keywords; the keywords of nodes at the same level are arranged from left to right in order of size, starting from the left/right end of the node or between two keywords Lead a branch. The size of the keywords in the node connected by the branch must be between the connected keywords at the previous level (if it is led from the left endpoint, it should be smaller than the left end keyword, and if it is led from the right endpoint, it should be larger than the right end keyword. )

Basic operations

Search: Search downward from the root node

Insertion: For a keyword that does not exist in the B-tree, the position where the search fails is the insertion position. If the number of node keywords is greater than m-1 after insertion, the node needs to be split: the keywords with centered values among the interpolated nodes will be merged into the upper-level node. If the upper-level node keyword If the number also exceeds the standard, repeat the operation.

delete

The deleted node is located at the terminal node

The number of node keywords is greater than [m/2]-1: delete directly

The number of node keywords is equal to [m/2]-1

If the number of keywords in the left and right nodes of the keyword is greater than [m/2]-1, borrow words from the node with the number of keywords greater than [m/2]-1 to fill the original position.

If the number of keywords on the left and right nodes of the keyword is equal to [m/2]-1, then the left and right nodes of the keyword will be merged into one node after deleting the keyword.

The deleted node is not in the terminal node

① Follow the left pointer of the keyword to its subtree root node ② Go down along the right pointer of the rightmost keyword in the root node, and use the same method until you reach the terminal node ③ Use the terminal node Click to replace the node to be deleted, and then use the method of deleting the terminal node to perform subsequent processing after the terminal node is replaced upwards.

B-tree

Basic property: A node containing n keywords (including terminal nodes) has n branches, where [m/2]<=n<=m

The difference from B-tree: In B-tree, all non-leaf nodes only serve as an index and do not contain the storage address of the record corresponding to the keyword. They are only in the record pointed to by the pointer of each leaf node. The storage address of all keywords; each keyword in the B-tree corresponds to the storage address of a record

hash table

Basic property: Calculate the address of the keyword in the table based on the given keyword

Construction method

Direct addressing method: take the keyword or a linear function of the keyword as the Hash address

Numeric analysis method: take several digits of the keyword to form a Hash address

Square method: take the middle digits after squaring the keyword as the Hash address

Divide and leave remainder method: take the keyword divided by a number that is not larger than the length of the Hash table (usually the largest prime number that is not larger than the table length), and divide the keyword by the number to get the remainder as the Hash address

Conflict handling methods

open address law

Linear probing method: After a duplicate address appears, probe backwards using this address as the starting point until the number of unused addresses appears.

Square detection method: process the conflicting address d (d² 1) and use the calculated value as the address

Chain address method: a method of connecting all synonyms using a singly linked list

sort

Internal sorting: the sorting process in which the column to be sorted is completely stored in memory, suitable for element sequences that are not too large

A method with time complexity of O(n²)

Bubble sorting: ① Compare adjacent elements. If the first is larger than the second, swap them both ② Do the same for each pair of adjacent elements, starting with the first pair and ending with the last pair. At this point, the last element should be the largest number. ③ Repeat the above steps for all elements except the last one. ④ Continue repeating the above steps for fewer and fewer elements each time until there are no pairs of numbers to compare.

Simple selection sort: Suppose the number of records in the sorted sequence is n. i takes 1, 2,...,n-1, find the record with the smallest sorting code from all n-i 1 records (Ri, Ri 1,..., Rn), and exchange it with the i-th record. After executing n-1 times, the sorting of the record sequence is completed.

Direct insertion sorting: First, the first data is ranked first, and then in each pass, a piece of data to be sorted is inserted into the appropriate position of a group of records that has been sorted according to the size of its key. Until all data to be sorted is inserted

Method with time complexity of O(n^3/2)

Hill sorting: First take an integer d1 less than n as the first increment, and group all the records in the file. All records whose distance is a multiple of d1 are placed in the same group. First perform direct insertion sorting within each group; then, take the second increment d2<d1 and repeat the above grouping and sorting until the increment dt=1 (dt<...<d2<d1)

A method with time complexity O(nlog2n)

Heap sort: Construct the sequence to be sorted into a binary tree, and then perform transposition adjustments to ensure that all child nodes are smaller than their parent nodes. At this time, the root node value must be the maximum value. Take out the node and build a binary tree again. , repeat the above operations

Two-way merge sort: ① Form a number of binary groups and adjust them to order within the group ② Merge the ordered binary groups into one group and adjust them to order within the group ③ Merge all data into one group to complete the sorting

A method with time complexity O (nlog(r)m) (r is the base taken, and m is the heap number)

Radix sorting: Set up ten spaces, named 0 space, 1 space,..., 9 space. First, correspond the records in the sequence to each major space one by one according to the single digit value and place them into each space. Complete the sorting in each space. , then take out each record from the 0 space to form a new sequence, and then repeat the work at higher bits until the highest bit sorting is completed

External sorting: The files to be sorted cannot be loaded into the memory at one time, and multiple data exchanges between the memory and external storage are required to sort the entire file.

Mainstream algorithm

Merge sort: Divide the initial sequence into m smaller record segments, sort these record segments, and continuously compare the minimum values from the smallest ends of each record segment until the sorting is completed.

important subalgorithm

Loser tree: When merge sorting detects the minimum value, if you do not use the loser tree, you need to compare the k values read k-1 times. After using it, you only need to perform log2k times. The time complexity of selecting the best value is O(log2k ), the tree building time complexity is O(klog2k), and the loser tree height is [log2k] 1

Establish

① For the k records read in, a binary tree is established with any two nodes as a group. The smallest value in each group is the winner. The sequence number corresponding to the loser is used as the parent node of both, and the sequence number corresponding to the winner is The sequence number is used as the parent node of the parent node. If there is one record left, the next process will be processed. ② Process the excess record, compare its sequence number with a certain binary tree, and merge it into one tree according to the winner-on-top principle. And connect the excess record values at this node as its child nodes ③ Compare the binary trees and merge them into one tree according to the winner-on-top principle (the root node of the loser tree has only one fork, and the rest conform to the binary tree in principle)

Adjustment

After taking out the minimum value in the loser tree, the newly read records need to be added to form the loser tree. At this time, the loser tree needs to be adjusted to meet the criteria of the loser tree. Adjustment method: fill in the vacancies with newly read records, and then compare step by step from bottom to top. The winner's serial number is the parent node of the loser's serial number until the adjustment is completed.

Replacement-selection sorting: According to the size of the buffer, a record is read from the external memory. When the record fills the buffer, the smallest one is selected and written back to the external memory. Its vacant position is replaced by the next read record, and the output record becomes the current initial record. Part of the merged segment. If the newly input record is smaller than the record taken out into the merge segment, it will be generated as an alternative to other initial merge segments. Repeat the above operations

Optimal merge tree: Merge segments of different lengths are obtained through replacement-selection sorting. Each segment is placed on a Huffman tree according to its length (see the chapter on trees for the method). Starting from the root node, each segment is reached. Twice the sum of the number of edges passed by the node is the number of I/Os corresponding to the optimal merge tree (minimum number of I/Os)