Data structure and algorithm architecture summarized by a god on the Internet.

I. Time complexity and space complexity

1. What are time complexity and space complexity

How to distinguish the good from the bad of an algorithm, if implemented in the program, will be interfered by various factors, so the concept of time complexity and space complexity is introduced.

The time complexity is whether the algorithm is fast, and the space complexity is whether the algorithm is consuming space.

The asymptotic time complexity of the algorithm is T(n) = O(F(n))——> large O notation.

2. Time complexity

Let’s say we’re going to run this algorithm many times, so what’s the expression for it? Take the highest degree term.

  • For example, the most basic line of code is O (1);
  • If an algorithm computes the same amount of time, it must take longer and longer the more times it does it, and it grows linearly. For example, it takes 1 minute to eat a drumstick every time it executes it n times, so its time complexity is O (n);
  • If you take the sum from 1 to 100, the expression is (1 + n) * n/2- > which is 0.5n² + 0.5n, ignoring n to the first power, so the time complexity is order (n²).
  • If you take a piece of string that’s 16 centimeters, and you cut half of it each time, how long does it take to leave one centimeter, then you’re going to have to use the logarithm, which is order log base 16.

3. Spatial complexity

Space complexity does not need to be understood too deeply, but it is not a description of how much memory is occupied, but rather a comparison of memory changes.

  • Let’s say I have a variable that’s equal to 1, and I assign it plus and plus every time, and it’s the same variable, but I keep assigning, and it doesn’t change, so it’s still 1
  • A for loop, for example, creates a new variable each time, making sure its space complexity is N
  • If it’s a two-dimensional array, and it’s assigned by a double-layer for loop, it’s n ^ 2

Second, the array

1, the introduction

An array is one of the most basic data structures. It can store a finite number of elements (fixed length) and can be added, deleted, modified, or queried

2. Code implementation

public class MyArray {
    // Define an array
    int[] elements;

    // Initialize the array
    public MyArray(a){
        elements = new int[0];
    }

    // Get the length of the array
    public int size(a){
        return elements.length;
    }

    // Add an element to the end of the array
    public void add(int ele){
        int[] newArr = new int[elements.length + 1];
        for (int i = 0; i < elements.length; i++){ newArr[i] = elements[i]; } newArr[elements.length] = ele; elements = newArr; }// The method of traversing a number group
    public void arrayShow(a){
        System.out.println(Arrays.toString(elements));
    }

    // Delete an element
    public void delete(int index){
        if (index < 0 || index > elements.length - 1) {throw new RuntimeException("Incorrect incoming subscript");
        }
        int[] newArr = new int[elements.length - 1];
        for (int i = 0; i < newArr.length; i++){if (i < index){
                newArr[i] = elements[i];
            }else{
                newArr[i] = elements[i + 1];
            }
        }
        elements = newArr;
    }

    // Retrieves the element at the specified position
    public int get(int index){
        if (index < 0 || index > elements.length -1) {throw new RuntimeException("Incorrect incoming subscript cannot read element");
        }
        return elements[index];
    }

    // Insert an element to the specified position
    public void insert(int index,int ele){
        int[] newArr = new int[elements.length + 1];
        for (int i = 0; i < newArr.length; i++){if (i < index){
                newArr[i] = elements[i];
            }else{
                newArr[i + 1] = elements[i]; }}// Insert a new element
        newArr[index] = ele;
        // Replace the array
        elements = newArr;
    }

    // Replace one of the elements
    public void update(int index,int ele){
        if (index < 0 || index > elements.length - 1) {throw new RuntimeException("Incorrect subscript passed in, cannot modify array");
        }
        elements[index] = ele;
    }

    // Linear search
    public int search(int target){
        for (int i = 0; i < elements.length; i++){if (elements[i] == target){
                returni; }}// No corresponding element was found
        return -1; }}Copy the code

Test array:

public class TestMyArray {
    public static void main(String[] args) {
        MyArray myArray = new MyArray();
        myArray.add(2);
        myArray.add(11);
        myArray.add(15);
        myArray.add(7);
        myArray.add(14);
        myArray.add(3);
        myArray.add(8);
        myArray.delete(2); myArray.arrayShow(); }}Copy the code

Third, the queue

1, the introduction

  • A queue is an ordered list that can be implemented as an array or a linked list.
  • Follow the first-in, first-out principle. That is, data stored in the queue must be retrieved first. What is put in later is taken out later

2. Code implementation

public class MyQueue {
    // Create an array
    int[] elements;

    // constructor
    public MyQueue(a){
        elements = new int[0];
    }

    // Add elements to the queue
    public void addQueue(int ele){
        int[] newArr = new int[elements.length + 1];
        for (int i = 0; i < elements.length; i++){ newArr[i] = elements[i]; } newArr[elements.length] = ele; elements = newArr; }// Fetch the element from the queue
    public int getQueue(a){
        int ele = elements[0];
        int[] newArr = new int[elements.length - 1];
        for (int i = 0; i < newArr.length; i++){ newArr[i] = elements[i +1];
        }
        elements = newArr;
        return ele;
    }

    // Check whether the queue is empty
    public boolean isEmpty(a){
        return elements.length == 0;
    }

    // Query all elements
    public void show(a){
        for (int i = 0; i < elements.length; i++){ System.out.println("Current queue no." + (i + 1) + The elements are:+ elements[i]); }}}Copy the code

The test.

public class TestMyQueue {
    public static void main(String[] args) {
        MyQueue mq = new MyQueue();
        System.out.println("Is the queue empty :" + mq.isEmpty());
        mq.addQueue(10);
        System.out.println("Is the queue empty :" + mq.isEmpty());
        mq.addQueue(12);
        mq.addQueue(8);
        mq.addQueue(15);
        mq.addQueue(22);
        mq.addQueue(113); mq.show(); }}Copy the code

Fourth, the linked list

1, the introduction

  • Linked lists are stored in the form of nodes
  • Each node contains the data field, and the next field: points to the next node.
  • The nodes of a linked list are not necessarily stored consecutively.

2, one-way linked list code implementation

public class SingleLinkedListDemo {

	public static void main(String[] args) {
		// Test
		// Create a node first
		HeroNode hero1 = new HeroNode(1."Sung river"."Timely rain");
		HeroNode hero2 = new HeroNode(2."Junyi Lu"."Jade Unicorn");
		HeroNode hero3 = new HeroNode(3."吴用"."Resourceful");
		HeroNode hero4 = new HeroNode(4."Lin"."Leopard head");
		
		// Create a linked list
		SingleLinkedList singleLinkedList = new SingleLinkedList();
		
		
		/ / to join
		singleLinkedList.add(hero1);
		singleLinkedList.add(hero4);
		singleLinkedList.add(hero2);
		singleLinkedList.add(hero3);

		// Test the reverse of a single list
		System.out.println("What happened to the original linked list?");
		singleLinkedList.list();
		
// system.out. println(" reverse single list ~~");
// reversetList(singleLinkedList.getHead());
// singleLinkedList.list();
		
		System.out.println("Test printing single linked list in reverse order without changing the structure of the list ~~");
		reversePrint(singleLinkedList.getHead());
		
/ * / / to join in the order number singleLinkedList addByOrder (hero1); singleLinkedList.addByOrder(hero4); singleLinkedList.addByOrder(hero2); singleLinkedList.addByOrder(hero3); // Display a singLelinkedList.list (); HeroNode newHeroNode = newHeroNode (2, "little "," yuqilin ~~"); singleLinkedList.update(newHeroNode); System.out.println(" modified list condition ~~"); singleLinkedList.list(); Singlelinkedlist.del (1); singleLinkedList.del(4); System.out.println(" delete list status ~~"); singleLinkedList.list(); System.out.println(" count of valid nodes =" + getLength(singLelinkedList.gethead ())); HeroNode res = findLastIndexNode(singLelinkedList.gethead (), 3); HeroNode res = findLastIndexNode(singLelinkedList.gethead (), 3); System.out.println("res=" + res); * /		
		
	}
	
