Shulou(Shulou.com)06/01 Report--

This article shares with you the content of sample analysis of Java data structures and algorithms. The editor thinks it is very practical, so share it with you as a reference and follow the editor to have a look.

Chapter 1 Overview of data structures and algorithms 1.1 importance of data structures and algorithms

The algorithm is the soul of the program, and the excellent program can still maintain high-speed computing when calculating large amounts of data.

The relationship between data structure and algorithm:

Program = data structure + algorithm

Data structure is the basis of the algorithm, in other words, if you want to learn the algorithm well, you need to learn the data structure in place.

Learning syllabus of data structure and algorithm

1.2 Overview of data structures

The data structure can be simply understood as some relations between the data and the data. The data structure is divided into the data storage structure and the data logical structure.

Logical structure

Set structure: data elements belong to the same set, there is a juxtaposition relationship between them, there is no other relationship; it can be understood as a collection of learning in middle school, within a range, there are many elements, there is no relationship between elements.

Linear structure: there is an one-to-one relationship between elements; it can be understood that each student corresponds to a student number, and the student number and name are linear structures.

Tree structure: there is an one-to-many relationship between elements, which can be simply understood as family tree, generation after generation.

Graphic structure: there is a many-to-many relationship between elements, each element may correspond to multiple elements, or be corresponding to multiple elements, mesh graph

Storage structure

Sequential storage structure: continuous storage of data, which can be compared to queuing in the school canteen, one after another.

Chained storage structure: it is not stored in order. The last number only needs to tell the previous node its address. The previous node stores the address of the number behind it, so the storage address of the last number is null. This structure can be compared to the shopping mall dinner call, the above number is compared to the address, you can after the address is what, the rest of the above is the content of the node

Difference:

Sequential storage is characterized by fast query and slow insertion or deletion.

Chain storage is characterized by slow query and fast insertion or deletion.

1.3 Overview of algorithms

Different solutions to the same problem

Judge the advantages and disadvantages of the algorithm by time and space complexity.

There is no best algorithm, only the most suitable, learning algorithm is to accumulate learning ideas, master learning ideas, not to solve a problem to remember a certain algorithm; for time complexity and space complexity, now most of the development cases, we are using space for time, consuming more memory to ensure faster speed.

The complexity and stability of each sorting algorithm:

How to understand the "Big O notation"

Although it is good to make a particularly specific and detailed analysis of the algorithm, its practical value in practice is limited. For the time and space properties of the algorithm, the most important thing is its quantity level and trend, which are the main parts of analyzing the efficiency of the algorithm. However, those constant factors in the scale function of the basic operation quantity of the metrology algorithm can be ignored. For example, 3N ^ 2 and 100n ^ 2 can be considered to be of the same order of magnitude, and if the costs of the two algorithms for processing instances of the same size are these two functions, they are considered to be "about the same" in efficiency, both at n ^ 2 level.

Time complexity

The time taken by an algorithm is directly proportional to the number of sentences executed in the algorithm, which algorithm takes more time. The number of sentence execution in the algorithm is called statement frequency or time frequency, which is recorded as T (n). N is called the scale of the problem, and when n is constantly changing, the time frequency T (n) will also change. But sometimes we want to know how it changes. For this reason, we introduce the concept of time complexity.

In general, the number of repetitions of the basic operation in the algorithm is a function of the problem size n. If there is an auxiliary function f (n) such that the limit value of T (n) / f (n) is a constant not equal to zero, then f (n) is said to be a function of the same order of magnitude of T (n). Write it down as T (n) = O (f (n)), and call O (f (n)) the asymptotic time complexity of the algorithm, abbreviated as time complexity.

Sometimes, the number of repeated basic operations in the algorithm varies with the input data set of the problem, for example, in bubble sorting, the input data is orderly and disordered, and the results are different. At this point, we calculate the average.

Basic calculation rules of time complexity:

The basic operation, that is, only a constant term, is considered to have a time complexity of O (1).

Sequential structure, time complexity is calculated by addition

Loop structure, the time complexity is calculated by multiplication

Branching structure, maximum time complexity

When judging the efficiency of an algorithm, we only need to pay attention to the highest secondary term of the number of operations, while other minor and constant terms can be ignored.

In the absence of special instructions, the time complexity of the algorithms we analyze refers to the worst time complexity.

Common time complexity:

Note: log2n (logarithm with base 2) is often abbreviated to logn.

The relationship between common time complexity:

So the time consumption is from small to large: O (1)

< O(log n) < O(n) < O(nlog n) < O(n^2) < O(2^n) < O(n!) < O(n^n) 案例1： count = 0; (1) for(i = 0;i =elements || index = elements || index < 0){ throw new IndexOutOfBoundsException(); }else{ arr[index] = value; } } //根据下标查询数据 public long get(int index){ if(index >

= elements | | index

< 0){ throw new IndexOutOfBoundsException(); }else{ return arr[index]; } } //展示数据 public void display(){ System.out.print("["); for(int i = 0; i < elements;i++){ System.out.print(arr[i] + " "); } System.out.println("]"); } //二分法查找数据 public int binarySearch(long value){ //声明三个指针分别指向数组的头，尾，中间 int low = 0; int pow = elements; int middle = 0; while(true){ middle = (low + pow) / 2; //如果中指针所指的值等于带查询数 if(arr[middle] == value){ return middle; }else if(low >

