Collection structure: the order between elements is arbitrary, only "belongs to the same set" to contact

Linear structure: an ordered sequence of data elements. Except for the beginning and end elements, the other elements have unique advances and successors.

Tree structure: Except for the root element, each node has only one forward trend, and the number of successors is unlimited.

Graphic structure: There is no limit on the number of forward and successors for each element

Components: data element storage, relational storage between data elements

Physical structure: storage node (storage data elements), logical structure representation (relational storage), additional information (such as linked list header nodes)

Basic storage method: The storage node can be used for structures/objects, adopt generic programming ideas, and focus on relational storage

Relational storage method:

Time: The program runs, and it is necessary to avoid excessive time-consuming

Space: The space required for the program to run, and it is necessary to avoid excessive memory usage

Core idea: do not consider the specific running time function, pay attention to the law of changing the running time with the scale when the problem is large, and take the order of magnitude of the running time function

definition:

Example: T(n)=(n 1)² is O(n²)

F(N) Selection: Select a simple function form, ignore the low-order terms and coefficients

Typical growth rate: constant (c), logarithmic (logN), log square (log₂N), linear (N), NlogN, square (N²), cubic (N³), exponent (2ⁿ)

Algorithm classification:

Steps: Define standard operations, calculate the number of standard operations to get the function, and take the main term to get the large O expression

theorem:

Calculation rules:

Simplified calculation: find the most complex program segment to calculate the time complexity, that is, the time complexity of the entire program

Solution 1 (exhaustive method): Find the sum of all possible sub-sequences, find the maximum value, time complexity O(n³)

Solution Two (O(n²) Algorithm): Using the recursive relationship of subsequence sums, omitting the innermost loop

Solution Three (O(n) algorithm): Optimize loops based on the characteristics that negative subsequence does not constitute the largest continuous subsequence

Core: Encapsulating the storage and processing process of data structures into tools

Advantages: Users only need to know the logical characteristics, no need to know storage and operation implementation

Learning requirements: Know storage and processing methods, understand packaging to adapt to user needs

The course adopts an object-oriented approach

Logical properties: abstract class description, pointing out the provided operations

Implementation: Several implementation classes are inherited from the corresponding abstract classes to ensure logical characteristics

Definition: A set composed of N identical characteristic nodes A₀, A₁,…, Aₙ₋₁, except A₀ and Aₙ₋₁, each element has a unique predecessor (Aᵢ₋₁) and successor (Aᵢ₊₊), A₀ has no predecessor, Aₙ₋₁ has no successor

Terms: N is the table size, A₀ is the head node, Aₙ₋₁ is the tail node, empty table (number of elements is 0), position (Aᵢ position is i)

Operations of tables: create (create()), clear (clear()), find length (length()), insert (insert(i,x)), delete (remove(i)), search (search(x)), access (visit(i)), traverse()

The order implementation of linear tables:

Linked implementation of linear tables:

Linear table abstract class: template class, including clear(), length(), insert(), remove(), search(), visit(), traverse() pure virtual functions and destructors

Sequence table class:

Double-linked list class:

Introduction to STL: C data structure implementation, called collection or container

Linear table implementation:

Definition: Last-in, first-out (LIFO) or first-in, last-out (FILO) structure, the earliest (late) arrives at the node at the latest (first), such as table tennis balls entering, exiting box

Related concepts: bottom of the stack (the header of the structure, the node arrives the earliest), top of the stack (the tail of the structure, the node arrives the latest), stack entry (Push, insert top of the stack), stack exit (Pop, delete top of the stack), empty stack (the number of nodes is 0)

ADT of the stack: template class, including isEmpty(), push(), pop(), and top() pure virtual functions

The order of stack implementation:

The link implementation of the stack:

Non-recursive implementation of recursive functions: use the stack to simulate function calls, and the current on-site stack is entered when the function calls, such as fast sorting non-recursive implementation

