The data structure

The physical structure

Sequential storage structure

Data elements are stored in sequential memory units in the same physical order as their logical order

implementation

An array of

Chain storage structure

Data is stored in address-scattered storage cells, the logical structure of which is specified by additional information

implementation

Use Pointers to represent the logical structure of data

Logical structure

The linear table
The tree
figure

Linear structure

Data structures with linear relationships

The characteristics of

Ai has only one predecessor and one successor, A0 has no predecessor and an has no successor
The logical order of data elements in a linear structure can be determined by ordinal number

implementation

Abstract Abstract data types

ADT List<T>{
	boolean isEmpty(a)
    int size(a)
    T get(int i)
    void set(int i,T x)
    String toString(a)
    int insert(T x,int i)
    int insert(T x)
    T remove(int i)
    void clear(a)    
    int search(T x)
    boolean contains(T key)
    int insertDifferent(T x)
    T remove(T x)
    boolean equals(Object obj)
    void addAll(List<T> lsit)    
}
Copy the code

Sequential storage structure

public class SeqList<T>{
	protected Object[] element;
    private int n;
    public SeqList(int length){
        if(length>=0) {this.element = new Object[length];
        	this.n = 0;   
        }else{
            throw new IllegalArgumentsException("Table length can not be negative"); }}public SeqList(a){
        this(64);
    }
    public SeqList(T[] values){
        this(values.length);
        for(int i=0; i<values.length; i++){this.element[i] = values[i];
        }
        this.n = values.length;
    }
    public boolean isEmpty(a){
        return this.n==0;
    }
    public int size(a){
        return this.n;
    }
    public T get(int i){
        if(i>=0) {return this.element[i];
        }else{
            throw new IllegalArgumentsException("The subscript cannot be negative."); }}public void set(int i,T x){
        this.element[i] = x;
    }
    public String toString(a){}}Copy the code

An array of

A collection of data elements of the same type

Continuity of storage space

Unable to insert or delete

The complexity of the

Space: O (n)

Time: O (n)

Chain storage structure

public Node<T>{
    public T date;
    public Node<T> next;
    public Node(T data,Node<T> next){
        this.data = data;
        this.next = next;
    }
    public Node(a){
        this(null.null);
    }
    public String toString(a){
        return this.data.toString(); }}Copy the code

string

The stack and queue

The stack

A linear table that allows insertions and deletions in only one segment

Top of stack: Allows operations

Bottom of stack: no operation allowed

Features:

Last in first Out (LIFO)

implementation

public interface Stack<T>{
    public abstract boolean isEmpty(a);
    public abstract void push(T x);
    public abstract T peek(a);
    public abstract T pop(a);
}
Copy the code

Sequential storage structure

public final class SeqStack<T>{
    private SeqList<T> list;
    public SeqStack(int length){
        this.list = new Seqlist<T>(length);
    }
    public SeqStack(a){
        this(64);
    }
    public boolean isEmpty(a){
        return this.list.isEmpty();
    }
    public void push(T x){
        this.list.insert(x);
    }
    public T peek(a){
        return this.list.get(this.list.size()-1);
    }
    public T pop(a){
        return this.list.remove(this.list.size()-1); }}Copy the code

Chain storage structure

public final class LinkedStack<T> impelements Stack<T>{
    private SinglyList<T> list;
    public LinkedStack(a){
        this.list = new SinglyList<T>();
    }
    public boolean isEmpty(a){
    	return this.list.isEmpty();
    }
    public void push(T x){
        this.list.insert(0,x);
    }
    public T peek(a){
        return this.list.get(0);
    }
    public T pop(a){
        return this.list.remove(0); }}Copy the code

application

The implementation basis for nested calls
Implement recursive algorithms in a non-recursive manner

The queue

Delete and insert linear tables at both ends

Features:

First in, first out (FIFO)

implementation

public interface Queue<T>{
    public abstract boolean isEmpty(a);
    public abstract boolean add(T x);
    public abstract T peek(a);
    public abstract T poll(a);
} 
Copy the code

Sequential storage structure