Pow) {return-1 } else {if (arr > value) {/ / the number to be queried is on the left, and the right pointer changes to pow = middle-1 } else {/ / the number with query is on the right, and the left pointer changes to low = middle + 1 }

Advantages: fast query (time complexity: O (logn))

Disadvantages: slow increase and deletion (time complexity: O (n))

Chapter III Stack 3.1 Stack concept

Stack (stack), which is called stack in some places, is a container that can store data elements, access elements, and delete elements. Its characteristic is that it is only allowed to add data (English: push) and output data (English: pop) at one end of the container (called stack top indicator, English: top). Without the concept of location, the element that can be accessed or deleted at any time is guaranteed to be the last one previously stored, and a default access order is determined.

Because the stack data structure is only allowed to operate at one end, it operates according to the last-in-first-out principle.

The stack can be implemented in either a sequential list or a linked list.

3.2 Stack operation

Stack () creates a new empty stack

Push (element) adds a new element element to the top of the stack

Pop () fetches the top element of the stack

Peek () returns the top element of the stack

Is_empty () determines whether the stack is empty

Size () returns the number of elements in the stack

Implementation class:

The bottom layer of the package mystack;public class MyStack {/ / stack uses arrays to store data / / private int [] elements; int [] elements; / / tests using public MyStack () {elements = new int [0];} / / add elements public void push (int element) {/ / create a new array int [] newArr = new int [elements.length + 1] / / copy the elements from the original array to the new array for (int I = 0; I

< elements.length; i++) { newArr[i] = elements[i]; } //把添加的元素放入新数组中 newArr[elements.length] = element; //使用新数组替换旧数组 elements = newArr; } //取出栈顶元素 public int pop() { //当栈中没有元素 if (is_empty()) { throw new RuntimeException("栈空"); } //取出数组的最后一个元素 int element = elements[elements.length - 1]; //创建一个新数组 int[] newArr = new int[elements.length - 1]; //原数组中除了最后一个元素其他元素放入新数组 for (int i = 0; i < elements.length - 1; i++) { newArr[i] = elements[i]; } elements = newArr; return element; } //查看栈顶元素 public int peek() { return elements[elements.length - 1]; } //判断栈是否为空 public boolean is_empty() { return elements.length == 0; } //查看栈的元素个数 public int size() { return elements.length; }} 测试类： package mystack;public class Demo { public static void main(String[] args) { MyStack ms = new MyStack(); //添加元素 ms.push(9); ms.push(8); ms.push(7); //取出栈顶元素// System.out.println(ms.pop()); //7// System.out.println(ms.pop()); //8// System.out.println(ms.pop()); //9 //查看栈顶元素 System.out.println(ms.peek()); //7 System.out.println(ms.peek()); //7 //查看栈中元素个数 System.out.println(ms.size()); //3 }}第4章 队列4.1 队列概念 队列（Queue）是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。 队列是一种先进先出的（First In First Out）的线性表，简称FIFO。允许插入的一端为队尾，允许删除的一端为队头。队列不允许在中间部位进行操作！假设队列是q=（a1，a2，……，an），那么a1就是队头元素，而an是队尾元素。这样我们就可以删除时，总是从a1开始，而插入时，总是在队列最后。这也比较符合我们通常生活中的习惯，排在第一个的优先出列，最后来的当然排在队伍最后。 同栈一样，队列也可以用顺序表或者链表实现。 4.2 队列的操作 Queue() 创建一个空的队列 enqueue(element) 往队列中添加一个element元素 dequeue() 从队列头部删除一个元素 is_empty() 判断一个队列是否为空 size() 返回队列的大小 实现类： public class MyQueue { int[] elements; public MyQueue() { elements = new int[0]; } //入队 public void enqueue(int element) { //创建一个新的数组 int[] newArr = new int[elements.length + 1]; //把原数组中的元素复制到新数组中 for (int i = 0; i < elements.length; i++) { newArr[i] = elements[i]; } //把添加的元素放入新数组中 newArr[elements.length] = element; //使用新数组替换旧数组 elements = newArr; } //出队 public int dequeue() { if (isEmpty()) { throw new RuntimeException("队空，无数据"); } //把数组中第1个元素取出来 int element = elements[0]; //创建一个新数组 int[] newArr = new int[elements.length - 1]; //把原数组除了第一个数据，其他存入新数组 for (int i = 0; i < elements.length; i++) { newArr[i] = elements[i + 1]; } //新数组替换旧数组 elements = newArr; return element; } //判断是否队空 public boolean isEmpty() { return elements.length==0; } //获取队列长度 public int size() { return elements.length; }} 测试类： public class Demo { public static void main(String[] args) { MyQueue mq = new MyQueue(); //入队 mq.enqueue(1); mq.enqueue(2); mq.enqueue(3); //出队 System.out.println(mq.dequeue()); //1 System.out.println(mq.dequeue()); //2 System.out.println(mq.dequeue()); //3 }}第5章 链表5.1 单链表单链表概念 单链表也叫单向链表，是链表中最简单的一种形式，它的每个节点包含两个域，一个信息域（元素域）和一个链接域。这个链接指向链表中的下一个节点，而最后一个节点的链接域则指向一个空值。 表元素域data用来存放具体的数据。 链接域next用来存放下一个节点的位置 单链表操作 is_empty() 链表是否为空 length() 链表长度 travel() 遍历整个链表 add(item) 链表头部添加元素 append(item) 链表尾部添加元素 insert(pos, item) 指定位置添加元素 remove(item) 删除节点 search(item) 查找节点是否存在 实现类： //一个节点public class Node { //节点内容 int data; //下一个节点 Node next; public Node(int data) { this.data = data; } //为节点追加节点 public Node append(Node node) { //当前节点 Node currentNode = this; //循环向后找 while (true) { //取出下一个节点 Node nextNode = currentNode.next(); //如果下一个节点为null，当前节点已经是最后一个节点 if (nextNode == null) { break; } //赋给当前节点，无线向后找 currentNode = nextNode; } //把需要追加的节点，追加为找到的当前节点（最后一个节点）的下一个节点 currentNode.next = node; return this; } //显示所有节点信息 public void show() { Node currentNode = this; while (true) { System.out.print(currentNode.data + " "); //取出下一个节点 currentNode = currentNode.next; //如果是最后一个节点 if (currentNode == null) { break; } } System.out.println(); } //插入一个节点作为当前节点的下一个节点 public void after(Node node) { //取出下一个节点，作为下下一个节点 Node nextNext = next; //把新节点作为当前节点的下一个节点 this.next = node; //把下下一个节点设置为新节点的下一个节点 node.next = nextNext; } //删除下一个节点 public void removeNode() { //取出下下一个节点 Node newNext = next.next; //把下下一个节点设置为当前节点的下一个节点 this.next = newNext; } //获取下一个节点 public Node next() { return this.next; } //获取节点中的数据 public int getData() { return this.data; } //判断节点是否为最后一个节点 public boolean isLast() { return next == null; }} 测试类： public class Demo { public static void main(String[] args) { //创建节点 Node n1 = new Node(1); Node n2 = new Node(2); Node n3 = new Node(3); //追加节点 n1.append(n2).append(n3); //取出下一个节点数据 System.out.println(n1.next().next().getData()); //3 //判断节点是否为最后一个节点 System.out.println(n1.isLast()); //false System.out.println(n1.next().next().isLast()); //true //显示所有节点信息 n1.show(); //1 2 3 //删除一个节点// n1.next.removeNode();// n1.show(); //1 2 //插入一个新节点 n1.next.after(new Node(0)); n1.show(); //1 2 0 3 }}5.2 循环链表循环链表概念 单链表的一个变形是单向循环链表，链表中最后一个节点的 next 域不再为 None，而是指向链表的头节点。 循环链表操作 实现类： //表示一个节点public class LoopNode { //节点内容 int data; //下一个节点 LoopNode next = this; //与单链表的区别，追加了一个this，当只有一个节点时指向自己 public LoopNode(int data) { this.data = data; } //插入一个节点 public void after(LoopNode node) { LoopNode afterNode = this.next; this.next = node; node.next = afterNode; } //删除一个节点 public void removeNext() { LoopNode newNode = this.next.next; this.next = newNode; } //获取下一个节点 public LoopNode next() { return this.next; } //获取节点中的数据 public int getData() { return this.data; }} 测试类： public class Demo { public static void main(String[] args) { //创建节点 LoopNode n1 = new LoopNode(1); LoopNode n2 = new LoopNode(2); LoopNode n3 = new LoopNode(3); LoopNode n4 = new LoopNode(4); //增加节点 n1.after(n2); n2.after(n3); n3.after(n4); System.out.println(n1.next().getData()); //2 System.out.println(n2.next().getData()); //3 System.out.println(n3.next().getData()); //4 System.out.println(n4.next().getData()); //1 }}5.3 双向循环链表双向循环链表概念 在双向链表中有两个指针域，一个是指向前驱结点的prev，一个是指向后继结点的next指针 双向循环链表操作 实现类： public class DoubleNode { //上一个节点 DoubleNode pre = this; //下一个节点 DoubleNode next = this; //节点数据 int data; public DoubleNode(int data) { this.data = data; } //增加节点 public void after(DoubleNode node) { //原来的下一个节点 DoubleNode nextNext = next; //新节点作为当前节点的下一个节点 this.next = node; //当前节点作为新节点的前一个节点 node.pre = this; //原来的下一个节点作为新节点的下一个节点 node.next = nextNext; //原来的下一个节点的上一个节点为新节点 nextNext.pre = node; } //获取下一个节点 public DoubleNode getNext() { return this.next; } //获取上一个节点 public DoubleNode getPre() { return this.pre; } //获取数据 public int getData() { return this.data; }} 测试类： public class Demo { public static void main(String[] args) { //创建节点 DoubleNode n1 = new DoubleNode(1); DoubleNode n2 = new DoubleNode(2); DoubleNode n3 = new DoubleNode(3); //追加节点 n1.after(n2); n2.after(n3); //查看上一个，自己，下一个节点内容 System.out.println(n2.getPre().getData()); //1 System.out.println(n2.getData()); //2 System.out.println(n2.getNext().getData()); //3 System.out.println(n1.getPre().getData()); //3 System.out.println(n3.getNext().getData()); //1 }}第6章 树结构基础6.1 为什么要使用树结构 线性结构中不论是数组还是链表，他们都存在着诟病；比如查找某个数必须从头开始查，消耗较多的时间。使用树结构，在插入和查找的性能上相对都会比线性结构要好 6.2 树结构基本概念 示意图 1、根节点：最顶上的唯一的一个；如：A 2、双亲节点：子节点的父节点就叫做双亲节点；如A是B、C、D的双亲节点，B是E、F的双亲节点 3、子节点：双亲节点所产生的节点就是子节点 4、路径：从根节点到目标节点所走的路程叫做路径；如A要访问F，路径为A-B-F 5、节点的度：有多少个子节点就有多少的度（最下面的度一定为0，所以是叶子节点） 6、节点的权：在节点中所存的数字 7、叶子节点：没有子节点的节点，就是没有下一代的节点；如：E、F、C、G 8、子树：在整棵树中将一部分看成也是一棵树，即使只有一个节点也是一棵树，不过这个树是在整个大树职中的，包含的关系 9、层：就是族谱中有多少代的人；如：A是1，B、C、D是2，E、F、G是3 10、树的高度：树的最大的层数：就是层数中的最大值 11、森林：多个树组成的集合 6.3 树的种类 无序树：树中任意节点的子节点之间没有顺序关系，这种树称为无序树，也称为自由树； 有序树：树中任意节点的子节点之间有顺序关系，这种树称为有序树； 二叉树：每个节点最多含有两个子树的树称为二叉树； 完全二叉树：对于一颗二叉树，假设其深度为d(d>

1). Except for layer d, the number of nodes in all layers has reached the maximum, and all nodes in layer d are closely arranged continuously from left to right. Such a binary tree is called a complete binary tree, in which a full binary tree is defined as a complete binary tree in which all leaf nodes are at the bottom.

Balanced binary tree (AVL tree): if and only if the height difference of two subtrees of any node is not greater than 1

Sort binary tree (binary search tree (English: Binary Search Tree), also known as binary search tree, ordered binary tree)

Huffman tree (for information coding): the binary tree with the shortest weighted path is called Huffman tree or optimal binary tree.

B-tree: a self-balanced binary search tree that optimizes read and write operations, which keeps the data in order and has more than two subtrees.

Storage and representation of 6.4 Tree

Sequential storage: the data structure is stored in a fixed array, but it has a certain advantage in traversal speed, but it is a non-mainstream binary tree because of its large space. Binary trees are usually stored in chains.

Chain storage:

Because it is impossible to grasp the number of nodes, the storage representation of the common tree is converted into a binary tree for processing, and the maximum number of sub-nodes is 2.

6.5 Application scenarios of some common trees

1. Xml,html, etc., so when writing parsers for these things, trees are inevitably used.

2. The routing protocol uses a tree algorithm

3. Mysql database index

4. Directory structure of the file system

5. So many classic AI algorithms are actually tree search, and decision tree in machine learning is also a tree structure.

Chapter 7 the definition of binary tree Daquan 7.1 binary tree

If the number of child nodes of any node does not exceed 2, that is the binary tree; the child nodes of the binary tree are divided into the left node and the right node, which cannot be reversed.

7.2 Properties (characteristics) of binary trees

Property 1: there are at most 2 ^ (iMel 1) nodes (I > 0) on the I layer of the binary tree.

Property 2: a binary tree with depth k has at most 2 ^ k-1 nodes (k > 0)

Property 3: for any binary tree, if the number of leaf nodes is N0 and the total number of nodes with degree 2 is N2, then N0=N2+1

Property 4: the depth of a complete binary tree with n nodes must be log2 (n = 1).

Property 5: for a complete binary tree, if it is numbered from top to bottom and from left to right, the node numbered I must be 2i on the left and 2i on the right, and the number of its parents must be iUnix 2 (except iTree 1).

7.3 full binary tree and complete binary tree

Full binary tree: all leaf nodes are concentrated on the bottom layer of the binary tree, and the total number of nodes is: 2 ^ n-1 (n is the number of layers / height)

Complete binary tree: all leaf nodes are on the last or penultimate layer, and the last layer is continuous on the left and the penultimate layer on the right (full binary tree is also a complete binary tree) (from top to bottom, you can count it next to each other from left to right.

7.4 binary tree with chained storage

Create a binary tree: first of all, you need a class of a tree, and you need another class to store the node and set the node; put the node into the tree and form a binary tree; (weights are needed in the node, left subtree, right subtree, and their values can be set).

Traversal of the tree:

Preorder traversal: root node, left node, right node (if the node has a subtree, traverse the subtree from left to right first, and then traverse the sibling node)

The result of preorder traversal is: A B D H I E J C F K G

Middle order traversal: left node, root node, right node (middle order traversal can be seen as, each node of the binary tree is projected vertically (it can be understood that each node falls vertically to the ground from the leftmost), and then counts from left to right.

The traversal result in the is: H D I B E J A F K C G

Traversal after order: left node, right node, root node

Traversal result after sequence: H I D J E B K F G C A

Hierarchical traversal: from top to bottom, from left to right

Hierarchical traversal result: A B C D E F G H I J K

Find nodes: first traverse the tree, and then find out the number you are looking for; because there are three sorting methods, the search nodes are also divided into first-order search, middle-order search, and post-order search.

Delete node: due to chained storage, the number to be deleted cannot be found directly, so you need to find his parent node, and then set the number to null;, so you need a variable to point to the parent node. After finding the number, you will disconnect.

Code implementation:

Tree class

Public class BinaryTree {TreeNode root; / / set root node public void setRoot (TreeNode root) {this.root = root;} / / get root node public TreeNode getRoot () {return root;} / / preorder traversal public void frontShow () {if (root! = null) {root.frontShow () }} / / traversing public void middleShow () {if (root! = null) {root.middleShow ();}} / / traversing public void afterShow () {if (root! = null) {root.afterShow () }} / / first find public TreeNode frontSearch (int I) {return root.frontSearch (I);} / delete a subtree public void delete (int I) {if (root.value = = I) {root = null;} else {root.delete (I);}

Node class

Right of public class TreeNode {/ / Node int value; / / left son TreeNode leftNode; / / right son TreeNode rightNode; public TreeNode (int value) {this.value = value;} / / set left son public void setLeftNode (TreeNode leftNode) {this.leftNode = leftNode;} / / set right son public void setRightNode (TreeNode rightNode) {this.rightNode = rightNode } / / preorder traversal public void frontShow () {/ / first traverse the value of the current node System.out.print (value + "); / / left node if (leftNode! = null) {leftNode.frontShow (); / / Recursive thought} / / right node if (rightNode! = null) {rightNode.frontShow () }} / / traverse public void middleShow () {/ / left node if (leftNode! = null) {leftNode.middleShow (); / / Recursive thought} / / traverse the value System.out.print (value + "") of the current node first / / right node if (rightNode! = null) {rightNode.middleShow ();}} / subsequent traversal of public void afterShow () {/ / left node if (leftNode! = null) {leftNode.afterShow () / / Recursive thought} / / right node if (rightNode! = null) {rightNode.afterShow ();} / / first traverse the value of the current node System.out.print (value + "");} / / preorder search public TreeNode frontSearch (int I) {TreeNode target = null / / compare the value of the current node if (this.value = = I) {return this / / the current node is not the node to be found} else {/ / find the left son if (leftNode! = null) {/ / if t is assigned to target, can not find target or null target = leftNode.frontSearch (I) } / / if target is not empty, if (target! = null) {return target;} / / if the left son does not find it, look for the right son if (rightNode! = null) {target = rightNode.frontSearch (I) }} return target;} / / Delete a subtree public void delete (int I) {TreeNode parent = this; / / judge the left son if (parent.leftNode! = null & & parent.leftNode.value = = I) {parent.leftNode = null; return } / / judge the right son if (parent.rightNode! = null & & parent.rightNode.value = = I) {parent.rightNode = null; return;} / / if neither, recursively check and delete the left son parent = leftNode; if (parent! = null) {parent.delete (I) } / / Recursive check and delete right son parent = rightNode; if (parent! = null) {parent.delete (I);}

Test class

Public class Demo {public static void main (String [] args) {/ / create a tree BinaryTree binaryTree = new BinaryTree (); / / create a root node TreeNode root = new TreeNode (1); / / assign the root node to the tree binaryTree.setRoot (root); / / create left, right node TreeNode rootLeft = new TreeNode (2); TreeNode rootRight = new TreeNode (3) / / set the newly created node as the child node of the root node root.setLeftNode (rootLeft); root.setRightNode (rootRight); / / create two child nodes rootLeft.setLeftNode (new TreeNode (4)) for the left node of the second layer; rootLeft.setRightNode (new TreeNode (5)); / / create two child nodes rootRight.setLeftNode (new TreeNode (6)) for the right node of the second layer RootRight.setRightNode (new TreeNode (7)); / / preorder traversal binaryTree.frontShow (); / 1 2 4 5 3 6 7 System.out.println (); / / medium order traversal binaryTree.middleShow (); / 4 25 1 6 37 System.out.println (); / / post order traversal binaryTree.afterShow () / / 4 5 2 6 7 3 1 System.out.println (); / / preorder lookup TreeNode result = binaryTree.frontSearch (5); System.out.println (result); / / binarytree.TreeNode@1b6d3586 / / delete a subtree binaryTree.delete (2); binaryTree.frontShow () / / 1 3 6 7, 2 and his child nodes were deleted}} 7.5 sequentially stored binary tree

Summary: sequential storage is implemented in the form of an array; because incomplete binary trees will cause gaps in the array, some positions cannot be filled with numbers, so sequential storage binary trees usually only consider complete binary trees.

Principle: sequentially stored in the array is stored down at one time according to the first layer and the second layer, and the traversal methods also include pre-order traversal, mid-order traversal, and subsequent traversal.

Nature:

The left child node of the nth element is: 2*n+1

The right child node of the nth element is: 2*n+2

The parent node of the nth element is: (nmur1) / 2

Code implementation:

Tree class

Public class ArrayBinaryTree {int [] data; public ArrayBinaryTree (int [] data) {this.data = data;} / / overload the preorder traversal method. Instead of passing parameters every time, it is guaranteed that public void frontShow () {frontShow (0);} / preorder traversal public void frontShow (int index) {if (data = = null | | data.length = = 0) {return } / / first traverse the content System.out.print (data [index] + "") of the current node; / / process the left subtree: 2*index+1 if (2*index+1)

< data.length) { frontShow(2 * index + 1); } //处理右子树：2*index+2 if (2 * index + 2 < data.length) { frontShow(2 * index + 2); } }} 测试类 public class Demo { public static void main(String[] args) { int[] data = {1,2,3,4,5,6,7}; ArrayBinaryTree tree = new ArrayBinaryTree(data); //先序遍历 tree.frontShow(); //1 2 4 5 3 6 7 }}7.6 线索二叉树(Threaded BinaryTree) 为什么使用线索二叉树？ 当用二叉链表作为二叉树的存储结构时，可以很方便的找到某个结点的左右孩子；但一般情况下，无法直接找到该结点在某种遍历序列中的前驱和后继结点 原理：n个结点的二叉链表中含有n+1(2n-(n-1)=n+1个空指针域。利用二叉链表中的空指针域，存放指向结点在某种遍历次序下的前驱和后继结点的指针。 例如：某个结点的左孩子为空，则将空的左孩子指针域改为指向其前驱；如果某个结点的右孩子为空，则将空的右孩子指针域改为指向其后继（这种附加的指针称为"线索"） 代码实现： 树类 public class ThreadedBinaryTree { ThreadedNode root; //用于临时存储前驱节点 ThreadedNode pre = null; //设置根节点 public void setRoot(ThreadedNode root) { this.root = root; } //中序线索化二叉树 public void threadNodes() { threadNodes(root); } public void threadNodes(ThreadedNode node) { //当前节点如果为null，直接返回 if (node == null) { return; } //处理左子树 threadNodes(node.leftNode); //处理前驱节点 if (node.leftNode == null) { //让当前节点的左指针指向前驱节点 node.leftNode = pre; //改变当前节点左指针类型 node.leftType = 1; } //处理前驱的右指针，如果前驱节点的右指针是null（没有右子树） if (pre != null && pre.rightNode == null) { //让前驱节点的右指针指向当前节点 pre.rightNode = node; //改变前驱节点的右指针类型 pre.rightType = 1; } //每处理一个节点，当前节点是下一个节点的前驱节点 pre = node; //处理右子树 threadNodes(node.rightNode); } //遍历线索二叉树 public void threadIterate() { //用于临时存储当前遍历节点 ThreadedNode node = root; while (node != null) { //循环找到最开始的节点 while (node.leftType == 0) { node = node.leftNode; } //打印当前节点的值 System.out.print(node.value + " "); //如果当前节点的右指针指向的是后继节点，可能后继节点还有后继节点 while (node.rightType == 1) { node = node.rightNode; System.out.print(node.value + " "); } //替换遍历的节点 node = node.rightNode; } } //获取根节点 public ThreadedNode getRoot() { return root; } //先序遍历 public void frontShow() { if (root != null) { root.frontShow(); } } //中序遍历 public void middleShow() { if (root != null) { root.middleShow(); } } //后序遍历 public void afterShow() { if (root != null) { root.afterShow(); } } //先序查找 public ThreadedNode frontSearch(int i) { return root.frontSearch(i); } //删除一个子树 public void delete(int i) { if (root.value == i) { root = null; } else { root.delete(i); } }} 节点类 public class ThreadedNode { //节点的权 int value; //左儿子 ThreadedNode leftNode; //右儿子 ThreadedNode rightNode; //标识指针类型,1表示指向上一个节点，0 int leftType; int rightType; public ThreadedNode(int value) { this.value = value; } //设置左儿子 public void setLeftNode(ThreadedNode leftNode) { this.leftNode = leftNode; } //设置右儿子 public void setRightNode(ThreadedNode rightNode) { this.rightNode = rightNode; } //先序遍历 public void frontShow() { //先遍历当前节点的值 System.out.print(value + " "); //左节点 if (leftNode != null) { leftNode.frontShow(); //递归思想 } //右节点 if (rightNode != null) { rightNode.frontShow(); } } //中序遍历 public void middleShow() { //左节点 if (leftNode != null) { leftNode.middleShow(); //递归思想 } //先遍历当前节点的值 System.out.print(value + " "); //右节点 if (rightNode != null) { rightNode.middleShow(); } } //后续遍历 public void afterShow() { //左节点 if (leftNode != null) { leftNode.afterShow(); //递归思想 } //右节点 if (rightNode != null) { rightNode.afterShow(); } //先遍历当前节点的值 System.out.print(value + " "); } //先序查找 public ThreadedNode frontSearch(int i) { ThreadedNode target = null; //对比当前节点的值 if (this.value == i) { return this; //当前节点不是要查找的节点 } else { //查找左儿子 if (leftNode != null) { //查找的话t赋值给target，查不到target还是null target = leftNode.frontSearch(i); } //如果target不为空，说明在左儿子中已经找到 if (target != null) { return target; } //如果左儿子没有查到，再查找右儿子 if (rightNode != null) { target = rightNode.frontSearch(i); } } return target; } //删除一个子树 public void delete(int i) { ThreadedNode parent = this; //判断左儿子 if (parent.leftNode != null && parent.leftNode.value == i) { parent.leftNode = null; return; } //判断右儿子 if (parent.rightNode != null && parent.rightNode.value == i) { parent.rightNode = null; return; } //如果都不是，递归检查并删除左儿子 parent = leftNode; if (parent != null) { parent.delete(i); } //递归检查并删除右儿子 parent = rightNode; if (parent != null) { parent.delete(i); } }} 测试类 public class Demo { public static void main(String[] args) { //创建一棵树 ThreadedBinaryTree binaryTree = new ThreadedBinaryTree(); //创建一个根节点 ThreadedNode root = new ThreadedNode(1); //把根节点赋给树 binaryTree.setRoot(root); //创建左,右节点 ThreadedNode rootLeft = new ThreadedNode(2); ThreadedNode rootRight = new ThreadedNode(3); //把新建的节点设置为根节点的子节点 root.setLeftNode(rootLeft); root.setRightNode(rootRight); //为第二层的左节点创建两个子节点 rootLeft.setLeftNode(new ThreadedNode(4)); ThreadedNode fiveNode = new ThreadedNode(5); rootLeft.setRightNode(fiveNode); //为第二层的右节点创建两个子节点 rootRight.setLeftNode(new ThreadedNode(6)); rootRight.setRightNode(new ThreadedNode(7)); //中序遍历 binaryTree.middleShow(); //4 2 5 1 6 3 7 System.out.println(); //中序线索化二叉树 binaryTree.threadNodes();// //获取5的后继节点// ThreadedNode afterFive = fiveNode.rightNode;// System.out.println(afterFive.value); //1 binaryTree.threadIterate(); //4 2 5 1 6 3 7 }}7.7 二叉排序树（Binary Sort Tree） 无序序列： 二叉排序树图解： 概述：二叉排序树（Binary Sort Tree）也叫二叉查找树或者是一颗空树，对于二叉树中的任何一个非叶子节点，要求左子节点比当前节点值小，右子节点比当前节点值大 特点： 查找性能与插入删除性能都适中还不错 中序遍历的结果刚好是从大到小 创建二叉排序树原理：其实就是不断地插入节点，然后进行比较。 删除节点 删除叶子节点，只需要找到父节点，将父节点与他的连接断开即可 删除有一个子节点的就需要将他的子节点换到他现在的位置 删除有两个子节点的节点，需要使用他的前驱节点或者后继节点进行替换，就是左子树最右下方的数（最大的那个）或右子树最左边的树（最小的数）；即离节点值最接近的值；（还要注解要去判断这个值有没有右节点，有就要将右节点移上来） 代码实现： 树类 public class BinarySortTree { Node root; //添加节点 public void add(Node node) { //如果是一颗空树 if (root == null) { root = node; } else { root.add(node); } } //中序遍历 public void middleShow() { if (root != null) { root.middleShow(root); } } //查找节点 public Node search(int value) { if (root == null) { return null; } return root.search(value); } //查找父节点 public Node searchParent(int value) { if (root == null) { return null; } return root.searchParent(value); } //删除节点 public void delete(int value) { if (root == null) { return; } else { //找到这个节点 Node target = search(value); //如果没有这个节点 if (target == null) { return; } //找到他的父节点 Node parent = searchParent(value); //要删除的节点是叶子节点 if (target.left == null && target.left == null) { //要删除的节点是父节点的左子节点 if (parent.left.value == value) { parent.left = null; } //要删除的节点是父节点的右子节点 else { parent.right = null; } } //要删除的节点有两个子节点的情况 else if (target.left != null && target.right != null) { //删除右子树中值最小的节点，并且获取到值 int min = deletMin(target.right); //替换目标节点中的值 target.value = min; } //要删除的节点有一个左子节点或右子节点 else { //有左子节点 if (target.left != null) { //要删除的节点是父节点的左子节点 if (parent.left.value == value) { parent.left = target.left; } //要删除的节点是父节点的右子节点 else { parent.right = target.left; } } //有右子节点 else { //要删除的节点是父节点的左子节点 if (parent.left.value == value) { parent.left = target.right; } //要删除的节点是父节点的右子节点 else { parent.right = target.right; } } } } } //删除一棵树中最小的节点 private int deletMin(Node node) { Node target = node; //递归向左找最小值 while (target.left != null) { target = target.left; } //删除最小的节点 delete(target.value); return target.value; }} 节点类 public class Node { int value; Node left; Node right; public Node(int value) { this.value = value; } //向子树中添加节点 public void add(Node node) { if (node == null) { return; } /*判断传入的节点的值比当前紫薯的根节点的值大还是小*/ //添加的节点比当前节点更小(传给左节点） if (node.value < this.value) { //如果左节点为空 if (this.left == null) { this.left = node; } //如果不为空 else { this.left.add(node); } } //添加的节点比当前节点更大(传给右节点） else { if (this.right == null) { this.right = node; } else { this.right.add(node); } } } //中序遍历二叉排序树，结果刚好是从小到大 public void middleShow(Node node) { if (node == null) { return; } middleShow(node.left); System.out.print(node.value + " "); middleShow(node.right); } //查找节点 public Node search(int value) { if (this.value == value) { return this; } else if (value < this.value) { if (left == null) { return null; } return left.search(value); } else { if (right == null) { return null; } return right.search(value); } } //查找父节点 public Node searchParent(int value) { if ((this.left != null && this.left.value == value) || (this.right != null && this.right.value == value)) { return this; } else { if (this.value >

Value & & this.left! = null) {return this.left.searchParent (value);} else if (this.value)

< value && this.right != null) { return this.right.searchParent(value); } return null; } }} 测试类 public class Demo { public static void main(String[] args) { int[] arr = {8, 3, 10, 1, 6, 14, 4, 7, 13}; //创建一颗二叉排序树 BinarySortTree bst = new BinarySortTree(); //循环添加/* for(int i=0;i< arr.length;i++) { bst.add(new Node(arr[i])); }*/ for (int i : arr) { bst.add(new Node(i)); } //中序遍历 bst.middleShow(); //1 3 4 6 7 8 10 13 14 System.out.println(); //查找节点 Node node = bst.search(10); System.out.println(node.value);//10 Node node2 = bst.search(20); System.out.println(node2); //null //查找父节点 Node node3 = bst.searchParent(1); Node node4 = bst.searchParent(14); System.out.println(node3.value); //3 System.out.println(node4.value); //10 //删除叶子节点// bst.delete(13);// bst.middleShow(); //1 3 4 6 7 8 10 14// System.out.println();// //删除只有一个子节点的节点// bst.delete(10);// bst.middleShow(); //1 3 4 6 7 8 ；10和14都没了 //删除有两个子节点的节点 bst.delete(3); bst.middleShow(); //1 4 6 7 8 10 13 14 }}7.8 平衡二叉树（ Balanced Binary Tree）为什么使用平衡二叉树？ 平衡二叉树（Balanced Binary Tree）又被称为AVL树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。这个方案很好的解决了二叉查找树退化成链表的问题，把插入，查找，删除的时间复杂度最好情况和最坏情况都维持在O(logN)。但是频繁旋转会使插入和删除牺牲掉O(logN)左右的时间，不过相对二叉查找树来说，时间上稳定了很多。 二叉排序树插入 {1,2,3,4,5,6} 这种数据结果如下图所示： 平衡二叉树插入 {1,2,3,4,5,6} 这种数据结果如下图所示： 如何判断平衡二叉树？ 1、是二叉排序树 2、任何一个节点的左子树或者右子树都是平衡二叉树（左右高度差小于等于 1） （1）下图不是平衡二叉树，因为它不是二叉排序树违反第 1 条件 （2）下图不是平衡二叉树，因为有节点子树高度差大于 1 违法第 2 条件（5的左子树为0，右子树为2） （3）下图是平衡二叉树，因为符合 1、2 条件 相关概念 平衡因子 BF 定义：左子树和右子树高度差 计算：左子树高度 - 右子树高度的值 别名：简称 BF（Balance Factor） 一般来说 BF 的绝对值大于 1，,平衡树二叉树就失衡，需要旋转纠正 最小不平衡子树 距离插入节点最近的，并且 BF 的绝对值大于 1 的节点为根节点的子树。 旋转纠正只需要纠正最小不平衡子树即可 例子如下图所示： 旋转方式 2 种旋转方式: 左旋 : 旧根节点为新根节点的左子树 新根节点的左子树（如果存在）为旧根节点的右子树 右旋： 旧根节点为新根节点的右子树 新根节点的右子树（如果存在）为旧根节点的左子树 4 种旋转纠正类型： 左左型：插入左孩子的左子树，右旋 右右型：插入右孩子的右子树，左旋 左右型：插入左孩子的右子树，先左旋，再右旋 右左型：插入右孩子的左子树，先右旋，再左旋 左左型： 第三个节点（1）插入的时候，BF(3) = 2，BF(2) = 1，右旋，根节点顺时针旋转 右右型： 第三个节点（3）插入的时候，BF(1)=-2 BF(2)=-1，RR 型失衡，左旋，根节点逆时针旋转 左右型： 第三个节点（3）插入的 时候，BF(3)=2 BF(1)=-1 LR 型失衡，先 左旋 再 右旋 右左型： 第三个节点（1）插入的 时候，BF(1)=-2 BF(3)=1 RL 型失衡，先 右旋 再 左旋 实例 （1）、依次插入 3、2、1 插入第三个点 1 的时候 BF(3)=2 BF(2)=1，LL 型失衡，对最小不平衡树 {3,2,1}进行 右旋 旧根节点（节点 3）为新根节点（节点 2）的右子树 新根节点（节点 2）的右子树（这里没有右子树）为旧根节点的左子树 （2）依次插入 4 ，5 插入 5 点的时候 BF(3) = -2 BF(4)=-1，RR 型失衡，对最小不平衡树 {3,4,5} 进行左旋 旧根节点（节点 3）为新根节点（节点 4）的左子树 新根节点（节点 4）的左子树（这里没有左子树）为旧根节点的右子树 （3）插入 4 ，5 插入 5 点的时候 BF(2)=-2 BF(4)=-1 ，RR 型失衡 对最小不平衡树{1,2,4}进行左旋 旧根节点（节点 2）为新根节点（节点 4）的左子树 新根节点（节点 4）的 左子树（节点 3）为旧根节点的右子树 （4）插入 7 节点的时候 BF(5)=-2, BF(6)=-1 ，RR 型失衡，对最小不平衡树 进行左旋 旧根节点（节点 5）为新根节点（节点 6）的左子树 新根节点的左子树（这里没有）为旧根节点的右子树 （5）依次插入 10 ，9 。插入 9 点的时候 BF(10) = 1，BF(7) = -2，RL 型失衡，对先右旋再左旋，右子树先右旋 旧根节点（节点 10）为新根节点（节点 9）的右子树 新根节点（节点 9）的右子树（这里没有右子树）为旧根节点的左子树 最小不平衡子树再左旋： 旧根节点（节点 7）为新根节点（节点 9）的左子树 新根节点（节点 9）的左子树（这里没有左子树）为旧根节点的右子树 代码实现 节点类 public class Node { int value; Node left; Node right; public Node(int value) { this.value = value; } //获取当前节点高度 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(); } //获取右子树高度 public int rightHeight() { if (right == null) { return 0; } return right.height(); } //向子树中添加节点 public void add(Node node) { if (node == null) { return; } /*判断传入的节点的值比当前紫薯的根节点的值大还是小*/ //添加的节点比当前节点更小(传给左节点） if (node.value < this.value) { //如果左节点为空 if (this.left == null) { this.left = node; } //如果不为空 else { this.left.add(node); } } //添加的节点比当前节点更大(传给右节点） else { if (this.right == null) { this.right = node; } else { this.right.add(node); } } //查询是否平衡 //右旋转 if (leftHeight() - rightHeight() >

= 2) {/ / A pair of rotation, if (left! = null & & left.leftHeight ()) when the height on the left side of the subtree is less than the height on the right side of the left subtree.

< left.rightHeight()) { //左子树先进行左旋转 left.leftRotate(); //整体进行右旋转 rightRotate(); } //单旋转 else { rightRotate(); } } //左旋转 if (leftHeight() - rightHeight() value && this.left != null) { return this.left.searchParent(value); } else if (this.value < value && this.right != null) { return this.right.searchParent(value); } return null; } }} 测试类 public class Demo { public static void main(String[] args) { int[] arr = {1,2,3,4,5,6}; //创建一颗二叉排序树 BinarySortTree bst = new BinarySortTree(); //循环添加 for (int i : arr) { bst.add(new Node(i)); } //查看高度 System.out.println(bst.root.height()); //3 //查看节点值 System.out.println(bst.root.value); //根节点为4 System.out.println(bst.root.left.value); //左子节点为2 System.out.println(bst.root.right.value); //右子节点为5 }}第8章 赫夫曼树8.1 赫夫曼树概述 HuffmanTree因为翻译不同所以有其他的名字：赫夫曼树、霍夫曼树、哈夫曼树 赫夫曼树又称最优二叉树，是一种带权路径长度最短的二叉树。所谓树的带权路径长度，就是树中所有的叶结点的权值乘上其到根结点的路径长度（若根结点为0层，叶结点到根结点的路径长度为叶结点的层数）。树的路径长度是从树根到每一结点的路径长度之和，记为WPL=（W1L1+W2L2+W3L3+…+WnLn），N个权值Wi（i=1,2,…n）构成一棵有N个叶结点的二叉树，相应的叶结点的路径长度为Li（i=1,2,…n）。可以证明赫夫曼树的WPL是最小的。 8.2 赫夫曼树定义 路径： 路径是指从一个节点到另一个节点的分支序列。 路径长度： 指从一个节点到另一个结点所经过的分支数目。 如下图：从根节点到a的分支数目为2 树的路径长度： 树中所有结点的路径长度之和为树的路径长度PL。 如下图：PL为10 节点的权： 给树的每个结点赋予一个具有某种实际意义的实数，我们称该实数为这个结点的权。如下图：7、5、2、4 带权路径长度： 从树根到某一结点的路径长度与该节点的权的乘积，叫做该结点的带权路径长度。如下图：A的带权路径长度为2*7=14 树的带权路径长度（WPL）： 树的带权路径长度为树中所有叶子节点的带权路径长度之和 最优二叉树：权值最大的节点离跟节点越近的二叉树，所得WPL值最小，就是最优二叉树。如下图：（b） （a）WPL=9*2+4*2+5*2+2*2=40 （b）WPL=9*1+5*2+4*3+2*3=37 （c） WPL=4*1+2*2+5*3+9*3=50 8.3 构造赫夫曼树步骤 对于数组{5,29,7,8,14,23,3,11}，我们把它构造成赫夫曼树 第一步：使用数组中所有元素创建若干个二叉树，这些值作为节点的权值（只有一个节点）。 第二步：将这些节点按照权值的大小进行排序。 第三步：取出权值最小的两个节点，并创建一个新的节点作为这两个节点的父节点，这个父节点的权值为两个子节点的权值之和。将这两个节点分别赋给父节点的左右节点 第四步：删除这两个节点，将父节点添加进集合里 第五步：重复第二步到第四步，直到集合中只剩一个元素，结束循环 8.4 代码实现 节点类 //接口实现排序功能public class Node implements Comparable { int value; Node left; Node right; public Node(int value) { this.value = value; } @Override public int compareTo(Node o) { return -(this.value - o.value); //集合倒叙，从大到小 } @Override public String toString() { return "Node value=" + value ; }} 测试类 import java.util.ArrayList;import java.util.Collections;import java.util.List;public class Demo { public static void main(String[] args) { int[] arr = {5, 29, 7, 8, 14, 23, 3, 11}; Node node = createHuffmanTree(arr); System.out.println(node); //Node value=100 } //创建赫夫曼树 public static Node createHuffmanTree(int[] arr) { //使用数组中所有元素创建若干个二叉树（只有一个节点） List nodes = new ArrayList(); for (int value : arr) { nodes.add(new Node(value)); } //循环处理 while (nodes.size() >

1) {/ / sort Collections.sort (nodes); / / take out the smallest two binary trees (flashback, from big to small) Node left = nodes.get (nodes.size ()-1); / / minimum weight Node right = nodes.get (nodes.size ()-2) / / less weight / / create a new binary tree Node parent = new Node (left.value + right.value); / / delete the original two nodes nodes.remove (left); nodes.remove (right); / / put the new binary tree into the original binary tree set nodes.add (parent) / / print the result System.out.println (nodes);} return nodes.get (0);}}

Number of cycles result

[Node value=29, Node value=23, Node value=14, Node value=11, Node value=8, Node value=7, Node value=8] [Node value=29, Node value=23, Node value=14, Node value=11, Node value=8, Node value=15] [Node value=29, Node value=23, Node value=15, Node value=14, Node value=19] [Node value=29, Node value=23, Node value=19, Node value=29] [Node value=29, Node value=29, Node value=42] [Node value=42 Node value=58] [Node value=100] Node value=100Process finished with exit code 0 Chapter 9 Multipath search trees (2-3 trees, 2-3-4 trees, B trees, B + trees) 9.1 Why to use multipath search trees binary trees

A binary tree needs to be loaded into memory. If there are few nodes in the binary tree, there is no problem, but if the binary tree has a large number of nodes (for example, 100 million), the following problems exist:

Problem 1: when building a binary tree, we need to carry out many I _ swap O operations (massive data are stored in databases or files), and there are a large number of nodes. When building a binary tree, the speed is affected.

Problem 2: the large number of nodes will also cause the height of the binary tree to be very large, which will slow down the operation speed.

Solve the above problems-> multi-tree

Multi-path search tree

1. In a binary tree, each node has data items and at most two child nodes. If each node is allowed to have more data items and more child nodes, it is called multiway tree.

2. The "2-3 tree" and "2-3-4 tree" we explain later are multi-forked trees, which can optimize the binary tree by reorganizing nodes and reducing the height of the tree.

3. Give an example (the following 2-3 trees are a multi-forked tree)

9.22-3 tree

2-3 tree definition

All leaf nodes should be on the same layer.

The two nodes either have two child nodes or have no nodes

Three nodes either have no nodes or have three child nodes

There can be no node dissatisfaction.

2-3 tree insertion operation

Insertion principle:

For the insertion of 2-3 trees, like the balanced binary tree, the insertion operation must take place on the leaf nodes, and the insertion and deletion of nodes may lead to imbalance, and it is also necessary to maintain the balance dynamically when inserting and deleting nodes, but the strategy of maintaining balance is different from that of AVL trees.

After adding nodes to the AVL tree, the balance is restored by rotation, while the 2-3 tree maintains the balance by splitting the nodes upward, that is to say, the level increases upward in the process of inserting elements into the 2-3 tree, so it does not cause the leaf nodes to be at the same level, and there is no need to rotate.

There are three insertion situations:

1) for an empty tree, insert a 2-node point

2) insert a node into a 2-node leaf. Since there is only one element itself, you only need to upgrade it to 3 nodes (for example, insert 3).

3) insert a node into a 3-node leaf. Because the 3 nodes themselves have the maximum capacity, they need to be split and move up one layer of the two elements in the tree or the three elements that are inserted into the tree.

There are three situations:

Upgrade parent node (insert 5)

Upgrade root node (insert 11)

Increase the height of the tree (insert 2, remove from bottom to top)

2-3 tree deletion operation

Deletion principle: the deletion of 2-3 trees is also divided into three cases, contrary to insertion.

There are three deletion situations:

1) the deleted element is located on a 3-node leaf node, which can be deleted directly and will not affect the tree structure (e.g. delete 9)