Symbol Balance Check:

Evaluation of expressions:

Definition: First-in-first-out (FIFO) structure, arrives early and leaves early. For example, banks queue up and print queues, you can imagine as pipelines, nodes flow in from the tail of the team and out from the head of the team.

Basic concepts: dequeue (dequeue, team leader delete), join (Enqueue, team tail insert), judge team empty (isEmpty)

ADT of the queue: template class, including isEmpty(), enQueue(), and deQueue() pure virtual functions

Queue order implementation:

Link implementation of queues:

Comparison of sequential implementation and link implementation:

Introduction to simulation: Use computer to simulate real-life system operations, collect statistical data, such as bank operating system simulation

Discrete event simulation: including two types of events: customer arrival and customer departure after service, statistics on customer queue length, waiting time, etc.

Basic method: Use probability function to generate input streams of customer arrival time and service time, sort by arrival time, and use "tick" as time unit

Time-driven simulation: The clock starts from 0, add 1 tick per step to check events, suitable for situations where event intervals are small, otherwise the efficiency is low

Event-driven simulation:

Implementation key:

Random event generation: Random number generator is used for uniform distribution

Priority queue: insert in order based on the queue, inherit the linkQueue class and rewrite enQueue()

Banking system simulation example:

Tool preparation: Waiting queue (normal queue), event queue (priority queue), random event generation function

Simulator design:

P108 Questions 4, 20, 24, 35

Definition: The finite set T of n (n≥1) nodes has a root node, and the remaining nodes are divided into m (m≥0) non-intersecting sets (subtrees)

Example diagram: Show the structure of the tree (A is the root, and the subtree contains B, C, D, etc.)

Terms: node, degree of node, leaf node, internal node, son node, father node, brother node, ancestor node, descendant node, node level, tree height, orderly tree, disorderly tree, forest

Data: A limited set of data elements/nodes of the same data type

Relationship: father-son relationship

Operation: Find the root node, find the parent node, find the i-th child, delete the i-th child, build a tree, and the traversal of the tree

Standard form: Each node contains data fields and K pointer fields (K is the degree of the tree)

Generalized standard form: Add father node pointer field based on standard form

Example: Tree generalized standard storage with degree K=3 (table display node values, s1, s2, s3, p)

Disadvantages: There are many empty pointer fields, waste of space

Left son and right brother notation: Each node contains data, the root pointer of the first subtree tree, and the pointer of the brother node, and a binary tree represents the tree

Example diagram: Displaying the tree's left son and right brother storage structure

Pre-order traversal: access the root node, pre-order traversal of each subtree

Post-order traversal: Post-order traversal of each subtree and access the root node

Example: Show the traversal results of the preamble (A, B, L, E, C, F, D, G, I, H) and the postsequence (L, E, B, F, C, I, G, H, D, A) of the tree

Application scenario: Operating system directory structure (such as Unix, Windows/DOS), list directory and subdirectory file names, and indent d file names into d tab characters

Implementation: pre-order traversal, listAll() function (print name, if it is a directory, traverse subdirectories)

Example: Show directory structure and traversal output

Definition: A finite set of nodes, empty or composed of roots and two left and right subtrees that do not intersect each other. The left and right subtrees are also binary trees, which strictly distinguish the left and right subtrees.

Basic forms: empty binary tree, root and empty left and right subtrees, root and left subtrees, root and left subtrees, root and left subtrees, root and right subtrees

Different shapes of binary trees with 3 nodes: Show all possible shapes

Common operations: create an empty tree, find the root node, find the parent node, find the left child, find the right child, build a binary tree (for left and right children and root), delete the left child, delete the right child, traversal

Property 1: Non-empty binary tree layer i has up to 2ⁱ⁻¹ nodes (i≥1), examples and proofs (inductive method)

Property 2: A binary tree with a height of k can reach up to 2ᵏ⁻¹ nodes, prove (summarize 2⁰ to 2ᵏ⁻¹)