public final class SeqQueue<T> implements Queue<T>{
    private Object element[];
    private int front,rear;
    public SeqQuene(int length){
        if(length<64){
            length = 64;
        }
        this.element = new Object[length];
        this.front = this.rear = 0;
    }
    public SeqQueue(a){
        this(64);
    }
    public boolean isEmpty(a){
        return this.front = this.rear;
    }
    public boolean add(T x){
        if(x==null) {return false;
        }
        if(this.front==(this.rear+1) %this.element.length){
            Object[] temp = this.element;
            this.element = new Object[temp*2];
            int j = 0;
            for(int i=this.front; i! =this.rear; i=(i+1)%temp.length){
                this.element[j++] = temp[i];
            }
            this.front = 0;
            this.rear= j;
        }
        this.element[this.rear] = x;
        this.rear = (this.rear+1) %this.element.length;
        return true;
    }
    public T peek(a){
        reutnr this.isEmpty()?null:(T)this.element[this.front];
    }
    public T poll(a){
        if(this.isEmpty()){
            return null;
        }
        T temp = (T)this.element[this.front];
        this.front = (this.rear+1) %this.element.length;
        returntemp; }}Copy the code

Arrays and generalized tables

figure

A data structure consisting of a set of vertices and a set of relations between vertices and between vertices

Undirected graph

Without direction, edges are represented by unordered pairs

Directed graph

Edges have directions, and each edge is represented by an ordered pair

Complete graph

The number of edges reaches its maximum

Undirected graph

n*(n-1)/2

Directed graph

N * (n – 1)

Weighted graph

Edges have weights

It also becomes the network

Adjacent vertices

Two vertices in an edge

The degree of

A degree of zero is called an outlier
Degree one is called the suspension point

In a digraph there is a difference between in and out

Degrees are degrees in plus degrees out

The number of edges of an undirected graph is equal to 1/2 of the sum of all vertex degrees

The sum of the input degrees of all vertices of a directed graph is equal to the sum of the output degrees is equal to the number of edges

subgraph

Vertices and edges are subsets

When the vertices are the same, is to generate a subgraph

connectivity

A vertex that has a path to another vertex is connected

A graph is connected if any vertex is connected to another vertex

The maximal connected subgraph of an unconnected graph is a connected component

It is strongly connected when any vertex is connected to another vertex and there is a return path

The path

implementation

Matrix class