2) the deleted element is located on a 2-node and is deleted directly to destroy the tree structure.

There are four situations:

The parents of this node are also 2 nodes and have a right child of 3 nodes (e. G. delete 1)

The parents of this node are 2 nodes, and its right child is also 2 nodes (for example: delete 4)

The parents of this node are 3 nodes (for example, delete 10)

The current tree is a full binary tree, reducing the height of the tree (e. G. delete 8)

3) the deleted element is located in a branch node that is not a leaf. At this time, traverse in the order of the tree to get the precursor or subsequent elements of this element, complement.

There are two situations:

The branch node is 2 nodes (for example: delete 4)

Branch nodes are 3 nodes (for example: delete 12)

9.3 2-3-4 tree

2-3-4 tree is an extension of 2-3 tree, including the use of 4 nodes, a 4-node contains small, medium and big three elements and four children (or no children)

Insert operation of 2-3-4 tree

1) if the node to be inserted is not 4 nodes, you can insert it directly

2) if the node to be inserted is 4 nodes, the new node is temporarily inserted into 5 nodes. Then the 5 nodes are split and merged upward, and the 5 nodes are split into two 2 nodes (the smallest element of 5 nodes, the second element of 5 nodes) and 1 3 nodes (the last two elements of 5 nodes). Then merge the second 2 node up into the parent node Then take the parent node as the current node after the element is inserted, and repeat steps (1) and (2) until the definition properties of the 2-3-4 tree are satisfied.