Property 3: Non-empty binary tree, leaf node number n₀=Number of node with degree 2 n₂ 1, prove (derivation of the relationship between total nodes and total branches)

Full binary tree: a binary tree with a height of k and 2 ᵏ⁻¹ nodes, the number of nodes of any layer reaches the maximum value, example diagram

Complete binary tree: Several nodes are drawn from the bottom layer of the full binary tree from right to left. Characteristics (the leaf node is at the lowest two layers, and the right subtree of any node is high k, and the left subtree is high k or k 1), example diagram (completely compared with non-complete)

Complete binary tree height characteristics (property 4): n nodes full binary tree height k=⌊log₂n⌋ 1, prove (range derivation)

Complete binary tree numbering characteristics: n nodes Complete binary trees are numbered in layer sequence (root 1), and the numbered i nodes (1≤i≤n):

Example diagram: Shows the complete binary tree number and correspondence

Pre-order traversal: empty is empty, otherwise access the root, pre-order traversal of the left subtree, pre-order traversal of the right subtree

Middle order traversal: empty is empty, otherwise middle order traversal the left subtree, access the root, middle order traversal the right subtree

Post-order traversal: empty is empty, otherwise the post-order traversal of the left subtree, and the post-order traversal of the right subtree

Example: Show the tree's preamble (A, L, B, E, C, D, W, X), intra-order (B, L, E, A, C, W, X, D), and post-order (B, E, L, X, W, D, C, A) traversal results

Preamble The binary tree is uniquely determined by the middle order: Example (preamble A, B, D, E, F, C, mid order D, B, E, F, A, C), gradually constructing the binary tree

Sequential storage:

Link storage:

Node design: embedded in tree class, including data, left, right pointers, constructors and destructors

BinaryTree design:

Class definition: template <class Type> class BinaryTree, including Node structure, root member, and construct, destructor, getRoot(), getLeft(), getRight(), makeTree(), delLeft(), delRight(), delTree(), isEmpty(), size(), height(), printPreOrder(), printPostOrder(), printInOrder(), createTree() functions, private member functions (height(), delTree(), size(), printPreOrder(), printPostOrder(), printInOrder())

Create a tree (createTree()):

Binary tree application: sample code (create tree, find height, find scale, traversal, merge), execution example (input and output results)

Iterator requirements: Provide tools to access tree elements in a certain order (such as accessing the next element), corresponding to three types of traversals

Iterator class behavior specification: TreeIterator class, including construct, destructor, First() (first node), operator () (next node), operator () (node), operator () (node), operator() (return current data) functions, protecting members T (binary tree), current (current node pointer)

Preorder traversal iterator (Preorder class):

Postorder traversal iterator (Postor class):

In-order traversal iterator (Inorder class):

Iterator application: Sample code (create a tree, traversed with preorder, middle, and postorder iterators)

Expression tree: Arithmetic expressions are represented as binary tree, and the result is obtained after the order is traversed. Example diagram ((4-2)*(10 (4 6)/2) 2)

Design objective: Use expression tree to calculate expressions

Construction process: recursively construct, the subexpression in brackets is a subtree, and handles operators and operators (by priority)

Class design: Calc class, including node structure (type, data, lchild, rchild), root member, and create(), postOrder(), getToken(), result(), public construct (constructed from expression), result() (calculate result) functions

getToken(): Take syntax units (DATA, ADD, SUB, MULTI, DIV, OPAREN, CPAREN, EOL) from expressions, and process spaces, numbers, operators, and brackets.

create(): recursively builds an expression tree and processes operators, brackets, and operators (by priority)

postOrder(): Post-order traversal output (verification expression tree)

result(): recursive calculation, post-order traversal, operation number returns data, operator calculates the results of left and right subtrees

Application: Sample code (create calc object, calculate expression results)

Problem: Not considered incorrect expression

