Data structure and algorithm 2020 notes
1, Linear structure and nonlinear structure
1.1 linear structure (9.17)
Common linear structures: array, queue, linked list, stack
Sequential storage structure (array) and chain storage structure, onetoone linear relationship
Onetoone array structure, nonlinear array structure, nonlinear tree structure
1.2 sparse array
When most elements in an array are 0 or an array with the same value, sparse array can be used to save the array
Treatment method:
 How many rows and columns are there in the record array? How many different values are there
 Record the rows, columns and values of elements with different values in a smallscale array, so as to reduce the size of the program (compression)
 Used to preserve twodimensional arrays (chessboard, map, etc.)
1.3 queue
 Ordered list (array, linked list)
 First in first out
1.3.1 array simulation queue
Disadvantages: cannot be reused
1.3.2 array simulation ring queue
 Conditions for queue full: (rear + 1)% maxSize = front
 Queue is empty: rear == front
 Initial value: front == rear == 0
 Number of valid data in the queue: (rear + maxSize  front)% maxSize (common small algorithm)
1.4 linked list
 Linked list is stored in the form of nodes, chain storage
 Each node contains the data field, and the next field: points to the next node
 The nodes of the linked list are not necessarily stored continuously
 Lead node and headless node. The head node does not store any data and is used to find the linked list entry
//Creation of oneway linked list private HeroNode head = new HeroNode(0, ""); //Join last public void add(HeroNode heroNode) { HeroNode temp = head; while (true) { if (temp.next == null) { break; } //If the last is not found, move temp back temp = temp.next; } temp.next = heroNode; } //Display linked list (traversal) public void list(){ if (head.next == null) { return ; } //The head node cannot be moved and needs an auxiliary variable to traverse HeroNode temp = head.next; while (true) { if (temp == null){ break; } //syso node //Move the temp backward and be careful of the dead cycle temp = temp.next; } } class HeroNode { public int no; public String name; public HeroNode next; } /* Add in order: new nodes next = temp.next; temp.next = new node; */ public void addByOrder(HeroNode heroNode){ //Single linked list: the temp to be found is the previous node of the addition location, otherwise it cannot be added HeroNode temp = head; boolean flag = false; // Judge whether the added number exists while (true) { if (temp.next == null) { break; } if (temp.next.no > heroNode.no) { break; } else if (temp.next.no == heroNode.no) { flag = true; break; } temp = temp.next; // Move back and traverse the current linked list } //Judge the value of flag if (flag) { //syso exists and cannot be added } else { heroNode.next = temp.next; temp.next = heroNode; } }
Modify node \ delete node
public void update(HeroNode heroNode) { if (head.next == null) { return; } HeroNode temp = new HeroNode(); temp = head; while (heroNode.no != temp.next.no && temp.next != null) { update(); temp = temp.next; } if (temp.next == null) return; else update(); }
1.4.1 bidirectional linked list
 One way linked list can only be traversed and searched from one direction
 A oneway linked list cannot be deleted by itself and needs to rely on auxiliary nodes, while a twoway linked list can be deleted by itself. When a single linked list deletes a node, you should find temp, which is the previous node of the node to be deleted.