Delete operation of 2-3-4 tree

Delete the order to make 1, 6, 3, 4, 5, 2, 9.

9.4 B-tree

B-tree (BTree) is a balanced multi-path search tree. 2-3 trees and 2-3-4 trees are special cases of B-trees.

We call the order of the child tree with the largest node as the order of the B tree, so the 2-3 tree is the 3-order B-tree and the 2-3-4 tree is the 4-order B tree.

As shown in the following figure, for example, to find 7, we first get three elements of the root node 3, 5, and 8 from out-of-memory, and find that 7 is not there, but between 5 and 8, so we find the end by reading out-of-memory 2, 6, and 7 nodes through A2.

The data structure of B-tree is prepared for internal and external data interaction. When the data to be processed is very large, it cannot be loaded into memory all at once. At this time, the B-tree is adjusted so that the order of the B-tree matches the page size stored on the hard disk. For example, a B-tree has an order of 1001 (that is, a node contains 1000 keywords) and a height of 2 (starting from 0). It can store more than 1 billion keywords (1001x1001x1000+1001x1000+1000). As long as the root node is kept in memory permanently, it will take at most two hard disk reads to find a keyword on this tree.

For the m-order B-tree with n keywords, the worst-case search times are calculated.

There are at least 1 node in the first layer and at least 2 nodes in the second layer. Since each branch node except the root node has at least 2 ⌉ ⌉ subtrees, the third layer has at least 2 ⌉ nodes. In this way, the k + 1 layer has at least 2x (⌈ m ⌉ 2) ^ (k Mel 1). In fact, the nodes in the k + 1 layer are leaf nodes. If the m-order B-tree has n keywords, then when you find the leaf node, it is actually tantamount to finding the unsuccessful node is nroom1, so