Data compression: variable length encoding, commonly used short character encoding, examples (character frequency a(10), e(15), etc., fixed length requires 174bit, Huffman encoding requires 146bit)

Huffman encoding: The character with a large frequency is close to the root of the tree, the path (left 0, right 1) is the encoding, sample diagram

step:

Example: A(10), e(15) and other characters to build a Huffman tree, example diagram

Huffman encoding generation: from leaf to root, left 0 to right 1, example (code 001 of a)

Features: The coded element is a leaf node, the others are a degree 2 node, and the size is 2n-1 (n is the number of coded elements)

Storage: size 2n array, 0 is not used, root is stored 1, leaf nodes are stored n 1 to 2n, each element stores data, weights, parent, left and right child positions

Example: Table shows Huffman tree storage (value, weight, parent, left, right)

Generation process: Gradually display the changes in array elements

Node definition: Node structure (data, weight, parent, left, right)

Returns the coded storage structure: hfCode structure (data, code)

Huffman tree class definition: hfTree class, containing elem (Node array), length members, as well as constructor (building Huffman tree), getCode() (getCode), destructor

Constructor: Initialize the leaf node and loop to build the internal node (select the minimum two weight nodes)

getCode(): From the leaf node to the root, record the path (left 0, right 1), generate the encoding

Use: Sample code (generate Huffman encoding of character set a(10) etc., output result)

Definition: empty or satisfies: any node p, left subtree (non-empty) all node keywords <p keyword, right subtree (non-empty) all node keywords> p keyword, left and right subtree is also a binary sorting tree

Example diagram: Showing the binary sorting tree (including characters and values)

Search: If the root is equal, it will be successful, it will be smaller than the left subtree, and it will be larger than the right subtree. Example (Find 122, 110, etc.)

Search recursive description: empty returns false, root equals return true, less than search left, greater than search right

Insert: If the new node is empty, it is the root. If the parent node is not empty, it is searched. If the parent node is inserted as a leaf according to the size, example (Sequences 122, 99, etc. build trees)

Insert recursive implementation: if empty, insert the root, smaller than insert the left, larger than insert the right

delete:

Delete recursive implementation: empty return, less than deletion left, greater than deletion right, equal to (the right subtree will be replaced by two sons and the right subtree will be replaced by the smallest, otherwise the son will be replaced)

Class definition: BinarySearchTree class, including BinaryNode structure (element, left, right), root member, and construct, destructor, findMin(), findMax(), contains(), isEmpty(), makeEmpty(), insert(), remove(), operator=(), printInOrder(), private member functions (insert(), remove(), findMin(), findMax(), contains(), makeEmpty(), clone(), printInOrder())

Design features: embedded BinaryNode class, root is a data member, and public functions call private recursive functions

Member function implementation:

Background: When the tree degenerates into linked lists, it is necessary to balance the tree

Equilibrium factor: left subtree high at node - right subtree high, empty tree height -1

Balanced binary tree: Each node has a balance factor of 1, -1, 0, or the height difference between left and right subtrees is up to 1

Height characteristics: height up to about 1.44log(N 2)-1.328

Example diagram: Showing equilibrium and unbalanced trees (equilibrium factor)

Insert process: Same as binary sorting tree, after insertion, it may be:

Example: Insert 29 (not destroyed), Insert 2 (destruction)

Insertion causes imbalance:

Adjustment method:

Node definition: AvlNode structure (element, left, right, height)

Find the node height: height(t), return -1 by empty

Insert: insert(x, t), recursively insert, judge the balance factor, perform corresponding rotation (LL, LR, RR, RL), update the height

Rotate function:

Class definition: AvlTree class, including AvlNode structure, root member, and construct, destructor, isEmpty(), findMin(), findMax(), contains(), insert(), remove(), makeEmpty(), printTree(), private member functions (insert(), remove(), findMin(), findMax(), contains(), makeEmpty(), clone(), rotateWithLeftChild(), rotateWithRightChild(), doubleWithLeftChild(), doubleWithRightChild(), height())