public class Matrix {                                      
	private int rows,columns;
	private int[][] elements;
	public Matrix(int m,int n) {
		this.elements = new int[m][n];
		this.rows = m;
		this.columns = n;
	}
	public Matrix(int m,int n,int[][] value) {
		this.elements = new int[m][n];
		this.rows = m;
		this.columns = n;
		for(int i=0; i<value.length&&i<m; i++) {
			for(int j=0; j<value[i].length&&j<n; j++) {
				this.elements[i][j] = value[i][j]; }}}public Matrix(int n) {
		this(n,n);
	}
	public int getRows(a) {
		return this.rows;
	}
	public int getColumns(a) {
		return this.columns;
	}
	public int get(int m,int n) {
		if(m>=0&&m<rows&&n>=0&&n<columns) {
			return this.elements[m][n];
		}
		throw new IndexOutOfBoundsException("Exceeding the number of rows or columns in the matrix");
	}
	public void set(int m, int n, int x) {
		if(m>=0&&m<rows&&n>=0&&n<columns) {
			this.elements[m][n] = x;
		}
		else throw new IndexOutOfBoundsException();
	}
	public String toString(a) {
		String str = "The matrix" + this.getClass().getName()+"("+this.rows+"*"+this.columns+"): \n";
		for(int i=0; i<this.rows; i++) {for(int j=0; j<this.columns; j++) { str+=String.format("%6d".this.elements[i][j]);
			}
			str += "\n";
		}
		return str;
	}
	public void setRowsColumns(int m,int n) {}public boolean equals(Matrix mat) {
		
		if(elements.length! =mat.rows||elements[0].length! =mat.columns) {return false;
		}
		else {
			for(int i=0; i<elements.length; i++) {
				for(int j=0; j<elements[0].length; j++) {
					if(elements[i][j]! =mat.elements[i][j]) {return false; }}}return true; }}public boolean isSymmetric(a) {
		int i = 1,j = 0;
		if(elements.length! =elements[0].length) {
			return false;
		}
		for(; i<elements.length; i++) {for(; j<i; j++) {if(elements[i][j]! =elements[j][i]) {return false; }}}return true;
	}
Copy the code

Adjacency matrix

Sequential storage structure

Use linear tables for storage

// Vertex class, linear tables store vertices
public abstract class AbstractGraph<T>{
	protected static final int MAX_WEIGHT = 0x0000ffff;
    protected SeqList<T> vertexlist;
    public AbstractGraph(int length){
        this.vertexlist = new SeqList<T>(length);
    }
    public AbstractGraph(a){
        this(10);
    }
    public int vertexCount(a){
        return this.vertexlist.size();
    }
    public String toString(a){
        return "Vertex set :"+ this.vertexlist.toString()+"\n";
    }
    public void setVertex(int i, T x){
        this.vertexlist.set(i,x);
    }
    public abstract int insertVertex(a);
    public abstract void removeVertex(a);
    public abstract int weight(int i,int j);
    public abstract int next(int i,int j);
}
Copy the code

/ / class
// graph (starting number, ending number, weight)
public class Triple implements Comparable<Triple>, Addible<Triple> {
	public int row,column,value;
	public int getRow(a) {
		return row;
	}
	public void setRow(int row) {
		this.row = row;
	}
	public int getColumn(a) {
		return column;
	}
	public void setColumn(int column) {
		this.column = column;
	}
	public int getValue(a) {
		return value;
	}
	public void setValue(int value) {
		this.value = value;
	}
	public Triple(int row,int column,int value) {
		if(row>=0&&column>=0) {
			this.row = row;
			this.column = column;
			this.value = value;
		}
		else throw new IllegalArgumentException("");
	}
	public Triple(Triple tri) {
		this(tri.row, tri.column, tri.value);
	}
	public Triple(a) {
		this(0.0.0);
	}
	@Override
	public void add(Triple tri) {
		if(this.compareTo(tri)==0) {
			this.value += tri.value;
		}else {
			throw newIllegalArgumentException(); }}public String toString(a) {
		return "("+row+","+column+","+value+")";
	}
	@Override
	public boolean removable(a) {
		return this.value==0;
	}
	@Override
	public int compareTo(Triple o) {
		// TODO Auto-generated method stub
		if(this.row<o.row) {
			return -1;
		}else if(this.row==o.row&&this.column==o.column){
			return 0;	
		}else if(this.row==o.row&&this.column==o.column) {
			return -1;
		}else {
			return 1; }}public boolean equals(Triple tri) {
		if(this.row==tri.row&&this.column==tri.column&&this.value==tri.value) return true;
		else return false;
	}
	public Triple toSymmetry(a) {
		return new Triple(this.column,this.row,this.value); }}Copy the code

public class MatrixGraph<T> extends AbatractGraph<T>{
	private SeqList<T> vertexlist;
	private Matrix adjaMatrix;
	public int vertexCount(a) {
		return this.vertexlist.size();
	}
	
	public int weight(int i, int j) {
		return this.adjaMatrix.get(i, j);
	}
	public T getVertex(int i) {
		return this.vertexlist.get(i);
	}
	public MatrixGraph(SeqList<T> vertexlist, Matrix adjaMatrix) {						     	if(vertexlist.size()! =adjaMatrix.getRows()||vertexlist.size()! =adjaMatrix.getColumns()) {throw new IndexOutOfBoundsException("");
		}
		this.vertexlist = vertexlist;
		this.adjaMatrix = adjaMatrix;
	}			
	