Numer1 > = 2x (⌈ mplink 2 ⌉) ^ (kmur1), that is

When searching on a B-tree with n keywords, the number of nodes involved in the path from the root node to the keyword node is not too large.

9.5 B + tree

The B + tree can be said to be the upgraded version of the B tree. Compared with the B tree, the B + tree makes more full use of the node space, making the query speed more stable, and its speed is completely close to the dichotomy search. Most file systems and data use B+ trees to implement the index structure.

 

In the following figure B tree, we are going to traverse it, assuming that each node belongs to a different page of the hard disk, and we traverse all the elements in the middle order, page 2-page 1-page 3-page 1-page 1-page 5, page 1 traverses three times, and each time we pass through the node, we traverse the elements in the node.

The B+ tree is a metamorphic tree of the B tree that meets the needs of the file system. In the B tree, each element tree appears only once, while in the B+ tree, the elements that appear in the branch node are re-listed as their intermediate successors (leaf nodes) at the branch node location. In addition, each leaf node holds a pointer to the latter leaf node.

The following picture is the B+ tree, the gray keyword, which appears at the root node and is listed again in the leaf node.

The difference between an m-order B + tree and an m-order B tree is as follows:

The non-leaf node of n subtrees contains n keywords (nMel 1 keyword in B tree), but each keyword does not save the data, but is only used to save the index of the same keyword of the leaf node, and all the data is stored in the leaf node. (here, for the relationship between m subtrees and n keywords of non-leaf nodes, the index structure of mysql seems to be m=n+1, rather than the m _ n above)