Delete: late deletion (mark)

Find performance: proportional to tree height, O(logN)

Theorem: The height h of N nodes equilibrium tree satisfies log₂(N 1)≤h≤1.44log₂(N 1)-0.328, prove (derivation of full binary tree, minimum node tree)

Additional balance information is required

Complex implementation, high cost for insertion and deletion

Not exploited 90-10 rules (90% of accesses are targeted at 10% of data)

Definition: limit M continuous operation costs and evenly distribute them to each operation

Example: Array doubled, total cost of M operations O(M)

Core: After accessing a node, it moves to the root through rotation, and often accesses the node near the root, which has the side effects of balancing

Basic idea: Continuously rotate with parent node to root, example (rotation after accessing 3)

Basic method defect: long and bad access sequences may occur, example (insert 1-N and access 1-N)

Goal: Extend from bottom to top to balance the tree, so that the logarithmic distribution is equal to the boundary

Strategy: By rotating from the bottom to the root, there are three situations (zig, zig-zig, zig-zag)

Rotation type:

Example: After inserting 1-N, accessing 1, the tree height is reduced, sample diagram

Advantages: Commonly access the near root of nodes, equal time O(logN)

Scenario: The amount of data is large, the memory cannot be stored, and external data structure is required to reduce the number of disk accesses

Example: 10⁷ records, the worst 10⁷ disk accesses (463 hours), average 32 times (5 seconds), typical 100 times (16 seconds)

Solution: M fork to find the tree, reduce the tree height, log_M N

M-order B-tree:

Example diagram: 5th order B-tree, displaying nodes (disk blocks), keys, and sons

Example: Block capacity 8192 bytes, key 32 bytes, branch 4 bytes, M=228 (non-leaf node), L=32 (leaf, 256 bytes per record)

Scale: 10⁷ records, up to 625,000 leaves, 3-4 layers of index

process:

Example: Insert 57, 55, 40 to show the changes in the tree

process:

Example: Delete 99, display the changes of the tree

Height: log_{⌈M/2⌉} (2N/L), 3-4 layers

Operation: Find the disk at most 5 times to read, insert and delete more than 1 write, split/merge the extra 4 writes (even-apart can be ignored)

Features: Ordered containers that do not allow duplicate elements

traversal: iterator and const_iterator

Operation: Basically similar to vector and list

Sample code: Display insert(), size(), traversal (iterator), output results

Features: Store keywords (unique) - value splices, different keywords can correspond to the same value

Operation: Similar to set

Application: Find words that change one letter to another word (such as wine→fine, etc.), example (the dictionary stores vector, and the result stores map<string, vector<string>>)

Implementation: computeAdjacentWords() (build map), printHighChangeables() (output result), algorithm optimization (grouped by length)

Hash function: map large numbers to small subscripts

String processing: interpreted as integers

Direct address method: H(key)=key or a×key b, example (keyword {100, 400, etc.}, H(x)=x or x/100)

Remaining method: H(key)=key MOD p or c (p≤m prime number), example (m=1024, p=1019), select p as the reason for prime number (avoid space waste)

Digital analysis method: select bits with uniform distribution of numbers as address

Closed hash table (using this hash table spare unit):

Open hash table (link method): Colliding nodes have a linear table outside the hash table, example diagram (synonym chain)

Rehash: Load factor >0.5 will double the capacity, recalculate the hash value insertion

Insert in the head, delete the traversal (O(n)); insert the ordered single-linked list to find the position (O(n)), delete the traversal (O(1))

Definition: Complete binary tree, satisfying:

Example: Minimize heap {2,3,4,5,7,10,23,29,60}, maximize heap {12,7,8,4,6,5,3,1}, sample diagram

Structural: Complete binary tree