	// Method 2:
	// You can use the stack data structure to push each node into the stack, and then use the characteristics of the stack first out, to achieve the effect of reverse printing
	public static void reversePrint(HeroNode head) {
		if(head.next == null) {
			return;// Empty linked list cannot be printed
		}
		// create a stack to push each node onto the stack
		Stack<HeroNode> stack = new Stack<HeroNode>();
		HeroNode cur = head.next;
		// Push all nodes of the linked list onto the stack
		while(cur ! =null) {
			stack.push(cur);
			cur = cur.next; //cur moves back so that it can be pressed into the next node
		}
		// Print the nodes in the stack and pop them off the stack
		while (stack.size() > 0) {
			System.out.println(stack.pop()); // Stack is characterized by first in, last out}}// Reverse the singly linked list
	public static void reversetList(HeroNode head) {
		// If the current list is empty, or there is only one node, no need to reverse, directly return
		if(head.next == null || head.next.next == null) {
			return ;
		}
		
		// Define an auxiliary pointer (variable) to help us traverse the original list
		HeroNode cur = head.next;
		HeroNode next = null;// Indicates the next node of the current node [cur]
		HeroNode reverseHead = new HeroNode(0.""."");
		// Iterate over the old list, each time a node is iterated, it is removed and placed at the top of the new list reverseHead
		/ / think
		while(cur ! =null) { 
			next = cur.next;// Save the next node of the current node temporarily, because it will be used later
			cur.next = reverseHead.next;// Point the next node of cur to the very front of the new list
			reverseHead.next = cur; // Connect cur to the new linked list
			cur = next;// make cur come back
		}
		// Point head.next to reversehead. next to reverse a single list
		head.next = reverseHead.next;
	}
	
	// Select the KTH node from the end of the list.
	/ / way of thinking
	//1. Write a method that receives a head node and an index
	//2. index indicates the penultimate index node
	//3. Run the list from start to end to get the total length getLength
	//4. Select * from the list where size = 1; //4
	//5. Nulll is returned otherwise
	public static HeroNode findLastIndexNode(HeroNode head, int index) {
		// If the list is empty, return null
		if(head.next == null) {
			return null;// Not found
		}
		// First traversal to get the length of the list (node number)
		int size = getLength(head);
		// The second time through the size-index position, is our reciprocal KTH node
		// Check index
		if(index <=0 || index > size) {
			return null; 
		}
		// Define an auxiliary variable, and position the for loop to the reciprocal index
		HeroNode cur = head.next; //3 //3-1 = 2
		for(int i =0; i< size - index; i++) {
			cur = cur.next;
		}
		return cur;
		
	}
	
	// Method: obtain the number of nodes in the single linked list (if the linked list is the head node, do not count the head node)
	/ * * * *@paramHead The head node * of the linked list@returnThis returns the number of valid nodes */
	public static int getLength(HeroNode head) {
		if(head.next == null) { / / an empty list
			return 0;
		}
		int length = 0;
		// Define a secondary variable, where we do not count the head node
		HeroNode cur = head.next;
		while(cur ! =null) {
			length++;
			cur = cur.next; / / traverse
		}
		returnlength; }}// Define SingleLinkedList to manage our heroes
class SingleLinkedList {
	// Initialize a header node, do not move the header node, do not store specific data
	private HeroNode head = new HeroNode(0.""."");
	
	
	// return the head node
	public HeroNode getHead(a) {
		return head;
	}

	// Add a node to the unidirectional list
	// when the number is not in order
	//1. Find the last node of the current list
	//2. Point next of the last node to the new node
	public void add(HeroNode heroNode) {
		
		// Since the head node cannot move, we need an auxiliary traversal of temp
		HeroNode temp = head;
		// Run through the list to find the end
		while(true) {
			// Find the end of the list
			if(temp.next == null) {//
				break;
			}
			// If the end is not found, temp will be moved back
			temp = temp.next;
		}
		// When exiting the while loop, temp points to the end of the list
		// Next of the last node points to the new node
		temp.next = heroNode;
	}
	
	// The second way to add a hero is to insert the hero into the specified position according to the ranking
	//(If there is a ranking, add failure, and give a hint)
	public void addByOrder(HeroNode heroNode) {
		// Since the head node cannot move, we still use an auxiliary pointer (variable) to help find the location to add
		// Because of the singly linked list, because we are looking for the temp node before the add position, otherwise we cannot insert
		HeroNode temp = head;
		boolean flag = false; // flag Indicates whether the added number exists. The default value is false
		while(true) {
			if(temp.next == null) {Temp is already at the end of the list
				break; //
			} 
			if(temp.next.no > heroNode.no) { // Find the position, just after temp
				break;
			} else if (temp.next.no == heroNode.no) {// Indicates that the number of the heroNode to be added already exists
				
				flag = true; // Indicates that the number exists
				break;
			}
			temp = temp.next; // Move back to iterate over the current list
		}
		// Determine the value of flag
		if(flag) { // If the id cannot be added, the id exists
			System.out.printf("Insert hero number %d already exists, cannot join \n", heroNode.no);
		} else {
			// Insert into the linked list, after tempheroNode.next = temp.next; temp.next = heroNode; }}// Modify the node information according to the NO number, that is, the NO number cannot be changed.
	/ / that
	//1. Modify newHeroNode's no
	public void update(HeroNode newHeroNode) {
		// Check whether it is null
		if(head.next == null) {
			System.out.println("Linked list is empty ~");
			return;
		}
		// Find the node to be modified according to the no number
		// Define an auxiliary variable
		HeroNode temp = head.next;
		boolean flag = false; // Indicates whether the node is found
		while(true) {
			if (temp == null) {
				break; // The list has been traversed
			}
			if(temp.no == newHeroNode.no) {
				/ / find
				flag = true;
				break;
			}
			temp = temp.next;
		}
		// Check whether the node to be modified is found according to flag
		if(flag) {
			temp.name = newHeroNode.name;
			temp.nickname = newHeroNode.nickname;
		} else { // Not found
			System.out.printf("No node with number %d found, cannot modify \n", newHeroNode.no); }}// Delete a node
	/ / way of thinking
	//1. Head cannot move, so we need a temp secondary node to find the node before the node to be deleted
	//2. We compare temp.next. No with no of the node to be deleted
	public void del(int no) {
		HeroNode temp = head;
		boolean flag = false; // Indicates whether the node to be deleted is found
		while(true) {
			if(temp.next == null) { // We are at the end of the list
				break;
			}
			if(temp.next.no == no) {
				// Temp is the previous node of the node to be deleted
				flag = true;
				break;
			}
			temp = temp.next; // Temp moves back to traverse
		}
		/ / determine flag
		if(flag) { / / find
			// It can be deleted
			temp.next = temp.next.next;
		}else {
			System.out.printf("The %d node to be deleted does not exist \n", no); }}// Display the list
	public void list(a) {
		// Check whether the list is empty
		if(head.next == null) {
			System.out.println("Linked list is empty");
			return;
		}
		// Since the head node cannot move, we need an auxiliary variable to traverse
		HeroNode temp = head.next;
		while(true) {
			// Determine whether to reach the end of the list
			if(temp == null) {
				break;
			}
			// Outputs node information
			System.out.println(temp);
			// Move temp back carefullytemp = temp.next; }}}// Define HeroNode, where each HeroNode object is a node
class HeroNode {
	public int no;
	public String name;
	public String nickname;
	public HeroNode next; // point to the next node
	/ / the constructor
	public HeroNode(int no, String name, String nickname) {
		this.no = no;
		this.name = name;
		this.nickname = nickname;
	}
	// To display the method, we re-toString
	@Override
	public String toString(a) {
		return "HeroNode [no=" + no + ", name=" + name + ", nickname=" + nickname + "]"; }}Copy the code

3, bidirectional linked list code implementation

public class DoubleLinkedListDemo {

	public static void main(String[] args) {
		/ / test
		System.out.println("Tests for bidirectional linked lists");
		// Create a node first
		HeroNode2 hero1 = new HeroNode2(1."Sung river"."Timely rain");
		HeroNode2 hero2 = new HeroNode2(2."Junyi Lu"."Jade Unicorn");
		HeroNode2 hero3 = new HeroNode2(3."吴用"."Resourceful");
		HeroNode2 hero4 = new HeroNode2(4."Lin"."Leopard head");
		// Create a bidirectional list
		DoubleLinkedList doubleLinkedList = new DoubleLinkedList();
		doubleLinkedList.add(hero1);
		doubleLinkedList.add(hero2);
		doubleLinkedList.add(hero3);
		doubleLinkedList.add(hero4);
		
		doubleLinkedList.list();
		
		/ / modify
		HeroNode2 newHeroNode = new HeroNode2(4."Gongsun Sheng"."Enter the Cloud Dragon");
		doubleLinkedList.update(newHeroNode);
		System.out.println("Modified linked list condition");
		doubleLinkedList.list();
		
		/ / delete
		doubleLinkedList.del(3);
		System.out.println("Deleted linked list situation ~~"); doubleLinkedList.list(); }}// Create a bidirectional list class
class DoubleLinkedList {

	// Initialize a header node, do not move the header node, do not store specific data
	private HeroNode2 head = new HeroNode2(0.""."");

	// return the head node
	public HeroNode2 getHead(a) {
		return head;
	}

	// The method of traversing the bidirectional list
	// Display the list
	public void list(a) {
		// Check whether the list is empty
		if (head.next == null) {
			System.out.println("Linked list is empty");
			return;
		}
		// Since the head node cannot move, we need an auxiliary variable to traverse
		HeroNode2 temp = head.next;
		while (true) {
			// Determine whether to reach the end of the list
			if (temp == null) {
				break;
			}
			// Outputs node information
			System.out.println(temp);
			// Move temp back carefullytemp = temp.next; }}// Add a node to the end of the bidirectional list.
	public void add(HeroNode2 heroNode) {

		// Since the head node cannot move, we need an auxiliary traversal of temp
		HeroNode2 temp = head;
		// Run through the list to find the end
		while (true) {
			// Find the end of the list
			if (temp.next == null) {//
				break;
			}
			// If the end is not found, temp will be moved back
			temp = temp.next;
		}
		// When exiting the while loop, temp points to the end of the list
		// Form a bidirectional linked list
		temp.next = heroNode;
		heroNode.pre = temp;
	}

	// Modify the contents of a node
	// Change the node type to HeroNode2
	public void update(HeroNode2 newHeroNode) {
		// Check whether it is null
		if (head.next == null) {
			System.out.println("Linked list is empty ~");
			return;
		}
		// Find the node to be modified according to the no number
		// Define an auxiliary variable
		HeroNode2 temp = head.next;
		boolean flag = false; // Indicates whether the node is found
		while (true) {
			if (temp == null) {
				break; // The list has been traversed
			}
			if (temp.no == newHeroNode.no) {
				/ / find
				flag = true;
				break;
			}
			temp = temp.next;
		}
		// Check whether the node to be modified is found according to flag
		if (flag) {
			temp.name = newHeroNode.name;
			temp.nickname = newHeroNode.nickname;
		} else { // Not found
			System.out.printf("No node with number %d found, cannot modify \n", newHeroNode.no); }}// Remove a node from the bidirectional list,
	/ / that
	// 1 For bidirectional lists, we can find the node to delete directly
	// 2
	public void del(int no) {

		// Check whether the current list is empty
		if (head.next == null) {/ / an empty list
			System.out.println("Linked list is empty and cannot be deleted");
			return;
		}

		HeroNode2 temp = head.next; // Auxiliary variable (pointer)
		boolean flag = false; // Indicates whether the node to be deleted is found
		while (true) {
			if (temp == null) { // We are at the end of the list
				break;
			}
			if (temp.no == no) {
				// Temp is the previous node of the node to be deleted
				flag = true;
				break;
			}
			temp = temp.next; // Temp moves back to traverse
		}
		/ / determine flag
		if (flag) { / / find
			// It can be deleted
			// temp.next = temp.next.next; [One-way linked list]
			temp.pre.next = temp.next;
			// Is there a problem with our code?
			// If it is the last node, there is no need to execute the following statement, otherwise a null pointer will appear
			if(temp.next ! =null) { temp.next.pre = temp.pre; }}else {
			System.out.printf("The %d node to be deleted does not exist \n", no); }}}// Define HeroNode2, where each HeroNode object is a node
class HeroNode2 {
	public int no;
	public String name;
	public String nickname;
	public HeroNode2 next; // Points to the next node, default is null
	public HeroNode2 pre; // Points to the previous node, null by default
	/ / the constructor

	public HeroNode2(int no, String name, String nickname) {
		this.no = no;
		this.name = name;
		this.nickname = nickname;
	}

	// To display the method, we re-toString
	@Override
	public String toString(a) {
		return "HeroNode [no=" + no + ", name=" + name + ", nickname=" + nickname + "]"; }}Copy the code

Five, the stack

1, the introduction

  • A stack is a filo-first In Last Out ordered list.

  • A stack is a special kind of linear table that limits the insertion and deletion of elements to the same end of the linear table. The end that allows insertion and deletion is the change end

    It is called the Top of the stack, and the other end is the fixed end, called the Bottom of the stack.

  • According to the definition of the stack, the first element to be added to the stack is at the bottom of the stack, and the last element to be added is at the top of the stack

2. Code implementation

public class MyStack {
    // Use arrays to store stacks
    private int[] elements;

    // constructor
    public MyStack(a){
        elements = new int[0];
    }

    // Get the array length
    public int size(a){
        return elements.length;
    }

    // Press the element
    public void push(int ele){
        // Create a new array
        int[] newArr = new int[elements.length + 1];
        // Add the original array element to the new array
        for (int i = 0; i < elements.length; i++){ newArr[i] = elements[i]; }// Add new elements to the new array
        newArr[elements.length] = ele;
        // Assign the new array to the old array
        elements = newArr;
    }

    // Fetch the top element of the stack
    public int pop(a){
        // throw an exception if the stack is empty
        if (elements.length == 0) {throw new RuntimeException("No data in stack, cannot pop element");
        }
        // Create an array
        int[] newArr = new int[elements.length - 1];
        // Put the element into the new array
        for (int i = 0; i < newArr.length; i++){ newArr[i] = elements[i]; }// Get the top element of the stack
        int ele = elements[elements.length - 1];
        // Assign to the original array
        elements = newArr;
        // Return the top element of the stack
        return ele;
    }

    // View the top element of the stack
    public int showPeek(a){
        // throw an exception if the stack is empty
        if (elements.length == 0) {throw new RuntimeException("No data in stack, cannot view top element");
        }
        return elements[elements.length - 1];
    }

    // Check whether the stack is empty
    public boolean isEmpty(a){
        return elements.length == 0; }}Copy the code

The test.

public class TestMyStack {
    public static void main(String[] args) {
        MyStack myStack = new MyStack();
        myStack.push(10);
        myStack.push(20);
        myStack.push(30); System.out.println(myStack.isEmpty()); System.out.println(myStack.showPeek()); System.out.println(myStack.pop()); System.out.println(myStack.showPeek()); System.out.println(myStack.pop()); System.out.println(myStack.showPeek()); System.out.println(myStack.pop()); System.out.println(myStack.isEmpty()); }}Copy the code

Sixth, the recursion

1, the introduction

Recursion is when a method calls itself, passing in a different variable each time. Recursion helps programmers solve complex problems while keeping code simple.

2. Common code implementation

public class TestRecursive {
    public static void main(String[] args) {
        show(10);
    }

    public static void show(int i){
        if (i > 0){ System.out.println(i); show(--i); }}}Copy the code

3. Realization of hannotta problem

public class TestHanoi {
    public static void main(String[] args) {
        hanoi(3.'A'.'B'.'C');
    }

    /** * Hannotta completes logic *@paramN There are several plates *@paramStart Start position *@paramMiddle switches position *@paramEnd Target position */
    public static void hanoi(int n,char start,char middle,char end){
        if (n == 1){
            System.out.println("Take the first plate from" + start + "挪到" + end);
        }
        else{
            // Move all the plates on the last one
            hanoi(n - 1,start,end,middle);
            System.out.println("The first" + n + "A plate from" + start + "挪到" + end);
            hanoi(n-1,middle,start,end); }}}Copy the code

Fibonacci and sequence problem implementation

public class TestFebonacci {
    public static void main(String[] args) {
        System.out.println(febonacci(8));
    }

    public static int febonacci(int i) {
        if (i == 1 || i == 2) {return 1;
        }
        return febonacci(i - 1) + febonacci(i - 2); }}Copy the code

Seven, trees,

1, the introduction

Tree is a kind of nonlinear data structure, it is composed of N (N >=0) finite nodes of a hierarchical relationship set. It’s called a tree because it looks like an upside down tree, meaning it has roots up and leaves down.

  • Root: The root node has no precursor.
  • Except for the root node, the remaining nodes are divided into a tree-like subtree. Each subtree root has one and only one precursor, and can have zero or more successors.
  • Thus, trees are defined recursively.

2. Several common concepts

  • Degree of node: the number of subtrees contained by a node is called the degree of the node; As shown in the figure above: A is 2
  • Leaf node: the node whose degree is 0 is called leaf node; As shown in the figure above, nodes G, H and I are leaf nodes
  • Non-terminal node or branch node: the node whose degree is not 0; As shown in the figure above, nodes B, D, C, E, and F are branch nodes
  • Parent node or parent node: If a node has children, the node is called the parent node of its children. As shown above: A is the parent of B
  • Child node or child node: The root node of the subtree that a node contains is called the child node of that node. As shown above: B is the child node of A
  • Sibling node: nodes with the same parent node are called sibling nodes. As shown in the figure above, B and C are siblings
  • Tree degree: In a tree, the degree of the largest node is called tree degree; As shown in the figure above: The degree of the tree is 2
  • Node hierarchy: the root is defined as the first layer, the child nodes of the root are defined as the second layer, and so on.
  • 2. The maximum level of nodes in a tree; As shown above: The height of the tree is 4
  • Cousin node: nodes with parents at the same level are Cousins of each other. As shown in the figure above, H and I are siblings of each other
  • Ancestor of a node: all nodes from the root to the branch through which the node passes; As in the figure above: A is the ancestor of all nodes
  • Descendant: Any node in the subtree rooted in a node is the descendant of the node. As shown in the figure above: All nodes are descendants of A
  • Forest: a collection of M non-intersecting trees called a forest;

3. Binary tree

3.1 introduction

A binary tree is a finite set of nodes that is either empty or consists of a root node plus two binary trees separately called left and right subtrees. Features of binary trees:

  1. Each node has at most two subtrees, that is, there is no node with a degree greater than 2 in the binary tree.
  2. The order of the subtrees of a binary tree cannot be reversed.

3.2 Storage Structure

Binary trees can generally use two storage structures, a sequential structure and a chain structure.

3.3 Chained storage of binary trees

Code implementation:

Create node code:

public class TreeNode {
    // Node three elements
    private Integer value;
    private TreeNode leftNode;
    private TreeNode rightNode;

    // Initializing a node requires assigning it a value
    public TreeNode(Integer value) {
        this.value = value;
    }

    // Assign a value to an element
    public void setLeftNode(TreeNode leftNode) {
        this.leftNode = leftNode;
    }

    public void setRightNode(TreeNode rightNode) {
        this.rightNode = rightNode;
    }

    public Integer getValue(a) {
        return value;
    }

    public void setValue(Integer value) {
        this.value = value;
    }

    // preorder traversal
    public void frontShow(a){
        System.out.println(value);
        if(leftNode ! =null){
            leftNode.frontShow();
        }
        if(rightNode ! =null){ rightNode.frontShow(); }}// middle order traversal
    public void midShow(a){
        if(leftNode ! =null){
            leftNode.midShow();
        }
        System.out.println(value);
        if(rightNode ! =null){ rightNode.midShow(); }}// after the sequence traversal
    public void afterShow(a){
        if(leftNode ! =null){
            leftNode.afterShow();
        }
        if(rightNode ! =null){
            rightNode.afterShow();
        }
        System.out.println(value);
    }

    // preorder search
    public TreeNode frontSearch(int num){
        TreeNode target = null;
        if (value == num){
            return this;
        }else{
            if(leftNode ! =null){
                target = leftNode.frontSearch(num);
            }
            if(target ! =null) {return target;
            }
            if(rightNode ! =null){ target = rightNode.frontSearch(num); }}return target;
    }

    @Override
    public String toString(a) {
        return "TreeNode{" +
                "value=" + value +
                ", leftNode=" + leftNode +
                ", rightNode=" + rightNode +
                '} ';
    }

    // Delete the subtree
    public void delete(int num){
        TreeNode parent = this;
        if(parent.leftNode ! =null && parent.leftNode.value == num){
            parent.leftNode = null;
            return;
        }
        if(parent.rightNode ! =null && parent.rightNode.value == null){
            parent.rightNode = null;
            return;
        }

        parent = leftNode;
        if(parent ! =null){
            leftNode.delete(num);
        };

        parent = rightNode;
        if(parent ! =null){ rightNode.delete(num); }}}Copy the code

Create binary tree code:

public class BinaryTree {
    TreeNode root;

    // Set the root node for the binary tree
    public TreeNode getRoot(a) {
        return root;
    }
    public void setRoot(TreeNode root) {
        this.root = root;
    }

    public void frontShow(a){
        root.frontShow();
    }

    public void midShow(a){
        root.midShow();
    }

    public void afterShow(a){
        root.afterShow();
    }

    public TreeNode frontSearch(int num){
        return root.frontSearch(num);
    }

    public void delete(int num){ root.delete(num); }}Copy the code

Testing:

public class TestBinaryTree {
    public static void main(String[] args) {
        BinaryTree tree = new BinaryTree();
        TreeNode node_01_01 = new TreeNode(1);
        // The tree sets the root node
        tree.setRoot(node_01_01);
        TreeNode node_02_02 = new TreeNode(2);
        TreeNode node_02_03 = new TreeNode(3);
        node_01_01.setLeftNode(node_02_02);
        node_01_01.setRightNode(node_02_03);
        TreeNode node_03_04 = new TreeNode(4);
        TreeNode node_03_05 = new TreeNode(5);
        TreeNode node_03_06 = new TreeNode(6);
        TreeNode node_03_07 = new TreeNode(7);
        node_02_02.setLeftNode(node_03_04);
        node_02_02.setRightNode(node_03_05);
        node_02_03.setLeftNode(node_03_06);
        node_02_03.setRightNode(node_03_07);
        TreeNode node_04_08 = new TreeNode(8);
        TreeNode node_04_09 = new TreeNode(9);
        TreeNode node_04_10 = new TreeNode(10);
        TreeNode node_04_11 = new TreeNode(11);
        TreeNode node_04_12 = new TreeNode(12);
        TreeNode node_04_13 = new TreeNode(13);
        TreeNode node_04_14 = new TreeNode(14);
        TreeNode node_04_15 = new TreeNode(15);
        node_03_04.setLeftNode(node_04_08);
        node_03_04.setRightNode(node_04_09);
        node_03_05.setLeftNode(node_04_10);
        node_03_05.setRightNode(node_04_11);
        node_03_06.setLeftNode(node_04_12);
        node_03_06.setRightNode(node_04_13);
        node_03_07.setLeftNode(node_04_14);
        node_03_07.setRightNode(node_04_15);
        tree.delete(5); tree.frontShow(); }}Copy the code

3.4 Sequential Storage of binary trees

In fact, every binary tree can be converted to an array, and an array can be converted to a binary tree. But in general, only the complete binary tree case is considered, because other cases may have empty values in the middle of the array.

The above binary tree can be changed to the following array:

This can be inferred from the binary tree above:

  • If the parent node is subscript n, its left child node is subscript (2n+1).
  • If the parent node is subscript n, its right child node is subscript (2n+2).
  • If the subscript of the child node is n, the subscript of its parent node is (n-1)/2

Code implementation:

public class ArrayBinaryTree {
    int[] data;

    public ArrayBinaryTree(int[] data) {
        this.data = data;
    }

    public void frontShow(a){
        frontShow(0);
    }

    public void frontShow(int index){
        if (data == null || data.length == 0) {return;
        }
        // Iterate over the contents of the current node
        System.out.println(data[index]);
        if (2*index + 1 < data.length){
            frontShow(2*index + 1);
        }
        if (2*index + 2 < data.length){
            frontShow(2*index + 2); }}}Copy the code

Output the value of the corresponding subscript:

public class TestArrayBinaryTree {
    public static void main(String[] args) {
        int[] array = new int[] {1.2.3.5.7.11.14.145};
        ArrayBinaryTree tree = new ArrayBinaryTree(array);
        tree.frontShow(7); }}Copy the code

4. Clue binary tree

Nodes:

public class ThreadedNode {
	// The weight of the node
	int value;
	/ / left son
	ThreadedNode leftNode;
	/ / right son
	ThreadedNode rightNode;
	// Identifies the pointer type
	int leftType;
	int rightType;
	

	public ThreadedNode(int value) {
		this.value=value;
	}
	
	// Set the left son
	public void setLeftNode(ThreadedNode leftNode) {
		this.leftNode = leftNode;
	}
	// Set the right son
	public void setRightNode(ThreadedNode rightNode) {
		this.rightNode = rightNode;
	}
	
	// preorder traversal
	public void frontShow(a) {
		// Iterate over the contents of the current node
		System.out.println(value);
		/ / the left node
		if(leftNode! =null) {
			leftNode.frontShow();
		}
		/ / right node
		if(rightNode! =null) { rightNode.frontShow(); }}// middle order traversal
	public void midShow(a) {
		// Left child node
		if(leftNode! =null) {
			leftNode.midShow();
		}
		// The current node
		System.out.println(value);
		// Right child node
		if(rightNode! =null) { rightNode.midShow(); }}// after the sequence traversal
	public void afterShow(a) {
		// Left child node
		if(leftNode! =null) {
			leftNode.afterShow();
		}
		// Right child node
		if(rightNode! =null) {
			rightNode.afterShow();
		}
		// The current node
		System.out.println(value);
	}

	// preorder search
	public ThreadedNode frontSearch(int i) {
		ThreadedNode target=null;
		// Compare the value of the current node
		if(this.value==i) {
			return this;
		// The value of the current node is not the node to look for
		}else {
			// Find the left son
			if(leftNode! =null) {
				// Target is still null
				target = leftNode.frontSearch(i);
			}
			// If it is not empty, it is found in the left son
			if(target! =null) {
				return target;
			}
			// Find the right son
			if(rightNode! =null) { target=rightNode.frontSearch(i); }}return target;
	}
	
	// Delete a subtree
	public void delete(int i) {
		ThreadedNode parent = this;
		// Judge the left son
		if(parent.leftNode! =null&&parent.leftNode.value==i) {
			parent.leftNode=null;
			return;
		}
		// Determine the right son
		if(parent.rightNode! =null&&parent.rightNode.value==i) {
			parent.rightNode=null;
			return;
		}
		
		// Recursively check and delete the left son
		parent=leftNode;
		if(parent! =null) {
			parent.delete(i);
		}
		
		// Recursively check and delete the right son
		parent=rightNode;
		if(parent! =null) { parent.delete(i); }}}Copy the code

Tree implementation code:

public class ThreadedBinaryTree {

	ThreadedNode root;
	// Used for temporary storage of precursor nodes
	ThreadedNode pre=null;
	
	// Walk through the clue binary tree
	public void threadIterate(a) {
		// Used to temporarily store the current traversal node
		ThreadedNode node = root;
		while(node! =null) {
			// Loop to find the original node
			while(node.leftType==0) {
				node=node.leftNode;
			}
			// Prints the value of the current node
			System.out.println(node.value);
			// If the right pointer of the current node points to a successor node, it may also have a successor node,
			while(node.rightType==1) {
				node=node.rightNode;
				System.out.println(node.value);
			}
			// Replace the traversal nodenode=node.rightNode; }}// Set the root node
	public void setRoot(ThreadedNode root) {
		this.root = root;
	}
	
	// Middle order cuing binary tree
	public void threadNodes(a) {
		threadNodes(root);
	}
	
	public void threadNodes(ThreadedNode node) {
		// If the current node is null, return directly
		if(node==null) {
			return;
		}
		// Process the left subtree
		threadNodes(node.leftNode);
		// Process the precursor node
		if(node.leftNode==null) {// Make the left pointer of the current node point to the precursor node
			node.leftNode=pre;
			// Change the type of the left pointer to the current node
			node.leftType=1;
		}
		// Handle the right pointer of the precursor if the right pointer of the precursor node is null(no reference to the lower right subtree)
		if(pre! =null&&pre.rightNode==null) {
			// Make the right pointer of the precursor node point to the current node
			pre.rightNode=node;
			// Change the right pointer type of the precursor node
			pre.rightType=1;
		}
		// For each node processed, the current node is the precursor of the next node
		pre=node;
		// Process the right subtree
		threadNodes(node.rightNode);
	}
	
	// Get the root node
	public ThreadedNode getRoot(a) {
		return root;
	}

	// preorder traversal
	public void frontShow(a) {
		if(root! =null) { root.frontShow(); }}// middle order traversal
	public void midShow(a) {
		if(root! =null) { root.midShow(); }}// after the sequence traversal
	public void afterShow(a) {
		if(root! =null) { root.afterShow(); }}// preorder search
	public ThreadedNode frontSearch(int i) {
		return root.frontSearch(i);
	}

	// Delete the subtree
	public void delete(int i) {
		if(root.value==i) {
			root=null;
		}else{ root.delete(i); }}}Copy the code

Testing:

public class TestThreadedBinaryTree {

	public static void main(String[] args) {
		// Create a tree
		ThreadedBinaryTree binTree = new ThreadedBinaryTree();
		// Create a root node
		ThreadedNode root = new ThreadedNode(1);
		// Assign the root node to the tree
		binTree.setRoot(root);
		// Create a left node
		ThreadedNode rootL = new ThreadedNode(2);
		// Set the newly created node as a child of the root node
		root.setLeftNode(rootL);
		// Create a right node
		ThreadedNode rootR = new ThreadedNode(3);
		// Set the newly created node as a child of the root node
		root.setRightNode(rootR);
		// Create two child nodes for the layer 2 left node
		rootL.setLeftNode(new ThreadedNode(4));
		ThreadedNode fiveNode = new ThreadedNode(5);
		rootL.setRightNode(fiveNode);
		// Create two child nodes for the right node of the second layer
		rootR.setLeftNode(new ThreadedNode(6));
		rootR.setRightNode(new ThreadedNode(7));
		// Middle order traversal tree
		binTree.midShow();
		System.out.println("= = = = = = = = = = = = = = =");
		// Binary treebinTree.threadNodes(); binTree.threadIterate(); }}Copy the code

5. Huffman Tree

5.1 introduction

A weighted path for A leaf node: As shown in the figure above, A line segment on each node (A/B/C/D) has A number that is the weight, and A weighted path is the number of such line segments * weights traversed.

For example, in the figure (a), a’s weighted path is 9×2 = 18, and B’s weighted path is 4×2 = 8.

WPL: Is the sum of the licensed paths of all leaf nodes in a tree.

So let’s do the math:

(a) WPL in the figure: 9×2 + 4×2 + 5×2 + 2×2 = 40

(b) WPL in figure 9×1 + 5×2 + 4×3 + 2×3 = 37

(c) WPL in figure 4×1 + 2×2 + 5×3 +9×3 =50

When attempting to build a tree with n nodes (all leaf nodes and each with its own weight), the tree is called an “optimal binary tree”, sometimes called a “Huffman tree” or “Huffman tree”, if the tree is constructed with the smallest WPL. So b is the Huffman tree.

5.2 Theoretical Implementation

For a given N nodes with their respective weights, there is an effective method to construct Huffman tree:

  1. Two minimum weights are selected from n weights, and the corresponding two nodes form a new binary tree, and the weight of the root node of the new binary tree is the sum of the weight of the left and right children.
  2. Delete the two smallest weights from the original N weights, and add the new weights to the row of n – 2 weights, and so on;
  3. Repeat 1 and 2 until all nodes form a binary tree, which is a Huffman tree.

5.3 Code Implementation

Create a node:

public class Node implements Comparable<Node> {
	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(a) {
		return "Node [value=" + value + "]"; }}Copy the code

The Huffman tree:

public class TestHuffmanTree {
	public static void main(String[] args) {
		int[] arr = {3.7.8.29.5.11.23.14};
		Node node = createHuffmanTree(arr);
		System.out.println(node);
	}
	
	// Create a Huffman tree
	public static Node createHuffmanTree(int[] arr) {
		// Create a binary tree with all the elements in the array (only one node)
		List<Node> nodes = new ArrayList<>();
		for(int value:arr) {
			nodes.add(new Node(value));
		}
		// loop processing,
		while(nodes.size()>1) {
			/ / sorting
			Collections.sort(nodes);
			// Retrieve the two binomial trees with the lowest weights
			// Select the binary tree with the least weight
			Node left = nodes.get(nodes.size()-1);
			// Retrieve the binary tree with the lowest weight
			Node right = nodes.get(nodes.size()-2);
			// Create a new binary tree
			Node parent = new Node(left.value+right.value);
			// Remove the two binary trees
			nodes.remove(left);
			nodes.remove(right);
			// Put it into the original binary tree set
			nodes.add(parent);
		}
		return nodes.get(0); }}Copy the code

5.4 Huffman coding

For example: To pass the statement can you can a can as a can canner can a can.

If we were to encode each word directly in the old way, we would see very large binary bytecodes.

Let’s start with this:

99 97 110 32 121 111 117 32 99 97 110 32 97 32 99 97 110 32 97 115 32 97 32 99 97 97 110 32 99 97 110 110 101 114 32 99 97 97 110 32 97 32 99 97 110 46

And then it looks like this: the length is 396

01100011 01100001 01101110 00100000 01111001 01101111 01110101 00100000 01100011 01100001 01101110 00100000 01100001 00100000 01100011 01100001 01101110 00100000 01100001 01110011 00100000 01100001 00100000 01100011 01100001 01101110 00100000 01100011 01100001 01101110 01101110 01100101 01110010 00100000 01100011 01100001 01101110 00100000 01100001 00100000 01100011 01100001 01101110 00101110

That’s a lot of storage. It eats up memory.

So someone might as well take a different approach:

Note the number of occurrences of each letter: R :1 S :1 U :1 E :1 Y :1.:1 O :1 C :7 N :8 Space :11 A :11

The problem can be solved by using smaller numbers for the letters that appear most frequently, and larger numbers for the letters that appear less frequently.

Such as according to this logic: a, 0 = 1 = Spaces, n = 10, 11 = c, 100 = o =. 101, 110 = y, 111 = e = 1000 u, 1001 = s = 1010 r

So it becomes this: 110101110 100 11010111001010011… .

The actual bytecode is no Spaces: 11010111010011010111001010011…

So that begs the question, how do you break a sentence? The first one is 1, is it 11, is it 110?

At this point, you can use the Huffman tree for storage. The diagram below:

Then the encoding of each character can be stored according to the weight above.

This ensures that the data is unique.

The saved character encoding is as follows:

111 1000 01 110010 11000 110100 01 111 1000 01 1001 111 1000 01 10 110111 01 1000 01 111 1000 01 111 1000 00 00 110101 110110 01 111 10 00 0110 01 111 10 00 110011

Remove Spaces: the total length is 122

11110000111001011000110100011111000011001111100001101101110110011111000011111000001101011101100111110000110011111000110011

From 396 to 122 you can see that’s a lot of compression.

Code implementation:

It should be divided into the following steps:

  • Count the characters and sort them

  • Create the Huffman tree

  • Create the Huffman encoding table

  • coding

Create a node:

public class Node implements Comparable<Node> {
	Byte data;
	int weight;
	Node left;
	Node right;
	public Node(Byte data,int weight) {
		this.data=data;
		this.weight=weight;
	}
	
	@Override
	public String toString(a) {
		return "Node [data=" + data + ", weight=" + weight + "]";
	}

	@Override
	public int compareTo(Node o) {
		return o.weight-this.weight; }}Copy the code

Create a Huffman tree:

public class TestHuffmanCode {

	public static void main(String[] args) {
// String msg="can you can a can as a can canner can a can.";
// byte[] bytes = msg.getBytes();
// // for Huffman coding compression
// byte[] b = huffmanZip(bytes);
// // is decoded using Huffman code
// byte[] newBytes = decode(huffCodes,b);
// System.out.println(new String(newBytes));
		String src="1.bmp";
		String dst="2.zip";
// try {
// zipFile(src, dst);
// } catch (IOException e) {
// e.printStackTrace();
/ /}
		try {
			unZip("2.zip"."3.bmp");
		} catch(Exception e) { e.printStackTrace(); }}/** * unzip the file *@param src
	 * @param dst
	 * @throws Exception 
	 */
	public static void unZip(String src,String dst) throws Exception {
		// Create an input stream
		InputStream is  = new FileInputStream("2.zip");
		ObjectInputStream ois = new ObjectInputStream(is);
		// Read the byte array
		byte[] b = (byte[]) ois.readObject();
		// Read the Huffman encoding table
		Map<Byte, String> codes = (Map<Byte, String>) ois.readObject();
		ois.close();
		is.close();
		/ / decoding
		byte[] bytes = decode(codes, b);
		// Create an output stream
		OutputStream os  = new FileOutputStream(dst);
		// Write out data
		os.write(bytes);
		os.close();
	}
	
	/** * zip file *@param src
	 * @param dst
	 * @throws IOException
	 */
	public static void zipFile(String src,String dst) throws IOException {
		// Create an input stream
		InputStream is = new FileInputStream(src);
		// Create a byte array of the same size as the file pointed to by the input stream
		byte[] b = new byte[is.available()];
		// Read the contents of the file
		is.read(b);
		is.close();
		// Use Huffman encoding to encode
		byte[] byteZip = huffmanZip(b);
		/ / the output stream
		OutputStream os = new FileOutputStream(dst);
		ObjectOutputStream oos = new ObjectOutputStream(os);
		// Write the compressed byte array to the file
		oos.writeObject(byteZip);
		// Write the Huffman encoding table to the file
		oos.writeObject(huffCodes);
		oos.close();
		os.close();
	}
	
	/** * decodes using the specified Huffman encoding table *@param huffCodes2
	 * @param b
	 * @return* /
	private static byte[] decode(Map<Byte, String> huffCodes, byte[] bytes) {
		StringBuilder sb = new StringBuilder();
		// Convert the byte array to a binary string
		for(int i=0; i<bytes.length; i++) {byte b = bytes[i];
			// Is it the last one?
			boolean flag = (i==bytes.length-1); sb.append(byteToBitStr(! flag,b)); }// Decodes the string according to the specified Huffman encoding
		// Switch the Huffman key pairs
		Map<String, Byte> map = new HashMap<>();
		for(Map.Entry<Byte, String> entry:huffCodes.entrySet()) {
			map.put(entry.getValue(), entry.getKey());
		}
		// Create a collection of bytes
		List<Byte> list = new ArrayList<>();
		// Process strings
		for(int i=0; i<sb.length();) {int count=1;
			boolean flag = true;
			Byte b=null;
			// truncate a byte
			while(flag) {
				String key = sb.substring(i, i+count);
				b = map.get(key);
				if(b==null) {
					count++;
				}else {
					flag=false;
				}
			}
			list.add(b);
			i+=count;
		}
		// Convert a collection to an array
		byte[] b = new byte[list.size()];
		for(int i=0; i<b.length; i++) { b[i]=list.get(i); }return b;
	}
	
	private static String byteToBitStr(boolean flag,byte b) {
		int temp=b;
		if(flag) {
			temp|=256;
		}
		String str = Integer.toBinaryString(temp);
		if(flag) {
			return str.substring(str.length()-8);
		}else {
			returnstr; }}/** * A method to compress the Huffman code *@param bytes
	 * @return* /
	private static byte[] huffmanZip(byte[] bytes) {
		// Count the number of occurrences of each byte and put it into a set
		List<Node> nodes = getNodes(bytes);
		// Create a Hefman tree
		Node tree = createHuffmanTree(nodes);
		// Create a Huffman encoding table
		Map<Byte, String> huffCodes = getCodes(tree);
		/ / code
		byte[] b = zip(bytes,huffCodes);
		return b;
	}
	
	/** * Perform Huffman encoding *@param bytes
	 * @param huffCodes2
	 * @return* /
	private static byte[] zip(byte[] bytes, Map<Byte, String> huffCodes) {
		StringBuilder sb = new StringBuilder();
		// Process the byte array to be compressed into a binary string
		for(byte b:bytes) {
			sb.append(huffCodes.get(b));
		}
		// Define the length
		int len;
		if(sb.length()%8= =0) {
			len=sb.length()/8;
		}else {
			len=sb.length()/8+1;
		}
		// Stores compressed bytes
		byte[] by = new byte[len];
		// Record the position of the new byte
		int index = 0;
		for(int i=0; i<sb.length(); i+=8) {
			String strByte;
			if(i+8>sb.length()) {
				strByte = sb.substring(i);
			}else {
				strByte = sb.substring(i, i+8);
			}
			byte byt = (byte)Integer.parseInt(strByte, 2);
			by[index]=byt;
			index++;
		}
		return by;
	}

	// For temporary storage paths
	static StringBuilder sb = new StringBuilder();
	// Used to store the Huffman code
	static Map<Byte, String> huffCodes = new HashMap<>();
	/** * Get the Huffman code from the Huffman tree *@param tree
	 * @return* /
	private static Map<Byte, String> getCodes(Node tree) {
		if(tree==null) {
			return null;
		}
		getCodes(tree.left,"0",sb);
		getCodes(tree.right,"1",sb);
		return huffCodes;
	}

	private static void getCodes(Node node, String code, StringBuilder sb) {
		StringBuilder sb2 = new StringBuilder(sb);
		sb2.append(code);
		if(node.data==null) {
			getCodes(node.left, "0", sb2);
			getCodes(node.right, "1", sb2);
		}else{ huffCodes.put(node.data, sb2.toString()); }}/** * Create a Huffman tree *@param nodes
	 * @return* /
	private static Node createHuffmanTree(List<Node> nodes) {
		while(nodes.size()>1) {
			/ / sorting
			Collections.sort(nodes);
			// Retrieve two binary trees with the lowest weights
			Node left = nodes.get(nodes.size()-1);
			Node right = nodes.get(nodes.size()-2);
			// Create a new binary tree
			Node parent = new Node(null, left.weight+right.weight);
			// Set the two binary trees as subtrees of the newly created binary tree
			parent.left=left;
			parent.right=right;
			// Delete the two binary trees
			nodes.remove(left);
			nodes.remove(right);
			// Put the newly created binary tree into the collection
			nodes.add(parent);
		}
		return nodes.get(0);
	}

	/** * Convert byte array to node set *@param bytes
	 * @return* /
	private static List<Node> getNodes(byte[] bytes) {
		List<Node> nodes = new ArrayList<>();
		// Store the number of occurrences per byte.
		Map<Byte, Integer> counts = new HashMap<>();
		// Count the number of occurrences per byte
		for(byte b:bytes) {
			Integer count = counts.get(b);
			if(count==null) {
				counts.put(b, 1);
			}else {
				counts.put(b, count+1); }}// Convert each key-value pair into a Node object
		for(Map.Entry<Byte, Integer> entry:counts.entrySet()) {
			nodes.add(new Node(entry.getKey(), entry.getValue()));
		}
		returnnodes; }}Copy the code

Binary sort tree

6.1 introduction

It has the following characteristics:

  • In a binary sorting tree, if the root node has a left subtree, the values of all nodes in the left subtree are less than the values of the root node.
  • In a binary sort tree, if the root node has a right subtree, then the values of all nodes in the right subtree are equal to the values of the root node;
  • The left and right subtrees of a binary sort tree should also be binary sort trees.

6.2 Code Implementation

Nodes:

public class Node {
	int value;
	Node left;
	Node right;
	
	public Node(int value) {
		this.value=value;
	}

	/** * adds node * to the subtree@param node
	 */
	public void add(Node node) {
		if(node==null) {
			return;
		}
		// Determine whether the value of the passed node is larger or smaller than the value of the root node of the current subtree
		// The added node has a smaller value than the current node
		if(node.value<this.value) {
			// If the left node is empty
			if(this.left==null) {
				this.left=node;
			// If not empty
			}else {
				this.left.add(node); }}else {
			if(this.right==null) {
				this.right=node;
			}else {
				this.right.add(node); }}}/** **@param node
	 */
	public void midShow(Node node) {
		if(node==null) {
			return;
		}
		midShow(node.left);
		System.out.println(node.value);
		midShow(node.right);
	}

	/** * find node *@param value2
	 */
	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;
			}
			returnright.search(value); }}/** * Search for the parent node *@param value
	 * @return* /
	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; }}}Copy the code

Binary sort tree:

public class BinarySortTree {
	Node root;
	
	/** * add node * to binary sort tree@param node
	 */
	public void add(Node node){
		// If it is an empty tree
		if(root==null) {
			root=node;
		}else{ root.add(node); }}/** * traverses the binary sort tree in order from smallest to largest */
	public void midShow(a) {
		if(root! =null) { root.midShow(root); }}/** * node search *@param value
	 * @return* /
	public Node search(int value) {
		if(root==null) {
			return null;
		}else {
			returnroot.search(value); }}/** * Delete node *@param value
	 */
	public void delete(int value) {
		if(root==null) {
			return;
		}else {
			// Find this node
			Node target = search(value);
			// If there is no such node
			if(target==null) {
				return;
			}
			// Find his parent node
			Node parent = searchParent(value);
			// The node to be deleted is the leaf node
			if(target.left==null&&target.right==null) {
				// The node to be deleted is the left child of the parent node
				if(parent.left.value==value) {
					parent.left=null;
					// The node to be deleted is the right child of the parent node
				}else {
					parent.right=null;
				}
			// The node to be deleted has two children
			}else if(target.left! =null&&target.right! =null) {
				// Delete the node with the smallest value in the right subtree
				int min = deleteMin(target.right);
				// Replace the value in the target node
				target.value=min;
			// The node to be deleted has a left child or a right child
			}else {
				// There are left child nodes
				if(target.left! =null) {
					// The node to be deleted is the left child of the parent node
					if(parent.left.value==value) {
						parent.left=target.left;
						// The node to be deleted is the right child of the parent node
					}else {
						parent.right=target.left;
					}
				// There are right child nodes
				}else {
					// The node to be deleted is the left child of the parent node
					if(parent.left.value==value) {
						parent.left=target.right;
						// The node to be deleted is the right child of the parent node
					}else {
						parent.right=target.right;
					}
				}
			}
		}
	}
	
	/** * Delete the smallest node * in a tree@param right
	 * @return* /
	private int deleteMin(Node node) {
		Node target = node;
		// recurse to the left
		while(target.left! =null) {
			target=target.left;
		}
		// Delete the smallest node
		delete(target.value);
		return target.value;
	}

	/** * Search for the parent node *@param value
	 * @return* /
	public Node searchParent(int value) {
		if(root==null) {
			return null;
		}else {
			returnroot.searchParent(value); }}}Copy the code

Testing:

public class TestBinarySortTree {

	public static void main(String[] args) {
		int[] arr = new int[] {7.3.10.12.5.1.9};
		// Create a binary sort tree
		BinarySortTree bst = new BinarySortTree();
		// loop add
		for(int i:arr) {
			bst.add(new Node(i));
		}
		// View the values in the tree
		bst.midShow();
		System.out.println("-- -- -- -- --");
		/ / to find
// Node node = bst.search(10);
// System.out.println(node.value);
		//
// Node node2 = bst.search(20);
// System.out.println(node2);
// // Tests to find the parent node
// Node p1 = bst.searchParent(12);
// System.out.println(p1.value);
// System.out.println("-----");
		// Delete the leaf node
// bst.delete(5);
// bst.midShow();
// System.out.println("===");
		// Delete a node with only one child node
// bst.delete(3);
// bst.midShow();
		// Delete a node with two children
		bst.delete(3);
		System.out.println("--"); bst.midShow(); }}Copy the code

7. AVL tree (Balanced binary tree)

7.1 introduction

Balanced Binary Tree is also called AVL Tree (different from AVL algorithm), and has the following properties: it is an empty Tree or the absolute value of the height difference between the left and right subtrees is not more than 1, and both subtrees are Balanced Binary trees. This scheme solves the problem of binary search tree degenerating into linked list well, and keeps the time complexity of insertion, search and deletion in O(logN) at best and at worst. However, frequent rotation causes insertion and deletion to sacrifice order (logN) time, but it is much more stable than binary search trees.

7.2 Rotation code implementation

public class Node {
	int value;
	Node left;
	Node right;
	
	public Node(int value) {
		this.value=value;
	}

	/** * Returns the height of the current node *@return* /
	public int height(a) {
		return Math.max(left==null?0:left.height(), right==null?0:right.height())+1;
	}
	
	/** * Gets the height of the left subtree *@return* /
	public int leftHeight(a) {
		if(left==null) {
			return 0;
		}
		return left.height();
	}
	
	/** * Get the height of the right subtree *@return* /
	public int rightHeight(a) {
		if(right==null) {
			return 0;
		}
		return right.height();
	}

	/** * adds node * to the subtree@param node
	 */
	public void add(Node node) {
		if(node==null) {
			return;
		}
		// Determine whether the value of the passed node is larger or smaller than the value of the root node of the current subtree
		// The added node has a smaller value than the current node
		if(node.value<this.value) {
			// If the left node is empty
			if(this.left==null) {
				this.left=node;
			// If not empty
			}else {
				this.left.add(node); }}else {
			if(this.right==null) {
				this.right=node;
			}else {
				this.right.add(node); }}// Check the balance
		// Rotate to the right
		if(leftHeight()-rightHeight()>=2) {
			/ / double rotation
			if(left! =null&&left.leftHeight()<left.rightHeight()) {
				// Rotate left first
				left.leftRotate();
				// Rotate to the right
				rightRotate();
			/ / a single rotation
			}else{ rightRotate(); }}/ / left rotation
		if(leftHeight()-rightHeight()<=-2) {
			/ / double rotation
			if(right! =null&&right.rightHeight()<right.leftHeight()) {
				right.rightRotate();
				leftRotate();
			/ / a single rotation
			}else{ leftRotate(); }}}/** * rotate left */
	private void leftRotate(a) {
		Node newLeft = new Node(value);
		newLeft.left=left;
		newLeft.right=right.left;
		value=right.value;
		right=right.right;
		left=newLeft;
	}

	/** ** right rotation */
	private void rightRotate(a) {
		// Create a new node equal to the value of the current node
		Node newRight = new Node(value);
		// Set the right subtree of the new node to the right subtree of the current node
		newRight.right=right;
		// Set the left subtree of the new node to the right subtree of the left subtree of the current node
		newRight.left=left.right;
		// Change the value of the current node to the value of the left child node
		value=left.value;
		// Set the left subtree of the current node to the left subtree of the left subtree
		left=left.left;
		// Set the right subtree of the current node to the new node
		right=newRight;
	}

	/** **@param node
	 */
	public void midShow(Node node) {
		if(node==null) {
			return;
		}
		midShow(node.left);
		System.out.println(node.value);
		midShow(node.right);
	}

	/** * find node *@param value2
	 */
	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;
			}
			returnright.search(value); }}/** * Search for the parent node *@param value
	 * @return* /
	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; }}}Copy the code

Balanced binary trees

public class BinarySortTree {
	Node root;
	
	/** * add node * to binary sort tree@param node
	 */
	public void add(Node node){
		// If it is an empty tree
		if(root==null) {
			root=node;
		}else{ root.add(node); }}/** * traverses the binary sort tree in order from smallest to largest */
	public void midShow(a) {
		if(root! =null) { root.midShow(root); }}/** * node search *@param value
	 * @return* /
	public Node search(int value) {
		if(root==null) {
			return null;
		}else {
			returnroot.search(value); }}/** * Delete node *@param value
	 */
	public void delete(int value) {
		if(root==null) {
			return;
		}else {
			// Find this node
			Node target = search(value);
			// If there is no such node
			if(target==null) {
				return;
			}
			// Find his parent node
			Node parent = searchParent(value);
			// The node to be deleted is the leaf node
			if(target.left==null&&target.right==null) {
				// The node to be deleted is the left child of the parent node
				if(parent.left.value==value) {
					parent.left=null;
					// The node to be deleted is the right child of the parent node
				}else {
					parent.right=null;
				}
			// The node to be deleted has two children
			}else if(target.left! =null&&target.right! =null) {
				// Delete the node with the smallest value in the right subtree
				int min = deleteMin(target.right);
				// Replace the value in the target node
				target.value=min;
			// The node to be deleted has a left child or a right child
			}else {
				// There are left child nodes
				if(target.left! =null) {
					// The node to be deleted is the left child of the parent node
					if(parent.left.value==value) {
						parent.left=target.left;
						// The node to be deleted is the right child of the parent node
					}else {
						parent.right=target.left;
					}
				// There are right child nodes
				}else {
					// The node to be deleted is the left child of the parent node
					if(parent.left.value==value) {
						parent.left=target.right;
						// The node to be deleted is the right child of the parent node
					}else {
						parent.right=target.right;
					}
				}
			}
		}
	}
	
	/** * Delete the smallest node * in a tree@param right
	 * @return* /
	private int deleteMin(Node node) {
		Node target = node;
		// recurse to the left
		while(target.left! =null) {
			target=target.left;
		}
		// Delete the smallest node
		delete(target.value);
		return target.value;
	}

	/** * Search for the parent node *@param value
	 * @return* /
	public Node searchParent(int value) {
		if(root==null) {
			return null;
		}else {
			returnroot.searchParent(value); }}}Copy the code

Testing:

public class TestBinarySortTree {

	public static void main(String[] args) {
Int [] arr = new int[] {8,9,6,7,5,4};
		int[] arr = new int[] {8.9.5.4.6.7};
		// Create a binary sort tree
		BinarySortTree bst = new BinarySortTree();
		// loop add
		for(int i:arr) {
			bst.add(new Node(i));
		}
		// Check the height
		System.out.println(bst.root.height());
		//System.out.println(bst.root.value); }}Copy the code

Multipath lookup tree

8.1 Computer storage

Memory storage is much faster than disk.

The disk has track after track, and we use magnetic arms for reading and writing operations. This is obviously much slower. In addition, the disk reads data slowly, reducing I/O operations on the disk. The disk prereads some data to the memory in advance. The data is of a certain length and may be immediately available or not needed. The length of the prefetch is generally an integer multiple of the page.

So if you read a binary tree, you’re going to read some of the data into memory, but you’re going to read some of the data into disk because you don’t have enough memory. A node in a binary tree is a page. In this way, only one node is accessed each time I/O is read.

This is better to use the way of multi-path search tree.

8.2 the 2-3 tree

A 2-3 tree is the simplest B-tree (or -tree) structure, with two or three children per non-leaf node and all leaves on a unified layer.

2-3 Tree lookup element 5:

2-3 tree to add data to an element position:

2-3 tree adds data to two element locations:

Another case of adding elements to a 2-3 tree:

2-3 Tree delete element:

8.3 B tree and B+ tree

B is basically like 2 and 3.

Hash table (hash table)

1, the introduction

Is a data structure that is accessed directly according to the Key value. That is, it accesses records by mapping key values to a location in the table to speed up lookups. This mapping function is called a hash function, and the array of records is called a hash table.

2. Code implementation

Student information

public class StuInfo {

	private int age;
	private int count;

	public int getAge(a) {
		return age;
	}

	public void setAge(int age) {
		this.age = age;
	}

	public int getCount(a) {
		return count;
	}

	public void setCount(int count) {
		this.count = count;
	}
	
	/** * hash function */
	public int hashCode(a) {
		return age;
	}

	public StuInfo(int age, int count) {
		super(a);this.age = age;
		this.count = count;
	}

	public StuInfo(int age) {
		super(a);this.age = age;
	}

	@Override
	public String toString(a) {
		return "StuInfo [age=" + age + ", count=" + count + "]"; }}Copy the code

Hash table:

public class HashTable {
	private StuInfo[] data = new StuInfo[100];
	
	/** * Adds elements * to the hash table@param stuInfo
	 */
	public void put(StuInfo stuInfo) {
		// Call the hash function to get the storage location
		int index = stuInfo.hashCode();
		// Add elements
		data[index]=stuInfo;
	}
	
	public StuInfo get(StuInfo stuInfo) {
		return data[stuInfo.hashCode()];
	}

	@Override
	public String toString(a) {
		return "HashTable [data=" + Arrays.toString(data) + "]"; }}Copy the code

Testing:

public class TestHashTable {

	public static void main(String[] args) {
		StuInfo s1 = new StuInfo(16.3);
		StuInfo s2 = new StuInfo(17.11);
		StuInfo s3 = new StuInfo(18.23);
		StuInfo s4 = new StuInfo(19.24);
		StuInfo s5 = new StuInfo(20.9);
		
		HashTable ht = new HashTable();
		ht.put(s1);
		ht.put(s2);
		ht.put(s3);
		ht.put(s4);
		ht.put(s5);

		System.out.println(ht);
		
		// The target data that you want to get
		StuInfo target = new StuInfo(18); StuInfo info = ht.get(target); System.out.println(info); }}Copy the code

3. Address conflict

3.1 Open address method

After a hash conflict occurs, the next free cell is found in a certain order and the conflicting elements are put in.

3.1.1 Linear exploration method

Start the probe from the conflicting cell and check whether the next cell is empty. If the last cell is empty, check from the top of the table. Do this until a free cell is hit or all cells have been explored.

3.2.2 Square probe method

Add 1^2,2^2,3^2 from the conflicting cell… N ^2, until it hits a free cell.

3.2 Chain address method

Form a linked list of elements with the same hash value, and place the head in the hash table. Lists that are longer than eight become red-black trees, and lists that are less than six become lists.

3.3 Rehash

Construct multiple different hash functions at the same time, Hi = RHi(key) I = 1,2,3… k; When H1 = RH1(key) conflict occurs, H2 = RH2(key) is used for calculation until the conflict does not occur again. This method is not easy to generate aggregation, but increases the calculation time.

Nine, figure

1, the introduction

Diagrams are used when we need to represent many-to-many relationships, where old trees, linked lists, etc., are not appropriate.

A graph is a data structure in which a node can have zero or more adjacent elements. The connection between two nodes is called an edge. Nodes can also be called vertices.

A directed graph is one with an arrow, and an undirected graph is one without an arrow.

The weighted values in the figure are weighted graphs.

2. Code implementation

public class Vertex {

	private String value;
	public boolean visited;

	public String getValue(a) {
		return value;
	}

	public void setValue(String value) {
		this.value = value;
	}

	public Vertex(String value) {
		super(a);this.value = value;
	}

	@Override
	public String toString(a) {
		returnvalue; }}Copy the code

Graph structure:

public class Graph {

	private Vertex[] vertex;
	private int currentSize;
	public int[][] adjMat;
	private MyStack stack = new MyStack();
	// The index of the current traversal
	private int currentIndex;
	
	public Graph(int size) {
		vertex=new Vertex[size];
		adjMat=new int[size][size];
	}
	
	/** * adds a vertex * to the graph@param v
	 */
	public void addVertex(Vertex v) {
		vertex[currentSize++]=v;
	}
	
	public void addEdge(String v1,String v2) {
		// Find the subscripts of the two vertices
		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;
	}
	
	/** * depth-first search algorithm traversal graph */
	public void dfs(a) {
		// mark the 0th vertex as visited
		vertex[0].visited=true;
		// subscript the 0th vertex.
		stack.push(0);
		// Prints the vertex values
		System.out.println(vertex[0].getValue());
		/ / traverse
		out:while(! stack.isEmpty()) {for(int i=currentIndex+1; i<vertex.length; i++) {// if it is common to the next iterated element
				if(adjMat[currentIndex][i]==1&&vertex[i].visited==false) {
					// Push the next element onto the stack
					stack.push(i);
					vertex[i].visited=true;
					System.out.println(vertex[i].getValue());
					continueout; }}// Pops the top element of the stack
			stack.pop();
			// Change the current position to the position of the top element on the stack
			if(! stack.isEmpty()) { currentIndex=stack.peek(); }}}}Copy the code

Testing:

public class TestGraph {

	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);
		
		/ / add edge
		g.addEdge("A"."C");
		g.addEdge("B"."C");
		g.addEdge("A"."B");
		g.addEdge("B"."D");
		g.addEdge("B"."E");
		
		for(int[] a:g.adjMat) {
			System.out.println(Arrays.toString(a));
		}
		Depth-first traversalg.dfs(); }}Copy the code