	public MatrixGraph(a) {
		vertexlist = new SeqList<T>(10);		
		adjaMatrix = new Matrix(10); }}Copy the code

edge

insert

public void insertEdge(int i,int j,int weight){
    if(! j=i){if(weight<=0||weight>MAX_WEIGHT){		// When the weights are valid and not ring
            weight = MAX_WEIGHT;
        }
        this.matrix.set(i,j,weight);			// Set matrix weights to represent edges
        
    }else throw new IllegalArgunmentException("Can't loop.");
    public void insertEdge(Triple edge){
        this.insertEdge(edge.row,edge.column,edge.value);// Set edges with triples of edge classes}}Copy the code

delete

public void removeEdge(int i,int j){
    if(i! =j)this.matrix.set(i,j,MAX_WEIGHT);
    
}
public void removeEdge(Triple edge){
    this.removeEdge(edge.row,edge.column);
}
Copy the code

The vertices

insert

public int insertVertex(T x){
    int i = this.vertexlist.size(x);
    if(i>=this.matrix.getRow()){
        this.matrix.setRowColumns(i+1,i+1);
    }
    for(int j=0; j<i; j++){this.matrix.set(i,j,MAX_WEIGHT);
        this.matrix.set(j,i,MAX_WEIGHT);
    }
    return i;
}
Copy the code

delete

public void removeVertex(int i){
    int n = this.vertexCount();
    if(i>=0&&i<n){
        this.vertexlist.remove(i);
        for(int j=i+1; j<n; j++){for(int k=0; k<n; k++){this.matrix.set(j-1,k,this.matrix.get(j,k));// The adjacency matrix is one row short}}this.matrix.setRowColumns(n-1,n-1);
    }else throw new IndexOutOfBoundsException("i = "+i);
}
Copy the code

Gets the weights of adjacent vertices and edges

// Get weights
public int weight(int i,int j){
    return this.matrix.get(i,j);// Returns the value in the matrix
}

protected int next(int i,int j){
    int n = this.vertexlistCount();
    if(i>=0&&i<n&&j>=-1&&j<n&&i! =j){// check whether the ring is formed, I is in the matrix, j meets the condition
        for(int k=j+1; k<n; k++){if(this.matrix.get(i,k)! =0&&this.matrix.get(i,k)! =MAX_WEIGHT){returnk; }}}return -1;
}
Copy the code

Adjacency list

implementation

// List storage matrix implementation
public class LinkedMatrix{
	private int rows,columns;
    SeqList<PolySinglyList<Triple>> rowlist;
    public LinkedMatrix(int i,int n){
        if(m>0&&n>0) {this.rows = m;
            this.columns = n;
            this.rowlist = new SeqList<PolySinglyList<Triple>>();
            for(int i=0; i<m; i++){this.rowlist.insert(newPolySinglyList<Triple>>()); }}else throw new IllegalArgunmentException("The number of rows and columns of the matrix cannot be less than zero.");
    }
    public LinkedMatrix(int m){
        this(m,m);
    }
    public LinkedMatrix(int m,int n,Triple[] tris){
        this(m,n);
        for(int i=0; i<this.length; i++){this.set(tri[i]); }}public int getRows(a)
    public int getColumns(a)
    
}
Copy the code

public class AdjListGraph<T> extends AbstractGraph<T>{
	protected LinkedMatrix adjlist;
    public AdjListGtrph(int length){
        super(length);
        this.adjlist = new LinkedMatrix(length,length);
    }
    public AdjListGraph(a){
        this(10);
    }
    public AdjListGraph(T[] vertices){
        this(vertices.length);
        for(int i=0; i<vertices.length; i++){this.insertVertex(vertices[i]); }}public AdjListGraph(T[] vertexlist,Triple[] edges){
        this(vertices);                     // Build a sequential table with array elements
        for(int i=0; i<edges.length; i++){this.insertEdge(edges[i]); }}public String toString(a){}}Copy the code

edge

insert

public void insertEdge(int i,int j,int weight){
	if(i! =j){if(weight<=0||weight>=MAX_WEIGHT){
            weight = 0;
        }
        this.adjlist.set(i,j,weight);
    }else throw new IllegalArgumentException("Not loopable")；
}
public void insertEdge(Triple edge){
    this.insertEdge(edge.getRow(),edge.getColumn(),edge.getValue());
}
Copy the code

delete

public void removeEdge(int i,int j){ if(i! =j){ this.adjlist.set(new Triple(i,j,MAX_WEIGHT)); } } public void removeEdge(Triple edge){ this.removeEdge(edge.getRow(),edge.getColumn(),edge.getValue()); }Copy the code

The vertices

insert

public int insertVertex(T x){
    int i = this.vertexlist.insert(x);
    if(i>=this.adjalist.getRows()){
        this.adjlist.setRowsColumns(i+1,j+1);
    }
    return i;
}
Copy the code

delete

public void removeVertex(int i){
	int n= this.vertexCount();
	if(i>=0&&i<n){
		SortedSinglyList<Triple> link = this.adjlist.rowlist.get(i);
		for(Node<Triple> p=link.head.next; p! =null; p=p.next){this.removeEdge(p.data.toSymmetry());
		}
		n--;
		this.adjlist.remove(i);
		this.adjlist.setRowsColumns(n,n);
		for(int j=0; j<n; j++){ link =this.adjlist.rowlist.get(j);
			for(Node<Triple> p=link; p! =null; p=p.next){if(p.data.row>i){
                    p.data.row--;
                }
                if(p.data.column>i){ p.data.column--; }}}this.vertexlist.remove(i);
	}else throw new IndexOutOfBoundsException("");
}
Copy the code

Get adjacent vertices Get the weights of adjacent vertices and edges

public int weight(int i,int j){
    if(i==j){
        return 0;
    }
    int weight = this.adjlist.get(i,j);
    returnweight! =0? weight:MAX_WEIGHT; }protected int next(int i,int j){
    int n= this.vertexCount();
    if(i>=0&&i<n&&j>=-1&&j<n&&i! =j){ SortedSinglyList<Triple> link =new this.adjlist.rowlist.get(i);
    	Node<Triple> find = link.head.next;
    	if(j==-1) {returnfind! =null? find.data.column:-1;
        }
        find = link.search(new Triple(i,j,0));
        if(find! =null){
            find = find.next;
            if(find! =null) {returnfind.data.column; }}}return -1;
}
Copy the code

traverse

Depth-first search

public void DFSTraverse(int i){
    boolean visited = new boolean[this.vertexCount()];
    int j = i;
    do{
        if(! visited[j]){ System.out.print("{");
            this.depthfs(j,visited);
            System.out.print("}");
        }
        j = (j+1) %this.vertexCount();          // set j from 1 to vertexCOunt() and back to 0
    }while(j! =i) System.out.println(); }private void depthfs(int i,boolean[] visited){
    System.out.println(this.getVertex(i)+"");
    visited[i] =true;
    int j=this.next(i,-1);
    while(j! =i){if(! visited[j]){ depthfs(j,visited);// Recursively accesses the adjacent vertices of this vertex
        }
        j = this.next(i,j); }}Copy the code

Breadth-first search

public void BFSTraverse(int i) {
		boolean[] visited = new boolean[this.vertexCount()];
		int j = i;
		do {
			if(! visited[j]) { System.out.print("{");
				breadthfs(j,visited);
				System.out.print("}");
			}
			j = (j+1) %this.vertexCount(); 
		}while(j! =i); System.out.println(); }private void breadthfs(int i, boolean[] visited) {
		System.out.print(vertexlist.get(i)+"");
		visited[i] = true;
		SeqQuene<Integer> que = new SeqQuene<Integer>();
		que.add(i);
		while(! que.isEmpty()) { i = que.poll();for(int j=0; j<adjaMatrix.getColumns(); j++) {if(adjaMatrix.get(i,j)! =0&&adjaMatrix.get(i, j)! =Integer.MAX_VALUE&&! visited[j]) { System.out.print(vertexlist.get(i)+"");
					visited[j] = true; que.add(j); }}}}Copy the code

Minimum spanning tree

Prim algorithm

/* Take the selected vertices as a set, select the edge with the least weight for the set to join the node to add to the set */
public void minSpanTree(a) {
		Triple[] mst= new Triple[vertexCount()-1];
		for (int i=0; i<mst.length; i++) { mst[i] =new Triple(0,i+1.this.weight(0,i+1));
		}
		for (int i=0; i<mst.length; i++) {int minweight = mst[i].value, min=i;
			 for (int j=i+1; j<mst.length; j++) {if(mst[j].value<minweight) {
					 minweight=mst[j].value;
					 min = j;
				 }
			 }
			 Triple edge = mst[min];
			 mst[min]=mst[i];
			 mst[i] = edge;
			 int tv=edge.column;
			 for(int j=i+1; j<mst.length; j++) {int v=mst[j].column;
				 int weight=this.weight(tv,v);
				 if(weight<mst[j].value){
					 mst[j]=new Triple(tv, v, weight);
				 }
			 }
		}
		System.out.print("\n Minimum spanning tree edge set:");
		int mincost=0;
		for (int i=0; i<mst.length; i++) {
			 System.out. print(mst[i]+"");

			 mincost += mst[i].value;

			 System.out.println(", the minimum cost is:+mincost); }}Copy the code

Kruskal algorithm

import java.until.Comparator
public class MinSpanTree{
    private Triple[] mst;
    private int cost = 0;
    public MinSpanTree(int n,Triple[] edge,Comparator<Triple> empr){
        this.mst = new Triple[n-1];
        Heap<Triple> minheap = new Heap<Triple>(true, edges, empr); UnionFindSet ufset =new UnionFindSet(n);
        System.out.println("And search set :"+ufset.toString()+"");
        int i=0;
        for(int j=0; j<n; j++){ Triple minedge = minheap.removeRoot(); System.out.print("Minimum edge"+minedge.toString());
        	if(ufset.union(minedge.row,minedge.column)){
                this.mst[i++]=minedge;
                this.cost += minedge.value;
                System.out.println("Insert edge:"+minedge.toString()+""); }}}public String toString(a);
    private static void print(boolean table[])
}
Copy the code

The shortest path

Dijkstra algorithm

/* The previous array S dist */

Copy the code

Floyd algorithm

The tree

A tree is a finite set of n nodes. Trees with n=0 are called empty trees

There is a special node called the root node, which has only successors and no predecessors
Other nodes except the root node are divided into m disjoint sets T0, T1,…… Tm-1 also has a tree structure, that is, a subtree of the root

The term

Parent, child, sibling

The root node of a knot tree is called its child
This node is the parent of its child node
Multiple nodes that share the same parent are called brothers

The degree of

The number of subtrees that a node has

Node hierarchy, tree height

The node’s hierarchy is the node’s hierarchy position in the tree, and the convention is that the root node’s hierarchy is 1 and the other levels are the parent node’s hierarchy plus 1

The height or depth of a tree is the maximum number of levels of nodes in the tree

Edge, path, diameter

An ordered pair connecting two nodes is an edge

An ordered set of pairs from one node to another

The ordered logarithm is the path length

Binary tree

The nature of the

If the root node level is 1, there are at most 2^(i-1) nodes at the I level of the binary tree (induction proof).
In a binary tree of height H, there are at most 2^h^-1 nodes
The number of leaves is n0, the number of nodes of 2 degrees is n2, n0=n2+ 1
- Complete binary tree: a binary tree with 2^ H ^-1 nodes
- Full binary tree: a binary tree with n nodes of height H. It is a complete binary tree if every node corresponds to node 0~n-1 in full binary tree of height H
A complete binary tree with n nodes whose height h == =[log2N +] integer = = + 1 (< h – 1 log2(n+1)=<h)
A complete binary tree with n nodes, for nodes numbered I
- If I =0, I is the root node and has no parent node. If I >0, the serial number of parent node of I is == (i-1) /2== rounded
- If 2i+1
- If 2i+2 is less than n, the node number of the right child of I is 2i+2; otherwise, I has no right child

traverse

Children first

The root first order

Access the root node, traverse the left subtree, traverse the right subtree
Root in order

Traverse the left subtree, access the root, traverse the right subtree
After the root order

Walk through the left subtree, walk through the right subtree, access the root

Brother is preferred

Each layer accesses the nodes of the same layer from left to right, and then enters the next node

implementation

ADT BinaryTree<T>{
	boolean isEmpty(a)
    int size(a)
    int height(a)
    void predrder(a)
    void inorder(a)
    void postorder(a)
    void levelorder(a)
    BinaryNode<T> insert(T x)
    BinaryNode<T> insert(BinaryNode<T> p,boolean leftChild)
    void remove(Binary<T> parent,boolean leftChild)
    void clear(a)
    BinaryNode<T> search(T key)
    boolean contains(T key)
    int level(T key)
}
Copy the code

Sequential storage structure

The sequential storage structure cannot reflect the data relationships of binary trees

Incomplete binary trees cannot adopt sequential storage structure

Chain storage structure

/ / node class
public class BinaryNode<T>{
    public T data;
    public BinaryNode<T> left,right;
    public BinaryNode(T data,BinaryNode<T> left,){
        this.data = data;
        this.left = left;
        this.right = right;
    }
    public BinaryNode(T data){
        this(data,null.null);
    }
    public String toString(a){
        return this.data.toString();
    }
    public boolean isLeaf(a){
        return this.left==null&&this.right==null; }}Copy the code

// Binary tree class
public Class BinaryTree<T>{
    public BinaryNode<T> root;
    public BinaryTree(a){
        this.root = null;
    }
    public boolean isEmpty(a){
        return this.root==null;
    }
   
    // Insert node
    public BinaryNode<T> insert(T x){
        return this.root = new BinaryNode<T>(x,this.root,null);
    }
    public BinaryNode<T> insert(BinaryNode<T> parent,T x,boolean leftChild){
        if(x==null) {return null;
        }
        if(leftChild){
            return parent.left = new BinaryNode<T>(x,parent,null);
        }else{
            return parent.right = new BinaryNode<T>(x,null,parent); }}public void remove(BinaryNode<T> parent,boolean leftChild){
        if(leftChild){
            parent.left = null;
        }else{
            parent.right = null; }}public void clear(a){
        this.root = null;
    }
    // order traversal first
    public void proorder(a){
        preorder(this.root);
        System.out.println();
        
    }
    private void preorder(BinaryNode<T> p){
        if(p! =null){
            System.out.print(p.data.toString()+""); preorder(p.left); preorder(p.right); }}//
    public String toString(a){
        return toString(this.root);
    }
    private String toString(BinaryNode<T> p){
        if(p==null) {return "^";
        }
        return p.data.toString()+""+toString(p.left)+""+toString(p.right); }}Copy the code

// Build a binary tree

Copy the code

Level traversal

Copy the code

Non-recursive sequential traversal

Copy the code

Cue binary tree

To find the

Average search length ASL= summation (p I *c I)

P I search probability

C I number of lookups

In order to find

Based on the ergodic algorithm, one by one comparison

ASL success

(n + 1) / 2

ASL is not successful

Binary search

Sequential storage
Data element sorting

The complexity of the

log2n

Index Indicates the block index of the table

hash

Binary sort tree

Balanced binary trees

The sorting

Insertion sort

Directly inserted into the

describe

Sorted and unsorted subsequences are set

You start with the whole sequence in the unsorted sequence, you keep picking the elements in the unsorted sequence, you put them in the sorted sequence, and you end up with the elements in the sorted sequence

Analysis of the

Let’s say we have n elements, and we need to do it n minus 1 times, and the number of comparisons and moves depends on the initial permutation

In the best case, the sequence is sorted, the number of comparisons is n-1, the number of moves is (2n-1) and the time complexity is O(n).

In the worst case, the sequence is completely reversed, I inserts compare I times, move I +2 times, order n^2^.

stable

implementation

public class Array{
    public static void insertSort(int[] key){
        for(int i=0; I < key. Length; i++){int temp  = key[i];
            for(int j=0; j>=0&&temp<key[j]; j++){ key[j+1] = key[j];
            }
            key[j+1] = temp; }}}Copy the code

Hill sorting

describe

Group elements separated by a certain distance (increment) in a sequence and sort them directly

The initial increment is typically half the length of the sequence, and each subsequent increment is halved, ending with 1

The elements in the group are incremented and sorted

Analysis of the

Three layers of cyclic implementation

The outermost loop changes delta for scanning

The inner two layers implement direct insertion

implementation

public class shellSort(int[] keys){
    for(int delta = keys.length/2; delta>0; delta/=2) {for(inti = delta; i<keys.length; i++){int temp = key[i];
            for(intj=i-delta; j>=0&&temp<key[j]; j-=delta){ keys[j+delta] = key[j]; } keys[j+delta] = temp; }}}Copy the code

Exchange sort

Bubble sort

describe

Compare two adjacent elements and swap if they are in reverse order

Analysis of the

In the best case, sequence sorting, only one scan, order n time.

In the worst case, the sequence is in reverse order, order n^2^.

implementation

private static void swap(int[] keys,int i,int j){
    int temp= key[j];
    key[j] = key[i];
    key[i] = temp;
}
public static void bubbkeSort(int[] keys){
    bubbleSort(keys,true);
}
public static void bubbleSort(int[] keys,boolean asc){
    boolean exchange = true;
    for(int i=0; i<keys.length&&exchange; i++){ exchange =false;
        for(int j=0; j<keys.length-i; j++){if(asc? keys[j]>keys[j+1]:keys[j]<keys[j+1]){
                swaq(keys,j,j+1);
                exchange = true; }}}}Copy the code

Quick sort

describe

An element in the sequence is selected as the base value, and each trip starts from both ends of the sequence. The elements less than the base value are swapped to the front end of the sequence, and the elements greater than the base value are swapped to the back end of the sequence

implementation

public static void quickSort(int[] keys){
    quickSort(keys,0,keys.length-1);
}
private static void quickSort(int[] keys,int begin,int end){
    if(begin>=0&&begin<keys.length&&end>=0&&end<keys.length&&begin<end){
        int i =begin,j=end;
        int vot= keys[i];
        while(i! =j){while(i<j&&keys[i]>=vot){
                j--;
            }
            if(i<j){
                keys[i++] =keys[i];
            }
            while(i<j&&keys[i]<=vot){
                i++;
            }
            if(i<j){
                keys][j--] = keys[i];
        }
        keys[i] = vot;
        quickSort(keys,beging,j-1);
        quickSort(keys,i+1,end); }}Copy the code

Analysis of the

In the best case, each sequence is divided into two similar sub-sequences, O(n*log 2 n)

In the worst case, each run splits the sequence into two subsequences of very different lengths, O(n^2^).

Selection sort

Direct selection sort

describe

Select the smallest element out of n and place it in the first position

implementation

public static void SelectSort(int[] keys){
    for(int i=0; i<keys.length; i++){int min = i;
        for(int j= i+1; j<keys.length; j++){if(keys[j]<keys[min]){
                min = j;
            }
            if(min! =i){ swaq(keys,i,j); }}}}Copy the code

Analysis of the

The ith run is n- I, the number of moves is related to the initial sort, and the time complexity is O(n^2^).

Heap sort

describe

Using the structure of binary tree, the sequence is stored in binary tree structure and sorted to form the maximum/minimum heap

implementation

public static void heapSort(int[] keys){
    heapSort(keys,true);
}
public static void heapSort(int[] keys,boolean minheap){
    for(int i=keys.length/2; i>=0; i--){ sift(keys,i,keys.length-1,minheap);
    }
    for(inti=keys.length; i>0; i--){ swaq(keys,0.1);
        sift(keys,0,i-1,minheap); }}private static void sift(int[] keys,int parent,int end,boolean minheap){
    int child = 2*parent+1;
    int value = keys[parent];
    while(child<=end){
        if(child<end&&(minheap? keys[child]>keys[child+1]:keys[child]<keys[child+1])){
            child++;
        }
        if(minheap? value>keys[child]:value<keys[child]){ keys[parent] = keys[child]; parent = child; child =2*parent+1;
        }else{
            break; } keys[parent] = value; print(keys); }}Copy the code

Merge sort

describe

The idea of divide and conquer is to divide the unsorted sequence into several groups of sub-sequences and then merge the sub-sequences

implementation

private static void merge(int[] x,int[] y,int begin1,int begin2,int n){
    int i = begin1,j = begin2,k = begin1;
    while(i<begin1+n&&j<begin2+n&&j<x.length){
        if(x[i]<x[j]){
            y[k++] = x[i++];
            
        }else{
            y[k++] = x[j++];
        }
        while(j<begin1+n&&i<x.length){
            y[k++] = x[i++];
        }
        while(j<begin2&&j<x.length){ y[k++] = x[j++]; }}}private static void mergepass(int[] x,int[] y,int n){
    for(int i=0; i<x.length; i+=2*n){ merge(x,y,i,i+n,n); }}public static void mergeSort(int[] x){
    int[] y = new int[x.length];
    int n = 1;
    while(n<x.length){
        mergepass(x,y,n);
        n*=2;
        if(n<x.length){
            mergepass(y,x,n);
            n*=2; }}}Copy the code

Analysis of the

Time order n log two n, space order n.

Merge sort is stable

Java data structure notes

The data structure

The physical structure

Sequential storage structure

implementation

Chain storage structure

implementation

Logical structure

Linear structure

The characteristics of

implementation

Sequential storage structure

An array of

The complexity of the

Chain storage structure

string

The stack and queue

The stack

Features:

implementation

Sequential storage structure

Chain storage structure

application

The queue

Features:

implementation

Sequential storage structure

Arrays and generalized tables

figure

Undirected graph

Directed graph

Complete graph

Undirected graph

Directed graph

Weighted graph

Adjacent vertices

The degree of

subgraph

connectivity

The path

implementation

Matrix class

Adjacency matrix

edge

The vertices

Adjacency list

implementation

edge

The vertices

traverse

Depth-first search

Breadth-first search

Minimum spanning tree

Prim algorithm

Kruskal algorithm

The shortest path

Dijkstra algorithm

Floyd algorithm

The tree

The term

Parent, child, sibling

The degree of

Node hierarchy, tree height

Edge, path, diameter

Binary tree

The nature of the

traverse

Children first

Brother is preferred

implementation

Sequential storage structure

Chain storage structure

Cue binary tree

To find the

In order to find

ASL success

ASL is not successful

Binary search

The complexity of the

Index Indicates the block index of the table