Order: Minimize/maximize heap characteristics

Discussion basis: Minimize heap

Priority queue: maximum/minimum element is root

Heap sorting: build heap, take root, adjust heap, repeat until heap is empty

Build a stack:

insert:

delete:

Class definition: BinaryHeap class, including currentSize, array (vector) members, as well as constructs, isEmpty(), findMin(), insert(), deleteMin(), deleteMin(minItem), makeEmpty() functions, private member functions (buildHeap(), percolateDown())

Constructor: default constructor, constructed from vector (buildHeap())

buildHeap(): Inversely call percolateDown() from currentSize/2

percolateDown(): filter downwards and find the younger son to exchange until the order is satisfied

Question: Find the kth largest element in N elements table

solution:

Scenario: Bank queueing system, generate arrival events, and process the earliest event (generate service time back to event queue)

Implementation: Set event queue to priority queue (time is priority)

Insert: O(log_d N)

Delete: O(dlog_d N) (d elements are found to be the smallest)

Empty path length (npl): x to the shortest path of nodes less than two children, leaf npl=0, empty npl=-1

Left heap: Each node has left child npl ≥ right child npl, left tilt, sample diagram (left heap and non-left heap)

Recursive method:

Example diagram: Show the merge process (H1, H2 merge)

Class definition: LeftistHeap class, including LeftistNode structure (element, left, right, npl), root member, and construct, destructor, isEmpty(), findMin(), insert(), deleteMin(), deleteMin(minItem), makeEmpty(), merge(), operator=() functions, private member functions (merge(), merge1(), swapChildren(), reclaimMemory(), clone())

Public merge(): merge two left heaps, rhs empty

Private merge(): merge the right subtree with the small root and the large root, and call merge1()

merge1(): Recursively merge the right subtree, swap the left and right subtrees (if needed), update npl

Benuri tree: B₀s single node, B€ is composed of two B€₋₁ trees, satisfying the order of the heap, example graph (B₀, B₁, B₂, B₃)

Benuri tree characteristics: B€ has 2 ᵏ nodes, and the number of nodes in the d layer is Benuri coefficient

Benuri Queue: Benuri tree collection, at most one tree at each height, corresponding to the number of elements in binary representation, example diagram (6, 7 element queues)

Merge:

insert:

delete:

Tree: Kids Brothers Chain

Forest: A linear table of pointers to the roots of a tree

Example diagram: Showcase queue storage structure

Class definition: BinomialQueue class, including BinomialNode structure (element, leftChild, nextSibling), currentSize, theTrees(vector<BinomialNode*>), and construct, destructuring, isEmpty(), findMin(), insert(), deleteMin(), deleteMin(minItem), makeEmpty(), merge(), operator=() functions, private member functions (findMinIndex(), capacity(), combineTrees(), makeEmpty(), clone())

Principle: Insert the objects to be sorted into the previous sorted sequence by keywords in each step

Process: 1≤j<n, compare a[j] with a[0..j-1] from right to left, insert into the appropriate position

Example diagram: Show the sorting process

Algorithm: insertionSort(vector<Comparable> &a), double-layer loop, tmp temporary storage a[p], insert after moving

Time complexity: O(N²) (worst reverse order), O(N) (best sorted), suitable for situations where there are few elements and close sorting

Fold and half insert sort: Use fold and half to find the insertion position to reduce the number of comparisons, and still need to move the elements, O(N²)

Hill sort: See Section 6.4

Take gap<n, divide gap subsequences (distance gap), and insert and sort each subsequence simply

Shrink gap, repeat until gap=1

buildHeap build heap (O(N))

N times deleteMin to take the element, and the result sorting (O(NlogN))

Problem: Double space required (heap result)

Solution: After deleteMin, the heap is reduced, the deleted elements are stored at the last position, and the maximum heap is incrementally sorted

Thought: Merge two sorted ordered tables, divide and govern