1.5.2 one way circular linked list & Joseph problem
Joseph's problem: let n people with numbers 1, 2,..., n sit around. It is agreed that the person with number k (1 < = k < = n) will count from 1, the person who counts to m will be listed, his next person will start counting, and so on until everyone is listed, resulting in a sequence of out of line numbers.
Solution: circular linked list, array module
public class Josepfu { public static void main(String[] args){ } } class CircleSingleLinkedList{ //first node private Boy first = new Boy(1); public void addBoy(int nums) { if (nums < 1) { return; } //Use the for loop to create a circular linked list Boy curBoy = null; for (int i = 1; i <= nums; i++){ //According to the number, create a child node and an auxiliary node cur Boy boy = new Boy(i); if (i == 1) { first = boy; first.setNext(first);//Constituent ring curBoy = first; } else { } } } } //Traverse circular linked list public void showEle() { if (first == null) { return; } Boy cur = first; while (true) { //syso show cur.no cur = cur.getNext(); if (cur == first) break; } } class Boy{ private int no ; private Boy next; }
Loop out analysis of ring linked list:
 You need to create an auxiliary variable helper to point to the last node of the ring linked list in advance (while loop traversal points to the last node)
 Before counting off, let the first and helper move k1 times to the location of the K node
 When counting, let the first and helper move m1 times at the same time
 At this time, circle the child node pointed to by first. First = first next helper. next = first
2, Stack
2.1 introduction to stack
 Ordered list of first in first out
 The top of the stack is the changing end, the insertion and deletion operations, and the bottom of the stack is the fixed end
 Out of stack pop
 Stack push
2.2 application scenarios
 Subroutine calling, processing and recursive calling
 Conversion and evaluation of expressions
 Traversal of binary tree
 Depth first search of graphics
2.3 use of array simulation stack
Train of thought analysis:
 Define a top to represent the top of the stack, which is initialized to  1,
 Stack operation: Top + +; stack[top] = value;
 Stack out operation: int value = stack[top]; top–; return value;
 When traversing, the data is displayed from the top of the stack
//Judge whether the stack is empty and exit the stack public int pop() { if (isEmpty()) { throw new RuntimeException("Stack empty, no data"); } int value = stack[top]; top; return value; }
2.4 simulate stack with linked list (null)
3, Prefix, infix, suffix expression
3.1 prefix expression (Polish expression)
 The operator of the prefix expression precedes the operand
 The prefix expression corresponding to (3 + 4) * 5  6 is  * + 3 4 5 6
 Computer evaluation method: scan the expression from right to left. When encountering a number, push the number into the stack. When encountering an operator, pop up the two numbers at the top of the stack, use the operator to calculate the corresponding (top element and secondary top element), and put the result into the stack. Repeat the above process until the leftmost end of the expression. The final value is the result of the expression.
 For the above expression, press 6 5 4 3 from right to left, get 7 when encountering + pop 3 4, and then enter the stack when encountering * pop 7 * 5 = 35, 35... At this time, 35 is at the top of the stack
3.2 infix expression
 Is a common operation expression
 However, it is not easy for computers to operate (because infix expressions need to judge the priority of operators and the priority of subsequent operators). When calculating the results, infix expressions are often converted into other expressions (generally suffix expressions)
3.3 suffix expression
 Also known as inverse Polish expression
 Similar to the prefix, except that the operator follows the operand
 (3 + 4) * 56: suffix expression: 3 4 + 5 * 6  35 is under 6
 4 * 5  8 + 60 + 8 / 2  4 5 * 8  60 + 8 2 / +
3.4 inverse Polish calculator (partial code)
//Put the inverse Polish expression, and put the data and operators in sequence, such as 3, 4 + 5 * 6 in ArrayList public static List<String> getListString(String str){ String[] split = str.split(" "); List<String> List = new ArrayList<String>(); for (String ele : split) { list.add(ele); } return list; } //calculation public static int calculate(List<String> ls){ Stack<String> stack = new Stack<String>(); for (String item : ls) { if (item.matches("\\d+")) { //Push stack.push(item); } else { //pop out two numbers, operate them, and then put them on the stack int num2 = Integer.parseInt(stack.pop()); int num1 = Integer.parseInt(stack.pop()); int res = 0; if (item.equals("+")){ res = num1 + num2; } else if (item.equals("")){ res = num1  num2; } else if (item.equals("*")){ res = num1 * num2; } else if (item.equals("/")){ res = num1 /num2; } else { throw new Exception("error"); } stack.push(res + ""); } } return Integer.parseInt(stack.pop()); }
3.5 thinking analysis of infix to suffix expression (9.20)
code:
//Infix expression is converted to the corresponding list, and then infix expression is converted to suffix expression public static List<String> toInfixExpressionList(String s) { List<String> ls = new ArrayList<String>(); int i = 0; String str; char c; do { if ((c = s.charAt(i)) < 48  (c = s.charAt(i)) > 57) { ls.add("" + c); i++; } else { //If it is a number, multiple numbers need to be considered str = "";//First set str to "" '0' [48]  > '9' [57] while (i < s.length() && (c = s.charAt(i)) >= 48 && (c = s.charAt(i)) <= 57) { str += c; i++; } ls.add(str); } } while (i < s.length()); return ls; } //Infix to suffix public static List<String> parseSuffixExpressionList(List<String> ls){ //Define two stacks Stack<String> s1 = new Stack<String>(); //Symbol stack //Because s2 stack has no pop operation in the whole conversion process, and it needs to be output in reverse order, so list is used //Stack<String> s2 = new Stack<String>(); List<String> s2 = new ArrayList<String>(); // list2 for storing intermediate results //Traversal ls for (String item : ls) { //If it's a number, add s2 if (item.matches("\\d+")) { s2.add(item); } else if (item.equals("(")) { s1.push(item); } else if (item.equals(")")) { while (!s1.peek().equals("(")){ s2.add(s1.pop()); } s1.pop(); //Pop up( } else { while (s1.size() != 0 && Operation.getValue(s1.peek()) >= Operation.getValue(item)) { s2.add(s1.pop()); } s1.push(item); } } //Pop the operators in the remaining s1 into s2 in turn while (s1.size() != 0) { s2.add(s1.pop()); } return s2; } //Writing an Operation class can return the priority corresponding to an operator class Operation{ private static int ADD = 1; private static int SUB = 1; private static int MUL = 2; private static int DIV = 2; public static int getValue(String operation){ int result = 0; switch (operation) { case "+" : result = ADD; break; case "" : result = SUB; break; case "*" : result = MUL; break; case "/" : result = DIV; break; default : //syso : not exsist; break; } return result; } }
4, Recursion
4.1 application scenario & problem solving
recursion: maze problem (backtracking), printing problem, factorial problem
Problem solving: eight queens problem, Hanoi Tower, factorial, maze, ball and basket, fast row, merge sort, binary search, divide and conquer algorithm, shortest path, minimum spanning tree, problems solved by stack, etc
Call rule:
 When the program executes a method, it will open up an independent space (stack)
 The local variables of the method are independent and will not affect each other
 Reference type variables (in the stack) will share data (such as arrays)
 return end method
4.2 maze problem
4.3 eight queens problem
A typical case of backtracking algorithm: eight queens are placed on an 8 * 8 grid chess. Any two queens cannot be in the same row, column, or slash. Ask how many pendulum methods there are.
92 species
4.3.1 array solution
The number of backtracking reaches 1w5, which is relatively large
//Write a method to place the n th queen private void check(int n) { if (n == max) {//max = 8 print(); return; } for (int i = 0; i < max; i++) { //First, put the current queen n in the first column of the row array[n] = i; //Judge whether there is a conflict when the nth queen is currently placed in column i if (judge(n)) { //No conflict, then put n+1 queens and start recursion check(n+1); // } //If there is a conflict, continue to execute array[n] = i; That is, the nth queen is placed in the backward position of the line } } //Judge whether the placed queen conflicts with the position in front private boolean judge(int n) { for (int i = 0; i < n; i ++) { // Growth by line // 1.array[i] == array[n] means to judge whether the nth queen is in the same column as the previous queen // 2.Math.abs(ni) == Math.abs(array[n]  array[i]) determines whether the nth queen is on the same slash as the ith queen if (array[i] == array[n]  Math.abs(ni) == Math.abs(array[n]  array[i])) { return false; } } return true; }
5, Sorting algorithm
5.1 classification of sorting
 Internal sorting (all sorting operations are completed in memory)
: load all data to be processed into internal memory for sorting
: insert sort (direct insert sort, Hill sort), select sort (simple select sort, heap sort), exchange sort (bubble sort, quick sort)
, merge sort, cardinal sort  External sorting method (put data on disk and sort through disk and memory transmission)
5.2 time complexity
Ex post statistical method and ex ante estimation method
5.2.1 time and frequency
The number of statements executed in an algorithm is called statement frequency or time frequency, which is recorded as T(n)
 Ignore constant term: T(n) = 2n = 2n + 10
 Ignore the lower order: T(n^2) = n^2 + 5n + 10 = 3n ^2, perform curve coincidence
 The coefficients of higherorder terms can be ignored. n^3+5n and 6n^3 + 4n, perform curve separation, and explain how much power is the key
5.2.2 calculation of time complexity
5.2.3 common time complexity
 Constant order O(1): no matter how many lines of code are executed, as long as there is no complex structure such as loop, the time complexity of this code is O(1); (code execution does not increase with the growth of a variable)
 O(logN):
 Linear order O(n):
 Linear order (nlogo):
 ...
5.2.4 average time complexity and worst time complexity
5.2.5 space complexity
A measure of the amount of storage space temporarily occupied by an algorithm during operation. The essence of some cache products and algorithms (cardinality sorting, fast sorting and merging) is to trade space for time.
5.3 bubble sorting (9.21)
 A total of  1 cycles of array size are carried out, and the maximum number is ranked last in each sorting
 The number of sortings per trip is gradually decreasing
 If there is no exchange in a certain sort, the bubble sort can be ended in advance. (optimized)
//O(n^2) public void BubbleSort(int[] arr){ int temp = 0; boolean flag = false;//Identify variables and whether they have been exchanged for simple optimization for (int i = arr.length  1; i >= 0; i){ for (int j = 0; j < i; j++){ if (arr[j] > arr[j + 1]) { flag = true; temp = arr[j + 1]; arr[j + 1] = arr[j]; arr[j] = temp; } } if(!flag){ break; } else { flag = false; } } //for (int i = 0; i < arr.length1; i++) // for (int j = 0; j < arr.length  1  i; j++){} }
5.4 selection and sorting
Select the value of the specified size, put it into the specified position according to certain rules, and get the sequence from small to large by traversing n1 times
First simple and then complex, the complex algorithm is divided into simple problems and then integrated
//Faster than bubble sorting in time public static void selectSort(int[] arr) { for (int i = 0; i < arr.length 1; i++){ int minIndex = i; int min = arr[i]; for (int j = i; j < arr.length  1; j++){ if (arr[j] < min) { minIndex = j; min = arr[j]; } } if (minIndex != i){ arr[minIndex] = arr[i]; arr[i] = min; } } }
5.5 insert sort
Basic idea: regard the n elements to be sorted as an ordered table and an unordered table, take out the first element from the unordered table each time, and insert it into the appropriate position of the ordered table.
public static void InsertSort(int[] arr){ for (int i = 1; i < arr.length; i++){ int insertVal = arr[i]; int insertIndex = i  1; //The number to be inserted into the unordered list is compared with the previous subscript //Find the insertion position for insertVal /* 1.insertVal >= 0, Prevent crossborder 2.insertVal < arr[insertIndex] compare 3.arr[insertIndex] Move back */ while (insertIndex >= 0 && insertVal < arr[insertIndex]) { arr[insertIndex + 1] = arr[insertIndex]; insertIndex; } //if (insertIndex+1 == i) arr[insertIndex + 1] = insertVal; } }
5.6 Hill sorting
Possible problems with simple insertion sorting:
When the number of inserts is small, the number of backward moves increases significantly, and the efficiency will be affected
Hill sorting introduction: reduce incremental sorting and insert an efficient version of sorting
Basic idea: group according to a certain increment of subscript, and use insertion sorting for each group. As the increment decreases, it decreases to 1
5.6.1 exchange method
public static void shellSort(int[] arr){ for (int gap = arr.length / 2; gap > 0; gap /= 2) { for (int i = gap; i < arr.length; i++){ //Traverse all elements in each group (a total of gap groups, each group has), step gap for (int j = i  gap; j >= 0; j = gap) { if (arr[j] > arr[j + gap]){ temp = arr[j]; arr[j] = arr[j + gap]; arr[j + gap] = temp; } } } } //Low efficiency }
5.6.2 displacement method
//nlogn  n ^ (1~2) //Optimize the Hill sort of exchange public static void shellSort2(int[] arr) { //Incremental gap for (int gap = arr.length / 2; gap > 0; gap /= 2) { for (int i = gap; i < arr.length; i++){ int j = i; int temp = arr[j]; if (arr[j] < arr[j  gap]){ while (j  gap >= 0 && temp < arr[j  gap]) { //move arr[j] = arr[j  gap]; j = gap; } //After exiting the while loop, explain to find the insertion location for temp arr[j] = temp; } } } }
5.7 quick sort
Basic idea: an improvement of bubble sorting. Through onetime sorting, the data to be sorted is divided into two independent parts. All the data in one part is smaller than all the data in the other part, and then the two parts are sorted quickly, which can be carried out in the same recursive way, so as to make the whole data orderly.
Code implementation:
//Recursive implementation of nlogn  n^2 recursion uses the stack to open up space and change space for time public static void quickSort(int[] arr, int left, int right) { int l = left; int r = right; //Central axis value int pivot = arr[(left + right) / 2]; int temp = 0; //The purpose of the while loop is to put those smaller than the pivot value on the left and those larger on the right while ( l < r ){ //Keep looking on the left of pivot while (arr[l] < pivot) { l += 1; } while (arr[r] > pivot) { r = 1; } if (l >= r) { break; } //exchange temp = arr[l]; arr[l] = arr[r]; arr[r] = temp; //If after the exchange, it is found that arr [l] = = the value of pivot, equal r , move forward and reach the median value, stop the cycle if (arr[l] == pivot) r = 1; if (arr[r] == pivot) l += 1; } //If l == r, it must be L + +, r , otherwise the stack overflows if (l == r) { l+= 1; r= 1; } if (left < r) quickSort(arr, left, r); if (right > l) quickSort(arr, l, right); }
5.8 merge sort
Merge sort, using divide and conquer strategy
Rule: merge two ordered subsequences into one ordered sequence,
mergeSort: O(nlogN)
public static void mergeSort(int[] arr, int left, int mid, int right, int[] temp) { if (left < right) { int mid = (left + right) / 2; //Decompose recursively to the left mergeSort(arr, left, mid, temp); //right mergeSort(arr, mid + 1, right, temp); // To merge merge(arr, left, mid, right, temp); } } public static void merge(int[] arr, int left, int mid, int right, int[] temp){ int i = left; int j = mid + 1; int t = 0; // Current index to temp //First fill the left and right (ordered) data into the temp array until one side is processed while (i <= mid && j <= right) { if (arr[i] <= arr[j]){ temp[t] = arr[i]; t += 1; i += 1; } else { temp[t] = arr[j]; t += 1; j += 1; } } //Fill remaining while (i <= mid) { //Left remaining temp[t] = arr[i]; t+=1; i+=1; } while (j <= right){ temp[t] = arr[j]; t+=1; j+=1; } //Copy the elements of temp array to arr t = 0; int tempLeft = left; while (tempLeft <= right) { // Merge 0, 1, 2, 3, 0, 3 for the first time. arr[tempLeft] = temp[t]; t += 1; tempLeft += 1; } }
5.9 cardinality sorting (bucket sorting extension)
 The elements to be sorted are assigned to some buckets by the value of each bit of the key value
 Cardinality sorting is an extension of bucket sorting
 Invented by Herman hollery in 1887: the integer is cut into different numbers according to the number of digits, and then compared according to each digit
 Stability ranking: 3 1 4 1 "1 1 3 4, the first 1 is still in the front
 Basic idea: unify all the values to be compared into the same digit length, fill zero in front of the number with shorter digits, and then sort them successively from the lowest bit.
public static void radixSort(int[] arr) { //Define a twodimensional array, representing 10 buckets, and each bucket is a onedimensional array //Cardinality sorting: the classical operation of space for time int[][] bucket = new int[10][arr.length]; //In order to record how many data are actually stored in each bucket, a onedimensional array is defined to record the number of data put in each bucket //For example, bucketElementCounts[0] records the number of data put into the bucket[0] int[] bucketElementCounts = new int[10]; //The first round of sorting is to sort the bits of each element for (int j = 0; j < arr.length; j++) { //Take out the single digit of each element int digitOfElement = arr[j] / 1 % 10; //Put it into the corresponding bucket bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j]; bucketElementCounts[digitOfElement]++; } //According to the order of this bucket (the subscript of onedimensional array takes out the data in turn and puts it into the original array) int index = 0; //Traverse each bucket and put the data in the bucket into the original array for (int k = 0; k < bucketElementCounts.length; k++){ //Judge whether there is data in the bucket if (bucketElementCounts[k] != 0) { // for (int l = 0; l < bucketElementCounts[k]; l++){ arr[index++] = bucket[k][l]; //++ } } //After the first round of processing, bucketelementcounts [k] = 0, the bucket array needs to be emptied bucketElementCounts[k] = 0; } //***********First round************************* //The second round: take ten arr[j] / 10% 10; 748 / 10 > 74 % 10 > 4 } public static void radixSort2(int[] arr) { //Final code //1. Get the maximum number of digits in the array int max = arr[0]; for (int i = 1; i < arr.length; i++) { if (arr[i] > max) { max = arr[i]; } } int[][] bucket = new int[10][arr.length]; //What is the maximum number int maxLength = (max + "").length(); int[] bucketElementCounts = new int[10]; for (int i = 0, n = 1; i < maxLength; i++, n *= 10){ //Sort the corresponding bits of each element, including single bit, ten bit for (int j = 0; j < arr.length; j++) { int digitOfElement = arr[j] / n % 10; //** n ** //Put it into the corresponding bucket bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j]; bucketElementCounts[digitOfElement]++; } //According to the order of this bucket (the subscript of onedimensional array takes out the data in turn and puts it into the original array) int index = 0; //Traverse each bucket and put the data in the bucket into the original array for (int k = 0; k < bucketElementCounts.length; k++){ //Judge whether there is data in the bucket if (bucketElementCounts[k] != 0) { // for (int l = 0; l < bucketElementCounts[k]; l++){ arr[index++] = bucket[k][l]; //++ } } //After the first round of processing, bucketelementcounts [k] = 0, the bucket array needs to be emptied bucketElementCounts[k] = 0; } } }
matters needing attention:
 The amount of data is too large, resulting in heap memory overflow
 Negative numbers cannot be sorted directly. If you want to deal with negative numbers, you need to improve.
6, Search algorithm (9.22)
 Sequential (linear) lookup
 Binary search
 Interpolation search
 fibonacci search
6.1 binary search
Binary search needs to find an ordered array
public static int binarySearch(int[] arr, int left, int right, int findVal){ //Not found, end recursion if (left > right> return 1; int mid = (left + right) / 2; int midVal = arr[mid]; if (findVal > midVal) { return binarySearch(arr, mid + 1, right, findVal); } else if (findVal < midVal) { return binarySearch(arr, left, mid  1, findVal); } else { return mid; /* Add an index that returns all the same values List<Integer> resIndexList = new ArrayList<Integer>(); int temp = mid  1; while (true){ if (temp < 0  arr[temp] != findVal) {break;} resIndexlist.add(temp); temp = 1; //temp Shift left } resIndexlist.add(mid); //Scan right temp = mid + 1; while (true){ if (temp > arr.length  1  arr[temp] != findVal) {break;} resIndexlist.add(temp); temp += 1; //temp Shift right } return resIndexlist */ } }
6.2 interpolation search
//Write interpolation search algorithm (sequence order is required) public static int insertValueSearch(int[] arr, int left, int right, int findVal) { if (left > right  findVal < arr[0]  findVal > arr[arr.length  1]) return 1; int mid = left + (right  left) * (findVal  arr[left]) / (arr[right]  arr[left]); int midVal = arr[mid]; if (findVal > midVal) { return insertValueSearch(arr, mid + 1, right, findVal); } else if (findVal < midVal) { return insertValueSearch(arr, left, mid  1, findVal); } else { return mid; } } //Note: for the lookup table with large amount of data and uniform keyword distribution, interpolation search is faster //Uneven (great jumping), not necessarily better than two points
6.3 Fibonacci (golden section) search algorithm
 Golden section point: a line segment is divided into two parts. The ratio of one part to the whole length is equal to that of the other part, with an approximate value of 0.618
 The ratio of two adjacent numbers in Fibonacci sequence is infinitely close to the golden section value of 0.618
//To create a Fibonacci sequence non recursively, you need to create a Fibonacci sequence first public static int[] fib(){ int[] f = new int[maxSize]; f[0] = 1; f[1] = 1; for (int i = 2; i < maxSize; i++){ f[i] = f[i  1] + f[i  2]; } return f; } //If the length of Fibonacci is not enough by using non recursion, it needs to be supplemented public static int fibSearch(int[] a, int key) { int low = 0; int high = a.length  1; int k = 0;//Subscript representing the Fibonacci division value int mid = 0; int f[] = fib(); //Get k while(high > f[k]  1) { k++; } //Because the value of f[k] may be greater than the length of a, we need to construct a new array int[] temp = Arrays.copyOf(a, f[k]); for (int i = high + 1; i < temp.length; i++) { temp[i] = a[high]; } //Use the while loop to find the key while (low <= high) { mid = low + f[k  1]  1; if (key < temp[mid]) { //Find left high = mid  1; k; } else if (key > temp[mid]) { //Find right low = mid + 1; //f[k] = f[k1] + f[k2]; So we continue the segmentation from the part of F [K2] k = 2; } else { //When you find it, make sure to put the subscript back if (mid <= high) { return mid; } else { return high; } } } }
7, Hash table
java program > cache products (redis, memcache) / hash table (array + linked list, array + binary tree) > L2 cache > Database
Hash table: (hash table), a data structure accessed according to the key value. Records are accessed by mapping the key value to a position in the table to speed up the search. This mapping function is called hash function, and the array storing records is called Hash list.
Manage employee information with hash table:
public class HashTabDemo{ } //Create hashTab to manage multiple linked lists class HashTab{ private EmpListedList[] empLinkedListArray; private int size; // public HashTab(int size) { this.size = size; empLinkedListArray = new EmpLinkedList[size]; // } //Add employee public void add(Emp emp) { //According to the employee's id, get the linked list to which the employee should be added int empLinkedListNo = hashFun(emp.id); empLinkedListArray[empLinkedListNo].add(emp); } //Traverse all linked lists public void list(){ for (int i = 0; i < size; i++) { empLinkedListArray[i].list(); } } //Hash function, using simple modular method public int hashFun(int id) { return id % size; } //Find the employee based on the entered id public void findEmpById(int id){ int empLinkedListNo = hashFun(id); Emp emp = empLinkedListArray[empLinkedListNo].findeEmpById(id); if (emp == null) {} else {} } } class Emp{ public int id; public String name; public Emp next; public Emp(){ } } class EmpLinkedList{ //Header pointer, execute the first emp private Emp head; //Add employee to linked list public void add(Emp emp) { if (head == null) { head = emp; return; } //Not the first, use the auxiliary pointer to locate the last Emp curEmp = head; while(true) { if (curEmp.next == null) { break; } curEmp = curEmp.next; } curEmp.next = emp; } //Employee information traversing the linked list public void list(){ if (head == null) { return; } Emp cuEmp = head; while (true){ //syso id\name if(curEmp.next == null) break; curEmp = curEmp.next; } } //Find employees by id public Emp findEmpById(int id) { //Determine whether the linked list is empty if (head == null) { return null; } //Auxiliary pointer Emp curEmp = head; while (true) { if (curEmp.id == id) { break; } if (curEmp.next == null){ curEmp = null; break; } curEmp = curEmp.next; } return curEmp; } }
8, Tree
8.1 Foundation (r1 9.26)
8.2 binary tree
 A tree with up to two child nodes per node
 Child nodes are divided into left nodes and right nodes
 If all leaf nodes of the binary tree are in the last layer, and the total number of nodes = 2^n1,n is the number of layers, which is called full binary tree
 If all leaf nodes of the binary tree are in the last or penultimate layer, and the leaf nodes of the last layer are continuous on the left and the leaf nodes of the penultimate layer are continuous on the right, it is called a complete binary tree.
 According to the output of the parent node, traversal is divided into the first, middle and last three types. Pre order traversal: first output the parent node, left subtree, right subtree, and so on.
public class BinaryTreeDemo { main{ } } //Define BinaryTree binary tree class BinaryTree { private HeroNode root; public void setRoot(HeroNode root){ this.root = root; } public void preOrder() { if (this.root != null) { this.root.preOrder(); } else //syso null {} } public void infixOrder() { } //Postorder traversal public void postOrder(){ } } class HeroNode { private int no; private String name; private HeroNode left; private HeroNode right; public HeroNode(int no, String name) { super(); this.no = no; this.name = name; } //get set //toString //Write preorder traversal public void preOrder() { //syso this if (this.left != null) { this.left.preOrder(); } if (this.right != null) { this.right.preOrder(); } } //Middle order traversal public void infixOrder(){ if (this.left != null){ this.left.infixOrder(); } //syso this if (this.right != null){ this.right.infixOrder(); } } //Postorder traversal public void postOrder(){ if (this.left != null){ this.left.postOrder(); } if (this.right != null) { this.right.postOrder(); } //syso this } }
8.2.1 binary tree  find the specified node
//Preorder traversal public HeroNode preOrderSearch(int no) { if (root != null) return root.postOrderSearch(no); else return null; } //Preorder traversal search public HeroNode preOrdersearch(int no) { //Compare whether the current node is if (this.no == no) { return this; } //Then judge whether the left child node of the current node is empty. If not, recursive preorder search HeroNode resNode = null; if (this.left != null) { resNode = this.left.preOrderesearch(no); } if (resNode != null) return resNode; //1. Left recursive preorder search //2. Right if (this.right != null) resNode = this.right.preOrdersearch(no); return resNode; }
8.2.2 deleting nodes
//Simple requirements: 1 Directly delete leaf nodes, 2 Delete subtree for non leaf node //Idea: 1 Because the binary tree is oneway, we judge whether the child nodes of the current node need to be deleted, rather than whether the node needs to be deleted //Because the parent node cannot be found directly //2 consider whether it is an empty tree root or just one root node //binaryTree public void delNode(int no) { if (root != null) { if (root.getNo() == no) { root = null; }else { root.delNode(no); } } else { //syso null } } //Recursively delete nodes public void delNode(int no) { if (this.left != null && this.left.no == no) { this.left = null; return; } if (this.right != null && this.right.no == no){ this.right = null; return; } if (this.left != null) { this.left.delNode(no); } if (this.right != null) { this.right.delNode(no); } }
Binary tree storage order
Basic description: from the perspective of data storage, the storage mode of array and tree can be converted to each other.
characteristic:
 Sequential binary trees usually only consider complete binary trees
 The left child node of the nth element is 2 * n + 1; The right child node is 2 * n + 2; Parent node is (n  1) / 2
class ArrBinaryTree{ private int[] arr;// An array that stores data nodes public ArrBinaryTree(int[] arr) { this.arr = arr; } public void preOrder(){ this.preOrder(0); } //Write a method to complete the preorder traversal of the sequential storage binary tree public void preOrder(int index) { //If the array is empty, or arr.length = 0 if (arr == null  arr.length == 0) //syso is null if (index * 2 + 1 < arr.length) { preOrder(2 * index + 1); } //Right recursive traversal if ((index * 2 + 2) < arr.length) { } } }
8.4 cued binary tree (9.23)
Basic introduction:
 The binary list of N nodes contains n + 1 (2n  (n  1) = n + 1) empty finger fields. The null pointer field in the binary linked list is used to store the pointer to the predecessor and successor nodes of the node in a certain traversal order (this additional pointer is called clue)
 Clue linked list, clue binary tree, pre order clue binary tree, middle order clue binary tree, post order
 Precursor node: the previous node of a node
//Medium order cued subtree public void threadedNodes(HeroNode node) { //If node == null, it cannot be threaded if (node == null) return; //1. Cued left subtree threadedNodes(node.getLeft()); //2. Cue the current node //Process the precursor node of the current node if (node.getLeft() == null) { //Make the left pointer of the current node point to the predecessor node node.setLeft(pre); //The pointer to the current node type is modified to the left node.setLeftType(1); } //Process the successor nodes of the current node //When the node moves to the next node, the point (pre) of the previous node of the node connects the successor to the node if (pre != null && pre.getRight() == null) { pre.setRight(node); pre.setRightType(1); } //*****After each node is processed, let the current node be the precursor node of the next node pre = node; //3. Cued right subtree threadedNodes(node.getRight()); }
8.4.1 traversing cued binary tree
Traverse the binary tree with medium order cueing
Analysis: after cueing, the direction of each node changes, so the original traversal method cannot be used. Each node can be traversed by linear method without recursion, which also improves the efficiency of traversal. The order of traversal should be consistent with that of middle order traversal.
//Method of traversing cued binary tree public void threadedList() { HeroNode node = root; while (node != null) { while (node.getLeftType() == 0){ node = node.getLeft(); } //syso this node while (root.getRightType == 1) { //Gets the successor node of the current node node = node.getRight(); //syso node } //Replace traversed nodes node = node.getRight(); } }
8.5 heap sorting (r1)
 Select sort, unstable sort, complexity O(nlogn)
 Generally, large top pile is used in ascending order and small top pile is used in descending order
 By using the operation of large top heap and small top heap for the array
//i: Index of non leaf node in array //length: decrease gradually, indicating how many elements are adjusted //Adjust an array (binary tree) to a large top heap public static void adjustHeap(int arr[], int i, int length){ int temp = arr[i]; //Start adjustment for (int k = i * 2 + 1; k < length; k = k * 2 + 1) { //i * 2 + 1 is the left child node of node i; k = k * 2 + 1 indicates the next left child node of the current node if (k+1< length && arr[k] < arr[k + 1]) { k++; //K points to the right child node } if (arr[k] > temp) { arr[i] = arr[k]; i = k; } else { break; } } //At the end of the loop, we have placed the maximum value of the tree with i as the parent node at the top (local) arr[i] = temp; } public static void heapSort(int arr[]){ //1. Build an unordered sequence into a heap, and select the large top heap / small top heap according to the ascending and descending requirements //Arr.length/2  1 find the largest non leaf node for (int i = arr.length / 2  1; i >= 0; i){ adjustHeap(arr, i, arr.length); } //This is the large top pile //2. Exchange the top heap element with the end element, and "sink" the largest element to the end of the array //3. Readjust the structure to meet the heap definition, then continue to exchange the top elements of the heap with the current tail elements, and repeat the adjustment + exchange steps until the whole sequence is in order for (int j = arr.length  1; j > 0; j) { //exchange temp = arr[j]; arr[j] = arr[0]; arr[0] = temp; adjustHeap(arr, 0, j); } }
9, Huffman tree
Basic introduction:
 Given n weights as n leaf nodes, a binary tree is constructed. If the weighted path length of the tree reaches the minimum, it is called the optimal binary tree, also known as Huffman tree.
 Huffman tree is the tree with the shortest weighted path length, the node with larger weight is closer to the root, and the tree with the smallest wpl
 The weight points are located in the leaf node
 Take two smallest root nodes to form a binary tree. The weight of the root node of the binary tree is the sum of the two nodes
matters needing attention:
 The file itself is compressed, and the recompression efficiency will not change significantly by using Huffman coding, such as ppt, video and other files
 Huffman can process all text by binary encoding
 If there is not much duplicate data in a file, the compression effect will not be obvious
//Create node class //In order to keep the Node objects sorted, the Collections collection is sorted class Node implements Comparable<Node>{ int value; //Node weight Node left; Node right; public Node (int value){ this.value = value; } //toString @override public int compareTo(Node node) { //Sort from small to large return this.value  o.value; } } public class HuffmanTree{ //Create Huffman tree public static NodeX createHuffmanTree(int[] arr) { //1. Traversal 2 Build each element of arr into Node3 Put Node into ArrayList List<Node> nodes = new ArrayList<Node>(); for (int value : arr) { nodes.add(new Node(value)); } while (nodes.size() > 1) { Collections.sort(nodes); //Take out the node with the smallest weight (binary tree) Node left = nodes.get(0); //Take out the second smallest node Node right = nodes.get(1); // Node parent = new Node(left.value + right.value): parent.left = left; parent.right = right; //Delete the processed binary tree from the list nodes.remove(left); nodes.remove(right); nodes.add(parent); } return nodes.get(0); } }
9.1 Huffman code

A coding algorithm

Huffman coding is widely used in data file compression. The compression rate is usually between 20%  90%, lossless compression

Huffman code is a kind of vlc with variable length coding.

Fixed length encoding: convert all bytes into binary

Variable length coding: first count the occurrence times of characters and code according to the occurrence times of each character. The more the occurrence times, the smaller the coding.

Prefix code: the code of characters cannot be the prefix of other character codes. The code that meets this requirement is called prefix code. That is, duplicate codes cannot be matched.

instable
9.2 data compression
public static void main(String[] args){ String content = ""; byte[] contentBytes = content.getBytes(); } //Receive byte array and put it back in list private static List<Node> getNodes(byte[] bytes){ //1. Create an ArrayList ArrayList<Node> nodes = new ArrayList<Node>(); //Traverse bytes, count the number of occurrences of each byte, and store it in map Map<Byte, Integer> counts = new HashMap<>(); for (byte b: bytes){ Integer count = counts.get(b); if (count == null) { //New characters encountered for the first time counts.put(b, 1); } else { counts.put(b, count + 1); } } //Convert each key value into a Node object and add it to the nodes collection //Traversal map for (Map.Entry<Byte, Integer> entry : counts.entrySet()) { nodes.add(new Node(entry.getKey(), entry.getValue())); } return nodes; } // private static Node createHuffmanTree(List<Node> nodes) { while (nodes.size() > 1) { //Sort, small to large Collections.sort(nodes); //Take out the first smallest binary tree Node leftNode = nodes.get(0); Node rightNode = nodes.get(1); //Create a new binary tree. Its root node has no data but only weights Node parent = new Node(null, leftNode.weight + rightNode.weight); parent.left = leftNode; parent.right = rightNode; //Delete the two binary trees that have been processed from nodes nodes.remove(leftNode); nodes.remove(rightNode); //Add a new binary tree to nodes nodes.add(parent); } //The last node of nodes is the root node return nodes.get(0); } //Create Node, data and weight class Node implements Comparable<Node>{ Byte data; //Store the data (character) itself, such as' a ' 97 int weight; //Weight (number of characters) Node left; Node right; public Node(Byte data, int weight) { super(); this.data = data; this.weight = weight; } @Override public int compareTo(Node o) { //Sort from small to large return this.weight  o.weight; } //toString //Preorder traversal public void preOrder(){ //syso this if (this.left != null) this.left.preOrder(); if (this.right != null) this.right.preOrder(); } }
9.3 generate Huffman code (9.27)
Generating Huffman coding and obtaining Huffman coded data
0 to the left and 1 to the right
//thinking //1. Store Huffman coding table in map, where map < byte, string > // Form: 32 > 01, 97 > 100, u > 11001 // 2. While generating Huffman coding table, continuously splice character paths and define a path where StringBuilder stores a leaf node static StringBuilder stringBuilder = new StringBuilder(); static Map<Byte, String> huffmanCodes = new HashMap<Byte, String>(); main{ List<Node> nodes = getNodes(contentBytes); Node huffmanTreeRoot = createHuffmanTree(nodes); getCodes(huffmanTreeRoot, "", sb);// Root node is empty } //The Huffman codes of all leaf nodes of the incoming node node are obtained and put into the Huffman codes collection //code the left child node is 0 and the right child node is 1 private static void getCodes(Node node, String code, StringBuilder sb){ StringBuilder sb2 = new StringBuilder(sb); sb2.append(code); if (node != null) { //Judge whether the current node is a leaf node or a non leaf node if (node.data == null) { //Recursive processing of non leaf nodes getCodes(node.left, "0", sb2); getCodes(node.right, "1", sb2); } else { //Indicates that the last node of a leaf is found huffmanCodes.put(node.data, sb2.toString()); } } } //The byte [] array corresponding to the string, through the generated Huffman encoding table, returns a byte [] compressed by Huffman encoding //Get the character array corresponding to Huffman coding table //Input string and output encoded data private static byte[] zip(byte[] bytes, Map<Byte, String> hfCode) { StringBuilder sb = new StringBuilder(); for (byte b : bytes) { sb.append(hfCode.get(b)); } // syso sb.toString(); // Add "101010101010....." Convert to byte [] int len; // (sb.length() + 7) / 8; if (stringBuilder.length() % 8 == 0) { len = sb.length() / 8; } else { len = sb.length() / 8 + 1; } //Create byte array to store compressed data byte[] by = new byte[len]; int index = 0; for (int i = 0; i < sb.length(); i+= 8) { //Every 8 bits corresponds to a byte String strByte; if (i+8 > sb.length()) { //The last time is less than 8 strByte = sb.substring(i); } else { strByte = sb.substring(i, i + 8); } //Convert strbyte into a byte and put it in by by[inde] = (byte)Integer.parserInt(strByte, 2); index++; } }
9.4 data decompression
1. Convert the original Huffman coded character array into binary string
//1. [88,65,56....] > "10101000..." //2. "1010100..." > "i like like..." //Complete the decoding of compressed data // 1 Huffman encoding table 2 character array obtained by Huffman decoding private static byte[] decode(Map<Byte, String> hfcodes, byte[] hfbytes) { //1. Get binary string first StringBuilder sb = new StringBuilder(); // for (int i = 0; i < hfcodes.length; i++){ byte b = hfbytes[i]; boolean flag = (i == hfbytes.length  1); sb.append(byteToBitString(!flag, b)); } //2. Decode the string according to the specified Huffman encoding table // a> 100 > a exchange Map<String, Byte> map = new HashMap<String, Byte>(); for (Map.Entry<Byte, String> entry : hfcodes.entrySet()) { map.put(entry.getValue(), entry.getKey()); } //Create a byte to store for the collection List<Byte> list = new ArrayList<>(); // for (int i = 0; i < sb.length; ){ int count = 1; //Counter boolean flag = true; Byte b = null; while (flag) { //Take out a '1' or '0' String key = sb.substring(i, i+count);//i don't move, count moves until it matches a character b = map.get(key); if (b == null) { count++; } else { //Match to flag = false; } } list.add(b); i+=count; //i move directly to count } // byte b = new byte[list.size()]; for (int i = 0; i < b.length; i++) { b[i] = list.get(i); } return b; } //flag: indicates whether to fill the high bit. The last byte does not need to fill the high bit //return: returns the binary string corresponding to b by complement private static String byteToBitString(boolean flag, byte b) { //1. [88,65,56....] > "10101000..." //Save b with variable int temp = b;// Convert b to int //If it is a positive number, there is a high complement if (flag){ temp = 256; // Bitwise and 256 1 0000  0000 00001 > 1 0000 0001 } String str = Integer.toBinaryString(temp); //The binary complement corresponding to temp is returned if (flag) { return str.substring(str.length()  8); } else { return str; } return }
10, Binary sort tree (BST) (9.28)
Improve retrieval, sorting, addition and deletion
Binary sort tree: (BST: binary sort (search) tree). For any non leaf node of the binary sort tree, the value of the left child node is required to be smaller than that of the current node, and the value of the right child node is required to be larger than that of the current node. The same value is placed on the left or right child node of the point.
10.1 binary sort tree creation and traversal
Create an array into the corresponding binary sort tree, and use the middle order to traverse the binary sort tree (the values traversed by the middle order are orderly)
//Create node class Node { int value; Node left; Node right; //constructor //Add node public void add(Node node) { //Adding nodes in the form of recursion needs to meet the requirements of binary sort tree if (node == null) { return; } //Judge the value of the incoming node and its relationship with the value of the root node of the current subtree if (node.value < this.value) { if (this.left == null) { this.left = node.value; } else { this.left.add(node); } } else { if (this.right == null) { this.right = node.value; } else { this.right.add(node); } } } //Middle order traversal public void infixOrder() { if (this.left != null) { this.left.infixOrder(); } //syso this.value if (this.right != null) { this.right.infixOrder(); } } } //Create binary sort tree class BinarySortTree { private Node root; //Method of adding nodes public void add(Node node) { if (root == null) { root = node; } else { root.add(node); } } //Middle order traversal public void infixOrder() { if (root != null) { root.infixOrder(); } else { // null } } //Find the node to delete public Node search(int value){ if (root == null) return null; else { return root.search(value); } } //Find parent node public Node searchParent(int value){ if (root == null) return null; else return root.searchParent(value); } public int delRightTreeMin(Node node) { //f returns the value of the smallest node of the binary sort tree with node as the root node //Delete the smallest node of the binary sort tree whose node is the root node Node target = node; while (target.left != null) { target = target.left; } //At this point, the target points to the smallest node delNode(target.value);//delete return target.value; } //Delete node public void delNode(int value) { if (root == null){ return; } else { Node targetNode = search(value); if (targetNode == null) { return; } //If only one node is found if (root.left == null && root.right == null) { root == null; return; } //Find the parent node of tgnode Node parent = searchParent(value); //If the deleted node is a leaf node if (targetNode.left == null && targetNode.right == null) { //Determine whether tg is the left child node or the right child node of the parent node if (parent.left != null && parent.left.value == value) { parent.left = null; } else if (parent.right != null && parent.right.value == value) { parent.right = null; } } else if (targetNode.left != null && targetNode.right != null) { //Delete a node with two subtrees int minval = delRightTreeMin(targetNode.right); targetNode.value = minval; //Find the smallest from the right subtree } else { //Delete the node of a subtree //Note: when there are two remaining nodes, you need to judge the existence of the root node if (targetNode.left != null){ if (parent != null) { if (parent.left.value == value) { parent.left = targetNode.left; } else { parent.right = targetNode.right; } } else root = targetNode.left; } else {//The deleted node has a right child node if (parent != null) { if (parent.left.value == value) { parent.left = targetNode.left; } else { parent.right = targetNode.right; } } else root = targetNode.right; } } } } }
10.2 deletion of binary sort tree
Consideration:
 Delete the leaf node (1. Find the node to be deleted first. targetNode 2. Find the parent node of targetNode 3. Determine whether the left child node or the right child node. parent.left= null;/ parent.right = null)
 Delete a node with only one subtree(
 123 \
 target is the left child node of parent: parent left = targetNode. left; \ parent. left = targetNode. right;)
 Delete a node with two subtrees(
 12 \
 Find the smallest node from the right subtree of targetNode,
 Save the value of the smallest node in temp with a temporary variable,
 Delete the minimum node, t
 argetNode.value = temp;
 //Or find the largest node from the left subtree)
//Find the node to delete public Node search(int value) { if (value == this.value) { return this; } else if (value < this.value) { //Left subtree recursive search if (this.left == null) { return null; } return this.left.search(value); } else { if (this.right == null) { return null; } return this.right.search(value); } } //Find the parent node of the node you want to delete public Node searchParent(int value) { if ((this.left != null && this.left.value == value)  (this.right != null && this.right.value == value)) { return this; } else { if (value < this.value && this.left != null) { return this.left.searchParent(value); } else if (value >= this.value && this.right != null) { //Avoid the same value in actual use return this.right.searchParent(value); } else { //not found return null; } } } //Other codes are in the previous section
11, Balanced binary tree (AVL)
Explain the possible problems of binary sort tree, which is also called balanced binary search tree
Case: {1, 2, 3, 4, 5, 6}, the binary tree formed is more like a single linked list, and the query is slower,
Problem analysis: all the left subtrees are empty, the insertion speed is not affected, the query speed is significantly reduced, and the advantages of bst cannot be brought into play. Solution: balance the binary tree.
Basic introduction:
 avl tree to ensure high query efficiency
 Features: the absolute value of the height difference between the left and right subtrees is no more than 1, and both the left and right subtrees are a balanced binary tree.
 Common implementation methods of balanced binary tree: red black tree, avl (algorithm), scapegoat tree, tree and extended tree
11.1 single rotation (left rotation)
Sequence 4 3 2 5 7 8,
Count the height of the left subtree and the height of the right subtree
class Node { int value; Node left; Node right; //constructor //**************************************************************** //Returns the height of the tree with the current node as the root node public int height(){ return Math.max(left == null ? 0 : left.height(), right == null ? 0 : right.height()) + 1; } public int leftHeight(){ if (left == null) return 0; return left.height(); } //Returns the height of the right subtree public int rightHeight(){ if (right == null) return 0; return right.height(); } //Left rotation method private void leftRotate() { //1. Create a new node to the value of the current root node Node new = new Node(value); new.left = left; new.right = right.left; value = right.value; right = right.right; left = new; } //********************************************************************** //Add node public void add(Node node) { //Adding nodes in the form of recursion needs to meet the requirements of binary sort tree if (node == null) { return; } //Judge the value of the incoming node and its relationship with the value of the root node of the current subtree if (node.value < this.value) { if (this.left == null) { this.left = node.value; } else { this.left.add(node); } } else { if (this.right == null) { this.right = node.value; } else { this.right.add(node); } } //************************************* //After adding a node, if (height of right subtree  height of left subtree) > 1, rotate left if (rightHeight()  leftHeight() > 1) { // if (right != null && right.rightHeight() < right.leftHeight()) { //Rotate the right subtree first //} //Simple consideration, left rotation leftRotate(); } // if (leftHeight()  rightHeight() > 1) { rightRotate(); } } //Middle order traversal public void infixOrder() { if (this.left != null) { this.left.infixOrder(); } //syso this.value if (this.right != null) { this.right.infixOrder(); } } }
11.2 right rotation
private void rightRotate(){ Node new = new Node(value); new.right = right; new.left = left.right; value = left.value; left = left.left; right = new; }
11.3 double rotation
Problem analysis:
 When the conditions for right rotation are met
 If the height of the right subtree of its left subtree is greater than the height of its left subtree
 First rotate the left node of the current node
 Then rotate the current node to the right
if(leftHeight()  rightHeight() > 1){ if (left != null && left.rightHeight() > left.leftHeigth()) { left.leftRotate(); rightRotate(); } else { rightRotate(); } return; // Must } if (rightHeight()  leftHeight() > 1) { //If the height of the left subtree of the right subtree is greater than the height of its right subtree //First rotate the right child node to the right, and then rotate the current node to the left if (right != null && right.leftHeight() > right.rightHeight()) { right.rightRotate(); leftRotate(); } else { leftRotate(); } return; }
12, Multiple lookup tree
12.1 binary tree and Btree
The operation efficiency of binary tree is high, but there are also problems
Node of full binary tree: 2^n1
The massive number of binary tree nodes causes problems: 1. During construction, i/o operations need to be carried out many times (massive data exists in the database or file). The massive number of nodes has an impact on the speed of constructing binary tree. 2.
2. The nodes are massive and the height of binary tree is very high, which reduces the operation speed.
Multitree:
Number of subtrees of nodes: degree of nodes
Maximum degree of all nodes: the degree of the tree
12.23 tree (9.29)
23 tree is a simple btree structure with the following features:
 All leaf nodes of the 23 tree are on the same layer (conditions satisfied by the b tree)
 23 tree has only 2 and 3 nodes and 2 nodes (with two nodes or no nodes)
 Meet the characteristics of sorting array and abide by the rules of binary sorting tree
 When a number is inserted to a node according to the regulations, if the above three requirements cannot be met, it needs to be removed. First remove it upward, and if the upper layer is full, remove this layer.
12.3 B tree, B + tree, b * Tree
Balanced
Btree
 Order of B tree: 23 tree = 3234 tree = 4, maximum number of child nodes of node
 Search performance: do a binary search in the complete set of keywords
B + tree
 Keywords are added to the linked list of leaf nodes (dense index)
 A non leaf node is equivalent to the index of a leaf node (sparse index)
B * Tree
13, Figure
Why are there pictures?
 The linear table is limited to the relationship between a direct precursor and a direct successor
 The tree can also have only one direct precursor (parent node)
 When we need to represent many to many relationships, we need to use graphs
Graph is a kind of data structure. Nodes can have zero or more adjacent elements, and there are edges between nodes.
 Undirected graph
 Directed graph
 Weighted graph (net)
Representation:
 Two dimensional array (adjacency matrix)
 Linked list (adjacency list)
13.1 implementation of undirected graph code
//Store vertex String using ArrayList 2 Save matrix int[][] edges private ArrayList<String> vertexList; private int[][] edges;//Storage graph corresponding adjacency matrix private int numOfEdges; public Graph(int n) { //Initialize matrix and vertexList edges = new int[n][n]; vertexList = new ArrayList<String>(n); numOfEdges = 0; } public void insertVertex(String vertex) { //Insert node vertexList.add(vertex); } //Add edge //v12 vertex subscript weight indicates weight public void insertEdge(int v1, int v2, int weight) { edges[v1][v2] = weight; edges[v2][v1] = weight; numOfEdges++; } //Common methods return the number of nodes public int getNumOfVertex(){ return vertexList.size(); } //Get the number of edges public int getNumOfEdges(){ return numOfEdges; } //Returns the data corresponding to the subscript of node i public String getValue(int i) { return vertexList.get(i); } //Returns the weight of v1 v2 public int getWeight(int v1, int v2) { return edges[v1][v2]; } //Corresponding matrix diagram
13.2 DFS
Basic steps:
 Access node, mark that the node has been accessed
 Find the first adjacent node
 Not accessed, the depth of the modified node takes precedence
//Defines the array boolean [], which records whether a node is accessed private boolean[] isVisited = new boolean[5];//Initialization is written in the constructor //Get the subscript of the first adjacent node public int getFirstNeighbor(int index) { for (int j = 0; j < vertexList.size(); j++){ if (edges[index][j] > 0) return j; } return 1; } //Obtain the next adjacent node according to the subscript of the previous adjacent node public int getNextNeighbor(int v1, int v2) { for (int j = v2 + 1; j < vertexList.size(); j++) { if (edges[v1][j] > 0) return j; } return 1; } //DFS public void dfs(boolean[] isVisited, int i) { //Access node //syso get(i)+">" //Tag access isVisited[i] = true; //Find the first adjacent node of node i int w = getFirstNeighbor(i); while (w != 1) { if (!isVisited[w]) { dfs(isVisited, w); } //If w has been accessed w = getNextNeighbor(i, w); } } main{ graph.dfs(); } //Reload dfs, public void dfs() { //Traverse all nodes and perform dfs backtracking for (int i = 0; i < getNumOfVertex(); i++){ if (!isVisited[i]) { dfs(isVisited, i); } } }
13.3 BFS
Similar to the hierarchical search process, breadth first search needs to use a queue to maintain the order of visited nodes
//bfs for a node private void bfs(boolean[] isVisited, int i) { int u; // Indicates the subscript corresponding to the header node of the queue int w; //Adjacent node w //Queue, record order LinkedList queue = new LinkedList(); //Access node //syso //Tag access isVisited[i] = true; //Node join queue queue.addLast(i); while (!queue.isEmpty()) { //Take out the subscript of the queue header node u = (Integer)queue.removeFirst(); //Get the subscript w of the first adjacent node w = getFirstNeighbor(u); while (w != 1) { if(!isVisited[w]) { //Output access //Tag access isVisited[w] = true; //Join queue queue.addLast(w); } w = getNextNeighbor(u, w);//Continue to find other adjacent node subscripts of the current layer } } } //Traverse all nodes for breadth first search public void bfs() { isVisited = new boolean[verTexList.size()]; for (int i = 0; i < getNumOfVertex(); i++) { if (!isVisited[i]) { bfs(isVisited, i); } } }
13.4 summary
14, 10 commonly used algorithms
14.1 non recursive binary search
 The binary search algorithm is only suitable for searching from the ordered sequence (numbers, letters, etc.) and sorting the sequence
 The running time is log time O(logN), and it takes up to logN times to find the target
//Ascending sequence public static int binarySearch(int[] arr, int target) { int left = 0; int right = arr.length  1; while (left <= right) { int mid = (left + right) / 2; if (arr[mid] == target) return mid; else if (arr[mid] > target) { right = mid  1;// You need to look to the left } else { left = mid + 1; } } return 1; }
14.2 divide and conquer algorithm
divide and rule
 The complex problem is divided into several identical or similar subproblems, and then the solutions of subproblems that can be solved simply are combined. This technique is the basis of many efficient algorithms, such as sorting (fast sorting, merging) and Fourier transform (fast Fourier transform)
 Solving classical problems: binary search, large integer multiplication, chessboard coverage, merge sort, quick sort, linear time selection, closest point pair problem, round robin schedule, Hanoi tower
14.2.1 divide and conquer Hanoi Tower
 If there is only one disk, a  > C
 N > = 2, as two disks, the bottom disk and the top disk.
 First put the top plate a  > B
 Lowest a  > C
 b all b  > C
// public static void hT(int num, char a, char b, char c) { if (num == 1) { //syso a  > c } else { //1. ab hT(num  1, a, c, b); //2. The bottom plate of aC //syso a > c //3. From B to c hT(num  1, b, a, c); } }
14.3 dynamic planning
Application scenario  Knapsack Problem
01 knapsack problem (one for each item at most), complete knapsack problem (without limiting the number of items, it can be changed to 01)
 Solving subproblems
 Different from divide and conquer, the subproblems obtained by decomposition are often not independent of each other. Based on the solution of the next sub stage, it is necessary to establish the solution of the next sub stage
 Dynamic programming can be advanced step by step by filling in the form to obtain the optimal solution
Thought  > formula (Law)  > code
//The ith item w[i] item weight v[i] item value v[i][j] the maximum value c backpack capacity that can be loaded into the backpack with capacity j in the first I items traversed each time /* Fill in the form  find the law  get the formula 1.v[i][0] = v[0][j] = 0 Indicates that the first row and column filled in the table are 0 2.w[i] > j, v[i][j]=v[i1][j] //When the capacity of the new product to be added is greater than the capacity of the backpack, the loading strategy of the previous cell is directly used 3.When J > = w [i], v [i] [J] = max {v [I1] [J], v [I1] [JW [i]] + v [i]} //When the newly added commodity capacity to be added is less than or equal to the capacity of the current backpack, the loading method is as follows: //v[i1][j]:Maximum loaded value of the previous cell //v[i]:Indicates the value of the current item //v[i1][jw[i]]:Maximum value of loading i1 items into the remaining space jw[i] Value of current goods + maximum value of goods in remaining space */ public static void main(String[] args) { int[] w = {1, 4, 3}; int[] val = {1500, 3000, 2000}; int m = 4; int n = val.length; //Create a 2D array int[][] v = new int[n+1][m+1]; for (int i = 0; i < v.length; i++){ v[i][0] = 0; } for (int i = 0; i < v[0].length; i++){ v[0][i] = 0; } //According to the formula obtained above, dynamic programming is processed for (int i = 1; i < v.length; i++){ //Do not process the first line for (int j = 1; j < v[0].length; j++){ // if (w[i1] > j){ v[i][j] = v[i1][j]; } else { //i starts with 1 and needs  1 v[i][j] = Math.max(v[i1][j], val[i  1]+v[i1][jw[i1]]); //Record the situation. You can't simply use the formula if () } } } }
14.4 KMP
Application scenario: string matching problem
Determine whether str1 contains str2
14.4.1 violence matching

Character matching, for i++, j++

Failed, str[i], make i=i(j1), j=0

A lot of backtracking, moving only one bit at a time, wasting a lot of time, and there are repeated matches
public static int violenceMatch(String str1, String str2) { char[] s1 = str1.toCharArray(); char[] s2 = str2.toCharArray(); int s1len = s1.length; int s2len = s2.length; int i = 0; int j = 0; while (i < s1len && j < s2len) { //Guarantee not to cross the line if (s1[i] == s2[j]) { i++; j++; } else { i = i  (j1); j = 0; } } if (j == s2len) { return i  j; } else return 1; }
14.4.2 kmp
kmp is a classical algorithm to solve whether the pattern string has appeared in the text string, and if so, the earliest position
Using the previously judged information, save the length of the longest common subsequence in the pattern string through a next array. During each backtracking, find the previously matched position through the next array, saving a lot of calculation time.
How to omit the repeated steps?
Through some search words, the partial matching table of pattern string is calculated.
The essence of partial matching: there will be repetition at the head and tail of the string, and partial matching value is the length of repetition.
main{ str1 = "sdsdsd dsddsd"; str2 = "sd"; } //kmp search algorithm public static int kmpSearch(String str1, String str2, int[] next) { for (int i = 0, j = 0; i < str1.length; i++){ //Need to process STR1 charAt(i) != str2. charAt(j) // *******kmp core********* while (j > 0 && str1.charAt(i) != str2.charAt(j)) { j = next[j  1]; } if (str1.charAt(i) == str2.charAt(j)) { j++; } if (j == str2.length()) {//eureka return i  j + 1; } } return 1; } //Gets the partial matching value table of a string (substring) public static int[] kmpNext(String dest) { //Create a next array to save some matching values int[] next = new int[dest.length()]; next[0] = 0; for (int i = 1, j = 0; i++){ //In case of inequality, we need to obtain a new j from next[j1] until we find that there is equality and exit //***********kmp core*********** while (j > 0 && dest.charAt(i) != dest.charAt(j)) { j = next[j  1]; } if (dest.charAt(i) == dest.charAt(j)) { j++; } next[i] = j; } return next; }
14.5 greedy algorithm
Application scenario  set coverage problem
Introduction:
 When solving the problem, the best or optimal choice is taken in each step, so as to hope to lead to the best or optimal algorithm
 The results obtained are not necessarily the optimal results (sometimes the optimal solution), but they are relatively close to the optimal solution
Train of thought analysis:
 Exhaustive method, list all sets. It takes a lot of time.
 Greedy algorithm:
14.6 PLIM algorithm
Road construction problems:
14.6.1 minimum spanning tree (MST)
minimum cost spanning tree
Given a weighted undirected connected graph, if a spanning tree is selected to minimize the sum of weights on all edges of the tree, the characteristics are as follows:
 N vertices, n1 edges
 Include all vertices
 n1 edges are all in the graph
 Minimum spanning tree algorithm: prim algorithm, Kruskal algorithm
14.6.2 solution of PLIM algorithm
 Find the socalled minimal connected subgraph
 The algorithm is as follows:
 Let G=(v,e) be a connected graph, T=(u,d) be a minimum spanning tree, vu be a set of vertices, and ed be a set of edges
 If the minimum spanning tree is constructed from the vertex, take the vertex u from the set V and put it into the set, and mark the vertex v with visited[u]=1
 If there are edges between vertex ui in set u and vertex vj in set vu, find the edge with the smallest weight among these edges, but it cannot form a loop. Add vertex vj to set u, and add edges ui and vj to set d, indicating vj=1
 Repeat 2 until UVs are equal and mark visited
//prim main{ } //Create minimum spanning tree, figure class MinTree{ //Create adjacency matrix of graph public void createMragph(MGraph graph, int verxs, char data[], int[][] weight) { int i, j; for (i = 0; i < verxs; i++){ graph.data[i] = data[i]; for (j = 0; j < verxs; j++) { graph.weight[i][j] = weight[i][j]; } } } //Show adjacency matrix of graph //Write prim algorithm to get the minimum spanning tree public void prim(MGraph graph, int v) { //v represents the vertex of the graph int visited[] = new int[graph.verxs]; // Mark whether the vertex has been accessed //Mark the current node as accessed visited[v] = 1; //h1 h2 records the subscripts of two vertices int h1 = 1; int h2 = 1; int minWeight = 10000;//Initialize a larger value and it will be replaced for (int k = 1; k < graph.verxs; k++) { for (int i = 0; i < graph.verxs; i++) {//Traverse visited nodes for (int j = 0; j < graph.verxs; j++) {//Traverse nodes that have not been accessed if (visited[i] == 1 && visited[j] ==0 && graph.weight[i][j] < minWeight) { //Replace minWeight minWeight = graph.weight[i][j]; h1 = i; h2 = j; } }} //Find an edge visited[h2] = 1; minWeight = 10000; } } } class MGraph{ int verx; //Represents the number of nodes in the graph char[] data;//Store node data int[][] weight;//Storage edge, adjacency matrix public MGragh(int verxs){ this.verxs = verxs; data = new char[verxs]; weight = new int[verxs][verxs]; } }
14.7 kruskar
Bus station connectivity
Firstly, a forest with only n vertices is constructed, and then edges are selected from the connected network to join the forest according to the weight from small to large, so that there is no loop in the forest until the forest becomes a tree.
A weight sorting b adds the edge with the smallest weight in turn, and does not generate a loop. By judging whether there are the same final vertices
a  sorting algorithm
b  record the end point of the vertex in the "minimum spanning tree". The end point of the vertex is "the largest vertex connected with it in the minimum spanning tree". Then each time you need to add an edge to the minimum spanning tree, judge whether the end points of the two vertices of the edge coincide. If they coincide, a loop will be formed. The two vertices of the added edge cannot all point to the same end point.
//Get the end point () of the vertex with subscript i, which is used to judge whether the end points of the two vertices are the same //The ends array records the corresponding end point of each vertex. The ends array is formed step by step in the process of traversal private int getEnd(int[] ends, int i) { while (ends[i] != 0) { i = ends[i]; } return i; } //Sort vertex classes //kruskal public void kruskal() { int index = 0; //Represents the index of the last result array int[] ends = new int[edgeNum]; //Used to save the end point of each vertex in the existing minimum spanning tree in the tree //Create a result array and save the last minimum spanning tree EData[] rets = new EData[edgeNum]; //Get the set of all edges in the graph, EData[] edges = getEdges(); //Sort according to the weight of edges (from small to large) sortEdges(edges); //Traverse the edges array. When adding edges to the spanning tree, judge whether the added edges form a loop. If not, add rets, otherwise you can't join for (int i = 0; i < edgeNum; i++) { //Gets the first vertex (starting point) to the ith edge int p1 = getPosition(edges[i].start); // int p2 = getPosition(edges[i].end); int m = getEnd(ends, p1); //Get p2 the vertex at the end of the existing minimum spanning tree int n = getEnd(ends, p2); //Does it constitute a loop if (m != n) { ends[m] = n;//Set the end point of m in ends < e, f > rets[index++] = edges[i]; //Add an edge } } }
14.8 dijestra
Shortest path problem
The main feature is to take the starting point as the center and expand to the outer layer (breadth first search idea) until it is extended to the end.
[the external link image transfer fails. The source station may have an antitheft chain mechanism. It is recommended to save the image and upload it directly (imgumlx6h5216447321619) (\ data structure and algorithm \ image.png)]
i] = data[i];
for (j = 0; j < verxs; j++) {
graph.weight[i][j] = weight[i][j];
}
}
}
//Show adjacency matrix of graph //Write prim algorithm to get the minimum spanning tree public void prim(MGraph graph, int v) { //v represents the vertex of the graph int visited[] = new int[graph.verxs]; // Mark whether the vertex has been accessed //Mark the current node as accessed visited[v] = 1; //h1 h2 records the subscripts of two vertices int h1 = 1; int h2 = 1; int minWeight = 10000;//Initialize a larger value and it will be replaced for (int k = 1; k < graph.verxs; k++) { for (int i = 0; i < graph.verxs; i++) {//Traverse visited nodes for (int j = 0; j < graph.verxs; j++) {//Traverse nodes that have not been accessed if (visited[i] == 1 && visited[j] ==0 && graph.weight[i][j] < minWeight) { //Replace minWeight minWeight = graph.weight[i][j]; h1 = i; h2 = j; } }} //Find an edge visited[h2] = 1; minWeight = 10000; } }
}
class MGraph{
int verx; // Represents the number of nodes in the graph
char[] data;// Store node data
int[][] weight;// Storage edge, adjacency matrix
public MGragh(int verxs){ this.verxs = verxs; data = new char[verxs]; weight = new int[verxs][verxs]; }
}
#### 14.7 kruskar Bus station connectivity First, construct a n Then select edges from the connected network to join the forest according to the weight from small to large, and make no loop in the forest until the forest becomes a tree. a Weight sorting b The edge with the smallest weight is added in turn, and no loop is generated, By judging whether there are the same final vertices a  Sorting algorithm b  Record the end point of the vertex in the "minimum spanning tree". The end point of the vertex is "the largest vertex connected with it in the minimum spanning tree". Then each time you need to add an edge to the minimum spanning tree, judge whether the end points of the two vertices of the edge coincide. If they coincide, a loop will be formed. The two vertices of the added edge cannot all point to the same end point. ```java //Get the end point () of the vertex with subscript i, which is used to judge whether the end points of the two vertices are the same //The ends array records the corresponding end point of each vertex. The ends array is formed step by step in the process of traversal private int getEnd(int[] ends, int i) { while (ends[i] != 0) { i = ends[i]; } return i; } //Sort vertex classes //kruskal public void kruskal() { int index = 0; //Represents the index of the last result array int[] ends = new int[edgeNum]; //Used to save the end point of each vertex in the existing minimum spanning tree in the tree //Create a result array and save the last minimum spanning tree EData[] rets = new EData[edgeNum]; //Get the set of all edges in the graph, EData[] edges = getEdges(); //Sort according to the weight of edges (from small to large) sortEdges(edges); //Traverse the edges array. When adding edges to the spanning tree, judge whether the added edges form a loop. If not, add rets, otherwise you can't join for (int i = 0; i < edgeNum; i++) { //Gets the first vertex (starting point) to the ith edge int p1 = getPosition(edges[i].start); // int p2 = getPosition(edges[i].end); int m = getEnd(ends, p1); //Get p2 the vertex at the end of the existing minimum spanning tree int n = getEnd(ends, p2); //Does it constitute a loop if (m != n) { ends[m] = n;//Set the end point of m in ends < e, f > rets[index++] = edges[i]; //Add an edge } } }
14.8 dijestra
Shortest path problem
The main feature is to take the starting point as the center and expand to the outer layer (breadth first search idea) until it is extended to the end.