All non-leaf node elements exist at the same time in the child node, which is the largest (or smallest) element among the child node elements.

All leaf nodes contain information about all keywords and a pointer data to the specific disk record that these keywords point to, and each leaf node has a pointer to the next adjacent leaf node, forming a linked list

9.6 Summary

The non-leaf node of the B-tree stores keywords and their corresponding data addresses, and the non-leaf node of the B + tree only stores the keyword index, not the specific data address, so a node of the B + tree can store more index elements than the B-tree, and the more keywords that need to be looked up at one time to read into memory, the smaller the height of the B + tree, and the lower the number of IO reads and writes.

The query efficiency of B-tree is not stable, the best case is to query only once (root node), the worst case is to find the leaf node, and the B + tree because the non-leaf node does not store the data address, but only the index of keywords in the leaf node. All queries have to find the leaf node to count the fate, and the query efficiency is relatively stable. This is very helpful for optimizing sql statements.

All the leaf nodes of the B+ tree form an ordered linked list, and you only need to traverse the leaf nodes to traverse the whole tree. It is convenient to query the scope of the data, but the B-tree does not support such operations or is too inefficient.

Index tables in modern databases and file systems are mostly implemented using B + trees, but not all of them

Chapter 10 the basic concept of chart structure 10.1 diagram

Graph (Graph) is a complex nonlinear structure, in which each element can have zero or more precursors or successors, that is to say, the relationship between elements is arbitrary.

Common terms:

The number of adjacent vertices connected by the same edge. The simple path from one vertex to another. And without repetition, the starting point and the ending point of the vertex loop are all the same vertex undirected graph, all edges in the directed graph have no direction, the edges in the unweighted graph have no weight value, and the edge bands in the weighted graph have certain weight values.

The structure of a graph is very simple, which is composed of vertex V set and edge E set, so the graph can be expressed as G = (VMagne E).

Undirected graph:

If the edge between vertex Vi and Vj has no direction, the edge is called undirected edge (Edge), which is represented by an unordered pair (Vi,Vj). A graph is called an undirected graph (Undirected graphs) if the edges between any two vertices in the graph are undirected edges.

For example, the following graph is an undirected graph, because it is directionless, the edges connecting vertices An and D can represent unordered queues (AMagi D) or write as (DMagol A), but they cannot be repeated. The vertex set V = {A ~ (A) B ~ () C ~ () D}; the edge set E = {(A _ () ~ ()) B), (A ~ () ~ D), (A ~ () ~ () C), (C ~ () ~ D),}

Directed graph:

Represented by ordered pairs, Vi is called Tail and Vj is called Head. If the edges between any two vertices in a graph are directed edges, the graph is called a directed graph (Directed grahs).

The following picture is a directed graph. The directed edge connecting vertex A to D is the arc, An is the end of the arc, D is the head of the arc, indicating the arc, note that can not be written. Where the vertex set V = {A _ Magi B ~ P C ~ D}; the arc set E = {,}

Note: undirected edges are indicated by parentheses "()", while directed edges are indicated by angle brackets "".

Authorized map:

The edges or arcs of some graphs have numbers related to them. The number related to the edges or arcs of a graph is called Weight. These weights can represent the distance or cost from one vertex to another. This kind of weighted graph is often called Network.

The figure below is as follows

Storage structure and implementation of 10.2 Graph

Two common storage methods of graph structure: adjacency matrix and adjacency table

Adjacency matrix

The 0 in the graph indicates that the vertex cannot lead to another vertex, on the contrary, 1 means that the vertex can lead to another vertex.

Let's take a look at the first row, which corresponds to vertex A, then we take vertex A to correspond to other points one by one, and find that vertex A can lead to any other vertex except that it can't lead to vertex D and itself.

Because the graph is undirected, if vertex A can lead to another vertex, then this vertex must also lead to vertex A, so the vertex corresponding to vertex A should also be 1.

Although we do use the adjacency matrix to represent the graph structure, but it has a fatal disadvantage, that is, there are a large number of zeros in the matrix, which will occupy a lot of memory in the program. At this point, we think about it, 0 means no, there is no reason to write, so let's take a look at the second way to represent the graph structure, which well solves the defect of the adjacency matrix.

Code implementation:

Vertex class

Public class Vertex {private String value; public Vertex (String value) {this.value = value;} public String getValue () {return value;} public void setValue (String value) {this.value = value;} @ Override public String toString () {return value;}}

Graph class