Merge example: Show the process of combining two ordered numbers

Merge sorting method:

Example diagram: Showcase the merger and sorting process

Package function: mergeSort(vector<Comparable> &a), create tmpArray, call mergeSort with parameter

mergeSort with parameter: mergeSort(a, tmpArray, left, right), recursively sort left and right, merge

merge function: merge(a, tmpArray, leftPos, rightPos, rightEnd), merge two ordered subarrays, and copy them back to the original array

Time complexity: O(NlogN), additional space required

step:

Key: Select the center point and divide it

Error method: Select the first element, sorted/inversely divided difference, O(N²)

Safe selection: random selection, time-consuming

The median value division of three elements: select the first, middle, and tail median, example (select 6 of 8, 1, 4, etc.), avoid the different sorting of the

process:

Example: Showcase the partitioning process (8, 1, 4, etc.)

Small scale (≤10) sort with insertion, terminate recursively to improve efficiency

Package function: quicksort(vector<Comparable> &a), call quicksort with parameter

median3 function: select the median value of three elements and put right-1

Quicksort with parameter: quicksort(a, left, right), sort with insertion on a small scale, otherwise choose pivot, divide, and recursively sort left and right.

Time complexity:

Quickselect(S,k):

Time: Worst O(N²), Average O(N)

The input is an arrangement of 1..N, a total of N!

The number of comparisons determines the arrangement. Each comparison is halved and the arrangement is possible. Log(N!) comparisons are required.

log(N!)≈NlogN-1.44N, so at least O(NlogN)

Device dependency: Consider tape, 2-3 tape drives are required

Assumption: 4 tapes A1, A2, B1, B2, M records are stored in memory

process:

Example diagram: Shows the initial and merged tape configuration

Time: log(N/M) times merge, add initial run construct

Principle: K-way merge reduces the number of mergers, and use the priority queue to find the minimum K elements

Example: 6 tapes and 3 channels merge, display process

Time: log_K (N/M) merge

Principle: K 1 tape realizes K-way merger, non-uniform distribution run

Example: 3 tapes 34 runs, distributions 21 and 13, showing the merge process

Initial run distribution: Fibonacci number, if not enough, fill in virtual run

Principle: Generate longer runs, read M elements to build heap, deleteMin output, read the element larger than the output, insert it, otherwise the spare position is stored, and the heap is empty will be new run (use spare element)

Example: 81, 94 and other generation run, display process

union: merge two trees (roots are subtrees), O(1)

find: find root, O(N) (worst)

Merge by scale: small trees are large subtrees, and the roots have negative scale

Example diagram: Show the difference between normal and by scale

Theorem: merge by scale, node depth ≤logN

Combined by height: shallow trees are deep subtrees, roots are

Class definition: DisjointSet class, including set (array), size members, and constructor, find(), and Union() functions

Member functions: construct (initialize set to -1), find() (find root), Union() (combined by scale)

Use: Sample code (find, Union operation, output result)

Initial: Full wall, unit is not connected

Select the wall randomly. If the partition unit is not connected, the wall will be demolished. Combine the equivalent category.

Repeat until fully connected

Connection is an equivalent relationship, unit number, adjoining unit judgment, wall removal and merge

Example diagram: Show the initial and wall removal process

Definition: G=(V,E), V vertex set, E edge (arc) set

Classification:

Adjacent: Directed graph Vi is adjacent to Vj, undirected graph Vi is adjacent to Vj

Degree: the number of adjacent edges of the undirected graph; the incoming degree (incoming edges), the outgoing degree (outgoing edges) of the directed graph

Sub-picture: G'=(V',E'), V'⊆V, E'⊆E, sample diagram

Undirected graph connectivity:

Directed graph connectivity:

Complete graph: undirected complete graph (n(n-1)/2 edge), directed complete graph (n(n-1) edge), example graph

Directed Acyclic Graph (DAG): Acyclic