MindMap Gallery Data Structures and Algorithms
Data Structures and Algorithms Data structures are the way data is stored and organized in computers. A data structure is a collection of data elements that has certain logical relationships, applies a certain storage structure in the computer, and encapsulates corresponding operations.
Edited at 2022-06-01 17:11:27This infographic, created using EdrawMax, outlines the pivotal moments in African American history from 1619 to the present. It highlights significant events such as emancipation, key civil rights legislation, and notable achievements that have shaped the social and political landscape. The timeline serves as a visual representation of the struggle for equality and justice, emphasizing the resilience and contributions of African Americans throughout history.
This infographic, designed with EdrawMax, presents a detailed timeline of the evolution of voting rights and citizenship in the U.S. from 1870 to the present. It highlights key legislative milestones, court decisions, and societal changes that have expanded or challenged voting access. The timeline underscores the ongoing struggle for equality and the continuous efforts to secure voting rights for all citizens, reflecting the dynamic nature of democracy in America.
This infographic, created using EdrawMax, highlights the rich cultural heritage and outstanding contributions of African Americans. It covers key areas such as STEM innovations, literature and thought, global influence of music and arts, and historical preservation. The document showcases influential figures and institutions that have played pivotal roles in shaping science, medicine, literature, and public memory, underscoring the integral role of African American contributions to society.
This infographic, created using EdrawMax, outlines the pivotal moments in African American history from 1619 to the present. It highlights significant events such as emancipation, key civil rights legislation, and notable achievements that have shaped the social and political landscape. The timeline serves as a visual representation of the struggle for equality and justice, emphasizing the resilience and contributions of African Americans throughout history.
This infographic, designed with EdrawMax, presents a detailed timeline of the evolution of voting rights and citizenship in the U.S. from 1870 to the present. It highlights key legislative milestones, court decisions, and societal changes that have expanded or challenged voting access. The timeline underscores the ongoing struggle for equality and the continuous efforts to secure voting rights for all citizens, reflecting the dynamic nature of democracy in America.
This infographic, created using EdrawMax, highlights the rich cultural heritage and outstanding contributions of African Americans. It covers key areas such as STEM innovations, literature and thought, global influence of music and arts, and historical preservation. The document showcases influential figures and institutions that have played pivotal roles in shaping science, medicine, literature, and public memory, underscoring the integral role of African American contributions to society.
Algorithms and Data Structures
linear table
Linked linear list has head node (pacesetter)
The first node is phead->next or head.next
stack
Non-recursive implementation of recursive programs does not necessarily require a stack
You can use the idea of DP
picture
The vertex set of the graph is not empty, so there is no empty graph
connected components
Maximally connected subgraph
A circuit is a ring
The cycle must not be a simple path
Except for the endpoints, the intermediate nodes of a simple loop do not repeat.
The vertices of a simple path are not repeated
adjacency matrix
Generally, the elements on the main diagonal are 0
Not connected is infinity
Critical Path
Earliest start time ve()
Latest start time vl()
The earliest start time of the activity e()
The earliest start time of the origin point
The latest start time of the activity l()
The latest start time of the meeting point minus the activity time
Activity time margin d()
Indicates the time margin of the activity. An activity with a margin of 0 is on the critical path.
Shortening the common edges of all critical paths can shorten the construction period
Extending any critical edge will extend the construction period
KMP
partial match table
A table consisting of the common prefix and suffix lengths of all prefixes of the substring
next[]
nextval[]
sort
Hill sort
an insertion sort
Gradually reduce the increment and use direct insertion sort within the group
external sort
multi-way balanced merging
The number of segments after each pass of processing becomes celing(m/k), where k is the number of passes.
Find
average search length
binary search
Draw search tree
Also known as binary decision tree
The average height of the failed node's parent node
Success is calculated as average depth
Hash table lookup
Tree
B-tree and B-tree
B-tree
Definition of m-order B-tree
Each node has at most m subtrees and m-1 keywords
The non-empty B-tree root node has at least 2 subtrees
The non-root node has at least ceiling(m/2) subtrees
3,4-2
5-3
The leaf node is the node where the search failed (actually does not exist)
The terminal node refers to the lowest node
Also called B-tree
Each element appears only once
Data is inside the B-tree node
Any node keyword always has left and right children
The predecessor/successor of any keyword is always at the lowest level
Split on insertion
Middle elements are raised, recursively split
After splitting, the node on the left is always full.
The 4th order B-tree node is split into 2,1,1
merge on delete
always translates into a merger from the bottom
If you have enough, borrow it from your brothers
If the borrowing is not enough, the parent keyword will be dropped and the terminal point will be merged.
If there is not enough money to borrow, it will definitely be merged.
The order is odd, and there are m-1 keywords after merging.
The order is even, and there are m-2 keywords after merging.
Note that the nodes after merging even-order B-trees are not full.
Merge towards the root
B-tree
m-order B-tree definition
Similarly, there are at most m subtrees and at least ceiling(m/2) subtrees.
But the keyword is the largest keyword corresponding to the child node
Therefore there are also m
Leaf nodes have pointers to records
Leaf nodes are linked horizontally to facilitate traversal search
Pay attention to the difference between the leaf nodes of the B tree and the leaf nodes of the B tree.
minimum spanning tree
When the weights of each edge are different from each other, the minimum spanning tree is unique
The spanning trees constructed using Prim's algorithm from different vertices are not necessarily the same.
The minimum spanning tree edge weight sequence of the same picture is the same
heap
Build a pile
Array traversal from back to front
AVL tree
Delete and insert
If the deleted node is a non-leaf node, the tree may be the same after reinsertion