Public class Graph {private Vertex [] vertex; / / Vertex array private int currentSize; / / default vertex position public int [] [] adjMat; / / adjacency table public Graph (int size) {vertex = new Vertex [size]; adjMat = new int [size] [size];} / / add vertex public void addVertex (Vertex v) {vertex [currentSize++] = v to the graph } / / add edges public void addEdge (String v1, String v2) {/ / find the subscript int index1 = 0 of the two points; for (int I = 0; I

< vertex.length; i++) { if (vertex[i].getValue().equals(v1)) { index1 = i; break; } } int index2 = 0; for (int i = 0; i < vertex.length; i++) { if (vertex[i].getValue().equals(v2)) { index2 = i; break; } } //表示两个点互通 adjMat[index1][index2] = 1; adjMat[index2][index1] = 1; }} 测试类 public class Demo { public static void main(String[] args) { Vertex v1 = new Vertex("A"); Vertex v2 = new Vertex("B"); Vertex v3 = new Vertex("C"); Vertex v4 = new Vertex("D"); Vertex v5 = new Vertex("E"); Graph g = new Graph(5); g.addVertex(v1); g.addVertex(v2); g.addVertex(v3); g.addVertex(v4); g.addVertex(v5); //增加边 g.addEdge("A", "B"); g.addEdge("A", "C"); g.addEdge("A", "E"); g.addEdge("C", "E"); g.addEdge("C", "D"); for (int[] a : g.adjMat) { System.out.println(Arrays.toString(a)); } }} 结果值 [0, 1, 1, 0, 1][1, 0, 0, 0, 0][1, 0, 0, 1, 1][0, 0, 1, 0, 0][1, 0, 1, 0, 0]邻接表 邻接表 是由每个顶点以及它的相邻顶点组成的 如上图：图中最左侧红色的表示各个顶点，它们对应的那一行存储着与它相关联的顶点 顶点A 与 顶点B 、顶点C 、顶点E 相关联 顶点B 与 顶点A 相关联 顶点C 与 顶点A 、顶点D 、顶点E 相关联 顶点D 与 顶点C 相关联 顶点E 与 顶点A 、顶点C 相关联 10.3 图的遍历方式及实现 从图中某一顶点出发访遍图中其余顶点，且使每一个顶点仅被访问一次，这一过程就叫做图的遍历 在图结构中，存在着两种遍历搜索的方式，分别是 广度优先搜索 和 深度优先搜索 广度优先搜索 广度优先遍历（BFS）：类似于图的层次遍历，它的基本思想是：首先访问起始顶点v，然后选取v的所有邻接点进行访问，再依次对v的邻接点相邻接的所有点进行访问，以此类推，直到所有顶点都被访问过为止 BFS和树的层次遍历一样，采取队列实现，这里添加一个标记数组，用来标记遍历过的顶点 执行步骤： 1、先把 A 压入队列，然后做出队操作，A 出队 2、把 A 直接相关的顶点 ，B、F 做入队操作 3、B 做出队操作，B 相关的点 C、I、G 做入队操作 4、F 做出队操作，F 相关的点 E 做入队操作 5、C 做出队操作，C 相关的点 D 做入队操作 6、I 做出队操作（I 相关的点B、C、D 都已经做过入队操作了，不能重复入队） 7、G 做出队操作，G 相关的点 H 做入队操作 8、E 做出队操作… 9、D 做出队操作… 10、H 做出队操作，没有元素了 代码实现： 深度优先搜索 深度优先遍历（DFS）：从一个顶点开始，沿着一条路径一直搜索，直到到达该路径的最后一个结点，然后回退到之前经过但未搜索过的路径继续搜索，直到所有路径和结点都被搜索完毕 DFS与二叉树的先序遍历类似，可以采用递归或者栈的方式实现 执行步骤： 1、从 1 出发，路径为：1 ->

2-> 3-> 6-> 9-> 8-> 5-> 4

2. When the search reaches 4, no unvisited points are found in the neighbors. At this time, we have to go back and look for other paths that have not been searched.

3. Go back to 5, and no unvisited points are found adjacent to it. Continue to retreat.

4. Return to 8, and adjacent points 7 that have not been accessed are found. The path is 8-> 7.

5. When the search reaches 7 and no unvisited points are found in the neighborhood, we have to go back at this time.

6. Return path 7-> 8-> 9-> 6-> 3-> 2-> 1. End of process.

Code implementation:

Stack class

The bottom layer of the public class MyStack {/ / stack uses arrays to store data / / private int [] elements; int [] elements; / / tests using public MyStack () {elements = new int [0];} / / add elements public void push (int element) {/ / create a new array int [] newArr = new int [elements.length + 1] / / copy the elements from the original array to the new array for (int I = 0; I

< elements.length; i++) { newArr[i] = elements[i]; } //把添加的元素放入新数组中 newArr[elements.length] = element; //使用新数组替换旧数组 elements = newArr; } //取出栈顶元素 public int pop() { //当栈中没有元素 if (is_empty()) { throw new RuntimeException("栈空"); } //取出数组的最后一个元素 int element = elements[elements.length - 1]; //创建一个新数组 int[] newArr = new int[elements.length - 1]; //原数组中除了最后一个元素其他元素放入新数组 for (int i = 0; i < elements.length - 1; i++) { newArr[i] = elements[i]; } elements = newArr; return element; } //查看栈顶元素 public int peek() { return elements[elements.length - 1]; } //判断栈是否为空 public boolean is_empty() { return elements.length == 0; } //查看栈的元素个数 public int size() { return elements.length; }} 顶点类 public class Vertex { private String value; public boolean visited; //访问状态 public Vertex(String value) { super(); this.value = value; } public String getValue() { return value; } public void setValue(String value) { this.value = value; } @Override public String toString() { return value; }} 图类 import mystack.MyStack;public class Graph { private Vertex[] vertex; //顶点数组 private int currentSize; //默认顶点位置 public int[][] adjMat; //邻接表 private MyStack stack = new MyStack(); //栈 private int currentIndex; //当前遍历的下标 public Graph(int size) { vertex = new Vertex[size]; adjMat = new int[size][size]; } //向图中加入顶点 public void addVertex(Vertex v) { vertex[currentSize++] = v; } //添加边 public void addEdge(String v1, String v2) { //找出两个点的下标 int index1 = 0; for (int i = 0; i < vertex.length; i++) { if (vertex[i].getValue().equals(v1)) { index1 = i; break; } } int index2 = 0; for (int i = 0; i < vertex.length; i++) { if (vertex[i].getValue().equals(v2)) { index2 = i; break; } } //表示两个点互通 adjMat[index1][index2] = 1; adjMat[index2][index1] = 1; } //深度优先搜索 public void dfs() { //把第0个顶点标记为已访问状态 vertex[0].visited = true; //把第0个的下标放入栈中 stack.push(0); //打印顶点值 System.out.println(vertex[0].getValue()); //遍历 out: while (!stack.is_empty()) { for (int i = currentIndex + 1; i < vertex.length; i++) { //如果和下一个遍历的元素是通的 if (adjMat[currentIndex][i] == 1 && vertex[i].visited == false) { //把下一个元素压入栈中 stack.push(i); vertex[i].visited = true; System.out.println(vertex[i].getValue()); continue out; } } //弹出栈顶元素（往后退） stack.pop(); //修改当前位置为栈顶元素的位置 if (!stack.is_empty()) { currentIndex = stack.peek(); } } }} 测试类 import java.util.Arrays;public class Demo { public static void main(String[] args) { Vertex v1 = new Vertex("A"); Vertex v2 = new Vertex("B"); Vertex v3 = new Vertex("C"); Vertex v4 = new Vertex("D"); Vertex v5 = new Vertex("E"); Graph g = new Graph(5); g.addVertex(v1); g.addVertex(v2); g.addVertex(v3); g.addVertex(v4); g.addVertex(v5); //增加边 g.addEdge("A", "B"); g.addEdge("A", "C"); g.addEdge("A", "E"); g.addEdge("C", "E"); g.addEdge("C", "D"); for (int[] a : g.adjMat) { System.out.println(Arrays.toString(a)); } //深度优先遍历 g.dfs();// A// B// C// E// D }}第11章 冒泡排序（含改进版）11.1 冒泡排序概念 冒泡排序（Bubble Sort）是一种简单的排序算法。它重复地遍历要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。遍历数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢"浮"到数列的顶端。 运行流程： 比较相邻的元素。如果第一个比第二个大（升序），就交换他们两个。 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。 针对所有的元素重复以上的步骤，除了最后一个。 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。 动图实现： 静图详解： 交换过程图示(第一次)： 那么我们需要进行n-1次冒泡过程，每次对应的比较次数如下图所示： 11.2 代码实现import java.util.Arrays;public class BubbleSort { public static void main(String[] args) { int[] arr = {4, 5, 6, 3, 2, 1}; bubbleSort(arr);// [4, 5, 3, 2, 1, 6]// [4, 3, 2, 1, 5, 6]// [3, 2, 1, 4, 5, 6]// [2, 1, 3, 4, 5, 6]// [1, 2, 3, 4, 5, 6] } //冒泡排序，共需要比较length-1轮 public static void bubbleSort(int[] arr) { //控制一共比较多少轮 for (int i = 0; i < arr.length - 1; i++) { //控制比较次数 for (int j = 0; j < arr.length - 1 - i; j++) { if (arr[j] >

Arr [j + 1]) {int temp = arr [j]; arr [j] = arr [j + 1]; arr [j + 1] = temp;}} / / print the result System.out.println (Arrays.toString (arr)) after each sort 11.3 time complexity

Optimal time complexity: O (n) (means that a traversal finds that there are no elements to swap, and the sort ends. )

Worst-case time complexity: O (n ^ 2)

Stability: stability

Sorting analysis: there are a total of 6 numbers in the array to be sorted, five comparisons were made in the first round, four comparisons were made in the second round, and so on, and one comparison was made in the last round.

When the total number of array elements is N, the total number of comparisons required is: (Nmur1) + (Nmur2) + (Nmur3) +. 1 compare N* (NMu1) / 2

The algorithm makes about N ^ 2 / 2 comparisons. Because data is exchanged only when the previous element is larger than the later element, the number of exchanges is less than the number of comparisons. If the data is random and about half of the data needs to be exchanged, the number of exchanges is N ^ 2 / 4 (although in the worst case, when the initial data is in reverse order, each comparison needs to be exchanged).

The number of operations of exchange and comparison is proportional to N ^ 2. Because the constant is ignored in the large O representation, the time complexity of bubble sorting is O (N ^ 2).

The time complexity of O (N2) is a bad result, especially in the case of a large amount of data. Therefore, bubbling sorting is not usually used in practical applications.

11.4 Code improvement

The traditional bubbling algorithm only determines the maximum value for each sort, and we can do positive and negative bubbles twice in each cycle to find the maximum and minimum values respectively, so that the number of rounds of sorting can be reduced by half.

Import java.util.Arrays;public class BubbleSort {public static void main (String [] args) {int [] arr = {4,5,6,3,2,1}; bubbleSort (arr) / / [1, 4, 5, 3, 2, 6] / / [1, 2, 4, 3, 5, 6] / / [1, 2, 3, 4, 5, 6]} / / improved bubble sorting public static void bubbleSort (int [] arr) {int left = 0; int right = arr.length-1; while (left)

< right) { //正向冒泡，确定最大值 for (int i = left; i < right; ++i) { //如果前一位大于后一位，交换位置 if (arr[i] >

Arr [I + 1]) {int temp = arr [I]; arr [I] = arr [I + 1]; arr [I + 1] = temp;}}-- right; / / reverse bubbling, determine the minimum for (int j = right; j > left) -- j) {/ / if the previous bit is greater than the last bit, swap position if (arr [j])

< arr[j - 1]) { int temp = arr[j]; arr[j] = arr[j - 1]; arr[j - 1] = temp; } } ++left; System.out.println(Arrays.toString(arr)); } }}第12章 选择排序（含改进版）12.1 选择排序概念 选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。 选择排序的主要优点与数据移动有关。如果某个元素位于正确的最终位置上，则它不会被移动。选择排序每次交换一对元素，它们当中至少有一个将被移到其最终位置上，因此对n个元素的表进行排序总共进行至多n-1次交换。在所有的完全依靠交换去移动元素的排序方法中，选择排序属于非常好的一种 动图展示： 动图1： 动图2： 12.2 代码实现import java.util.Arrays;public class seletsort { public static void main(String[] args) { int[] arr = {4, 5, 6, 3, 2, 1}; selectSort(arr);// [1, 5, 6, 3, 2, 4]// [1, 2, 6, 3, 5, 4]// [1, 2, 3, 6, 5, 4]// [1, 2, 3, 4, 5, 6]// [1, 2, 3, 4, 5, 6]// [1, 2, 3, 4, 5, 6] } //选择排序 public static void selectSort(int[] arr) { //遍历所有的数 for (int i = 0; i < arr.length; i++) { int minIndex = i; //把当前遍历的数和后面所有的数依次进行比较，并记录最小的数的下标 for (int j = i + 1; j < arr.length; j++) { //如果后面比较的数比记录的最小的数小 if (arr[minIndex] >

Arr [j]) {/ / record the subscript of the smallest number minIndex = j;}} / / if a smaller element is found, swap position with the first element (the first is not the smallest element) if (I! = minIndex) {int temp = arr [I] Arr [I] = arr [minIndex]; arr [minIndex] = temp;} / / print the result of each sort System.out.println (Arrays.toString (arr));} 12.3 time complexity

Optimal time complexity: O (n ^ 2)

Worst-case time complexity: O (n ^ 2)

Stability: unstable (considering the maximum selection of ascending order each time)

The selection sort is the same as the bubble sort, it needs to be compared with N * (NMUI 1) / 2 times, but only N times of exchange is needed. When N is very large, the time influence of the exchange times is greater, so the time complexity of selecting sort is O (N ^ 2).

Although selective sorting and bubble sorting belong to the same order of magnitude in time complexity, there is no doubt that selective sorting is more efficient because it has fewer exchange operations, and when the time level of swap operations is much larger than that of comparison operations, the speed of selective sorting is quite fast.

12.4 Code improvement

The traditional selective sorting only determines the minimum value each time. According to the experience of the improved bubbling algorithm, we can improve the sorting algorithm as follows: each sort determines two maximum values-the maximum value and the minimum value, so that the number of sorting trips can be reduced by half.

The improved code is as follows:

