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:
- Each node has at most two subtrees, that is, there is no node with a degree greater than 2 in the binary tree.
- 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:
- 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.
- 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;
- 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