Import java.util.Arrays;public class seletsort {public static void main (String [] args) {int [] arr = {4,5,6,3,2,1}; selectSort (arr) / / [1, 5, 4, 3, 2, 6] / / [1, 2, 4, 3, 5, 6] / / [1, 2, 3, 4, 5, 6]} / / Select improved sorting public static void selectSort (int [] arr) {int minIndex; / / Storage minor int maxIndex of the smallest element / / small scale for (int I = 0; I) that stores the largest element

< arr.length / 2; i++) { minIndex = i; maxIndex = i; //每完成一轮排序，就确定了两个最值，下一轮排序时比较范围减少两个元素 for (int j = i + 1; j arr[maxIndex]) { maxIndex = j; } } //如果发现了更小的元素，与第一个元素交换位置（第一个不是最小的元素） if (i != minIndex) { int temp = arr[i]; arr[i] = arr[minIndex]; arr[minIndex] = temp; // 原来的第一个元素已经与下标为minIndex的元素交换了位置 // 所以现在arr[minIndex]存放的才是之前第一个元素中的数据 // 如果之前maxIndex指向的是第一个元素，那么需要将maxIndex重新指向arr[minIndex] if (maxIndex == i) { maxIndex = minIndex; } } // 如果发现了更大的元素，与最后一个元素交换位置 if (arr.length - 1 - i != maxIndex) { int temp = arr[arr.length - 1 - i]; arr[arr.length - 1 - i] = arr[maxIndex]; arr[maxIndex] = temp; } System.out.println(Arrays.toString(arr)); } }}第13章 插入排序（含改进版）13.1 插入排序概念 插入排序（Insertion Sort）是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间 动图展示： 13.2 代码实现import java.util.Arrays;public class InsertSort { public static void main(String[] args) { int[] arr = {4, 5, 6, 3, 2, 1}; insertSort(arr);// [4, 5, 6, 3, 2, 1]// [4, 5, 6, 3, 2, 1]// [3, 4, 5, 6, 2, 1]// [2, 3, 4, 5, 6, 1]// [1, 2, 3, 4, 5, 6] } //插入排序 public static void insertSort(int[] arr) { //遍历所有的数字，从第二个开始和前一个比较 for (int i = 1; i < arr.length; i++) { //如果当前数字比前一个数字小 if (arr[i] < arr[i - 1]) { //把当前遍历的数字存起来 int temp = arr[i]; //遍历当前数字前面的数字 int j; for (j = i - 1; j >

= 0 & & temp

< arr[j]; j--) { //把前一个数赋给后一个数 arr[j + 1] = arr[j]; } //把临时变量（外层for循环的当前元素）赋给不满足条件的后一个元素 arr[j + 1] = temp; } //打印每次排序后的结果 System.out.println(Arrays.toString(arr)); } }}13.3 时间复杂度 最优时间复杂度：O(n) （升序排列，序列已经处于升序状态） 最坏时间复杂度：O(n^2) 稳定性：稳定 在第一趟排序中，插入排序最多比较一次，第二趟最多比较两次，依次类推，最后一趟最多比较N-1次。因此有：1+2+3+...+N-1 = N*N(N-1)/2 因为在每趟排序发现插入点之前，平均来说，只有全体数据项的一半进行比较，我们除以2得到：N*N(N-1)/4 复制的次数大致等于比较的次数，然而，一次复制与一次比较的时间消耗不同，所以相对于随机数据，这个算法比冒泡排序快一倍，比选择排序略快。 与冒泡排序、选择排序一样，插入排序的时间复杂度仍然为O(N^2)，这三者被称为简单排序或者基本排序，三者都是稳定的排序算法。 如果待排序数组基本有序时，插入排序的效率会更高 13.4 代码改进 在插入某个元素之前需要先确定该元素在有序数组中的位置，上例的做法是对有序数组中的元素逐个扫描，当数据量比较大的时候，这是一个很耗时间的过程，可以采用二分查找法改进，这种排序也被称为二分插入排序 import java.util.Arrays;public class InsertSort { public static void main(String[] args) { int[] arr = {4, 5, 6, 3, 2, 1}; insertSort(arr);// [4, 5, 6, 3, 2, 1]// [4, 5, 6, 3, 2, 1]// [3, 4, 5, 6, 2, 1]// [2, 3, 4, 5, 6, 1]// [1, 2, 3, 4, 5, 6] } //二分插入排序 public static void insertSort(int[] arr) { for (int i = 1; i < arr.length; i++) { //如果新记录小于有序序列的最大元素，则用二分法找出新纪录在有序序列中的位置 if (arr[i] < arr[i - 1]) { int temp = arr[i]; //定义temp存储所要插入的数 int left = 0; //最左边的数，从str[0]开始 int right = i - 1; //最右边位，所要插入那个数的前一位 while (left left; j--) { arr[j] = arr[j - 1]; } arr[left] = temp; } System.out.println(Arrays.toString(arr)); } }}第14章 归并排序14.1 归并排序概念 归并排序（Merge Sort）是采用分治法的一个非常典型的应用。归并排序的思想就是先递归分解数组，再合并数组。 将数组分解最小之后，然后合并两个有序数组，基本思路是比较两个数组的最前面的数，谁小就先取谁，取了后相应的指针就往后移一位。然后再比较，直至一个数组为空，最后把另一个数组的剩余部分复制过来即可。 动图展示： 动图1 动图2 14.2 代码实现import java.util.Arrays;public class MergeSort { public static void main(String[] args) { int[] arr = {6, 5, 3, 1, 8, 7, 2, 4}; mergeSort(arr, 0, arr.length - 1);// [5, 6, 3, 1, 8, 7, 2, 4]// [5, 6, 1, 3, 8, 7, 2, 4]// [1, 3, 5, 6, 8, 7, 2, 4]// [1, 3, 5, 6, 7, 8, 2, 4]// [1, 3, 5, 6, 7, 8, 2, 4]// [1, 3, 5, 6, 2, 4, 7, 8]// [1, 2, 3, 4, 5, 6, 7, 8] } //归并排序 public static void mergeSort(int[] arr, int low, int high) { int middle = (high + low) / 2; //递归结束 if (low < high) { //处理左边 mergeSort(arr, low, middle); //处理右边 mergeSort(arr, middle + 1, high); //归并 merge(arr, low, middle, high); } } //归并操作 //low:开始位置，middle：分割位置，high：结束位置 public static void merge(int[] arr, int low, int middle, int high) { //用于存储归并后的临时数组 int[] temp = new int[high - low + 1]; //记录第一个数组中需要遍历的下标 int i = low; //记录第二个数组中需要遍历的下标 int j = middle + 1; //用于记录在临时数组中存放的下标 int index = 0; //遍历两个数组取出小的数字，放入临时数组中 while (i = arr[2i+2] 小顶堆：arr[i] 0; i--) { int temp = arr[0]; arr[0] = arr[i]; arr[i] = temp; //再把前面的处理为大顶堆 maxHeap(arr, i, 0); } } //数组转大顶堆,size:调整多少（从最后一个向前减），index:调整哪一个（最后一个非叶子节点） public static void maxHeap(int[] arr, int size, int index) { //左子节点 int leftNode = 2 * index + 1; //右子节点 int rightNode = 2 * index + 2; //先设当前为最大节点 int max = index; //和两个子节点分别对比，找出最大的节点 if (leftNode < size && arr[leftNode] >

Arr [max]) {max = leftNode;} if (rightNode

< size && arr[rightNode] >

Arr [max]) {max = rightNode;} / / Exchange position if (max! = index) {int temp = arr [index]; arr [index] = arr [max]; arr [max] = temp / / after switching positions, the previously arranged heaps may be destroyed, so the heaps arranged between them need to be readjusted maxHeap (arr, size, max);} / / print the result of each sort System.out.println (Arrays.toString (arr));}} 17.3 time complexity

Optimal time complexity: O (nlogn)

Worst-case time complexity: O (nlogn)

Stability: instability

Its running time is mainly spent on the initial build heap and repeated filtering when rebuilding the heap.

In the process of building the heap, because we are building a complete binary tree from the lowest and rightmost non-terminal node, compare it with its child and, if necessary, perform no more than two comparisons and swaps for each non-terminal node, so the time complexity of the whole build heap is O (n).

In the formal sorting, it takes O (logi) time to reconstruct the heap (the distance from a node of the complete binary tree to the root node is log2i+1), and the top record needs to be taken once, so the time complexity of reconstructing the heap is O (nlogn).

So overall, the time complexity of heap sorting is O (nlogn). Because heap sorting is not sensitive to the sorting state of the original record, it is O (nlogn) in terms of best, worst and average time complexity. This is obviously much better in terms of performance than the time complexity of bubbling, simple selection, and direct insertion of O (N2).

In terms of space complexity, it has only one temporary storage unit for exchange, which is also very good. However, because the comparison and exchange of records are carried out by jumping, heap sorting is an unstable sorting method.

Chapter 18 count sort 18.1 count sort concept

Count sorting (Counting Sort) is not a comparison-based sorting algorithm, its core is to convert the input data values into keys and store them in the extra array space. As a sort of linear time complexity, counting sorting requires that the input data must be integers with a definite range.

Sort steps:

Find the largest and smallest elements in the array to be sorted

Count the number of occurrences of each element with a value of I in the array and deposit it in the item I of the array C.

Add up all counts (starting with the first element in C, each item is added to the previous one)

Backfill the target array: place each element I in the C (I) item of the new array, and subtract C (I) from 1 for each element

The moving picture shows:

Code implementation import java.util.Arrays;public class CountingSort {public static void main (String [] args) {/ / Test int [] arr = {1, 4, 6, 7, 5, 4, 3, 2, 1, 4, 5, 10, 9, 10, 3}; sortCount (arr); System.out.println (Arrays.toString (arr)) / / [1, 1, 2, 3, 3, 4, 4, 4, 5, 5, 6, 7, 9, 10, 10] / / count sort public static void sortCount (int [] arr) {/ / one: get the maximum and minimum values, and calculate the length of the intermediate array: int max = arr [0]; int min = arr [0]; int len = arr.length For (int I: arr) {if (I > max) {max = I;} if (I < min) {min = I }} / / II, with the maximum and minimum values, you can determine the length of the intermediate array (the intermediate array is used to record the frequency of each value in the original data) int [] temp = new int [max-min + 1]; / / three. Loop through the old array count sort: that is to count the frequency of the occurrence of the original array values to the intermediate array temp (int I = 0; I < len; iArr +) {temp [arr [I]-min] + = 1;} / 4, traversal output / / cycle each element in the subscript of the count sequencer for (int I = 0, index = 0) I < temp.length; iTunes +) {int item = temp [I]; the number of loops while (item--! = 0) {/ / thought that the original min was reduced and now with min, the value becomes the original value arr [index++] = I + min;} 18.3 time complexity

Optimal time complexity: O (nymk)

Worst-case time complexity: O (nymk)

Stability: instability

Counting sorting is a stable sorting algorithm. When the input element is n integers between 0 and k, the time complexity is O (n ~ k) and the space complexity is also O (n ~ k), which is faster than any comparison sorting algorithm. When k is not very large and the sequence is relatively centralized, counting sorting is a very effective sorting algorithm.

Chapter 19 barrel sort 19.1 barrel sort concept

Bucket sort, or so-called box sorting, is a sorting algorithm that works by dividing an array into a limited number of buckets. Each bucket is sorted individually (it is possible to use another sorting algorithm or to continue to use bucket sorting recursively), and finally the records in each bucket are listed in turn to get the ordered sequence. Bucket sorting is an inductive result of pigeon nest sorting. Bucket sorting uses the linear time o (n) when the values in the array to be sorted are evenly distributed. But bucket sorting is not a comparative sort, and it is not affected by the lower bound of O (n log n).

Sort steps:

Set a quantitative array as an empty bucket

Traverse the input data and put the data in the corresponding bucket one by one

Sort each bucket that is not empty

Never put the ordered data together in a bucket that is not empty.

The moving picture shows:

The still picture shows:

Code implementation package sort;import java.util.ArrayList;import java.util.Collections;public class BucketSort {public static void main (String [] args) {int [] arr = {29, 25, 3, 49, 9, 37, 21, 43}; bucketSort (arr) / / the result is: [[3,9], [], [21,25], [29], [37], [43,49]]} public static void bucketSort (int [] arr) {/ / large when small, small when big int max = Integer.MIN_VALUE; int min = Integer.MAX_VALUE / / find the minimum and maximum value for (int item0, len=arr.length; I)

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.