Tree of data structures

Why is a tree a data structure
Common term for tree
Tree structure Java code implementation
Order traversal before, middle and after
Huffman part
Hoffman tree
Huffman coding
Huffman encrypts the file
The binary tree part
Sequential storage of binary trees
Cue binary tree
Binary sort tree
Balanced binary trees
Multi-fork tree part
B plus tree and B star tree
Red and black tree

The following ideas and key methods are only given. The source code of the algorithm is put in Git, and you need to take it yourself

Gitee.com/leidl97/alg…

Why is a tree a data structure

Because tree structures store and read data more efficiently than other data structures!

1. Array storage mode analysis

Advantages: Fast access to elements by subscript. For ordered arrays, binary lookup can also be used to speed up retrieval

Disadvantages: If you want to retrieve a specific value, or the insert moves as a whole, reducing efficiency

2. Analysis of chain structure

Advantages: It is fast to insert and delete a node

Disadvantages: Retrieval is still inefficient and requires traversal of the primary node

3. Tree structure analysis

Improve the efficiency of storage and reading, such as the use of binary tree sorting, can ensure the storage speed, but also to ensure the speed of reading, modify, delete and so on

Common term for tree

Node: A circle represents a node
Root node: uppermost node
Parent node: Whoever points to it is the parent node
Child node: Whoever it points to indicates who the child node is
Leaf node: The lowest layer of nodes (nodes with no children)
Weight: represents the value of a node

A binary tree, as its name implies, is a binary tree with two forks. A node has at most two child nodes

If all the leaves of a binary tree are at the last level, we are a full binary tree

If the last layer is left continuous and all other layers are full, we call it a complete binary tree, as shown

Tree structure Java code implementation

Take binary trees, for example

Main attributes: left node, right node, weight

Attribute definitions

Public class Node {// Left subtree public Node leftNode; // Right subtree public Node rightNode; Public int value; Public Node(int value) {this.value = value; }}Copy the code

Nodes are added and modified by constantly looking for and operating accordingly if the node is empty

But no matter what kind of tree, deleting is the most complicated. More on that later

Order traversal before, middle and after

Subject to the father!

Foreorder traversal: parent left and right

Middle order traversal: left parent right

Post-order traversal: left and right parent

Code implementation logic (recursive thinking)

The former sequence traversal

1. Output the current node first

2. Traverse the left node (if the node is not empty)

3. Traverse to the right node (if the node is not empty)

Public void beforeTraversal(Node Node) {system.out. print(node.getValue() + "\t"); // Iterate over if (node.getLeftNode()! =null) { beforeTraversal(node.getLeftNode()); } // Go right over if (node.getrightNode ()! =null) { beforeTraversal(node.getRightNode()); }}Copy the code

In the sequence traversal

1. Traverse the left node (if the node is not empty)

2. Output the current node first

3. Traverse to the right node (if the node is not empty)

Public void centerTraversal(Node Node) {if (node.getLeftNode()! =null) { centerTraversal(node.getLeftNode()); } system.out. print(node.getValue() + "\t"); If (node.getrightNode ()! =null) { centerTraversal(node.getRightNode()); }}Copy the code

After the sequence traversal

1. Traverse the left node (if the node is not empty)

2. Traverse to the right node (if the node is not empty)

3. Output the current node first

Public void afterTraversal(Node Node) {if (node.getLeftNode()! =null) { centerTraversal(node.getLeftNode()); } // Next go right through if (node.getrightNode ()! =null) { centerTraversal(node.getRightNode()); } system.out. print(node.getValue() + "\t"); }Copy the code

All traversal search, the truth is the same, rebuild the method, pass in one more target value value, the previous order traversal prevail, then the code implementation is

Public void beforeTraversalSearch(Node Node, int value) {count++; If (node.getValue() == value) {system.out.println (" find the element :"+value+", count :"+count "); } // iterate to the left if (node.getLeftNode()! =null) { beforeTraversalSearch(node.getLeftNode(),value); } // Go right over if (node.getrightNode ()! =null) { beforeTraversalSearch(node.getRightNode(),value); }}Copy the code

Huffman tree (WPL smallest tree)

Introduction: given n weight n leaf nodes, construct a binary tree, if the tree’s weighted path length (WPL) reaches the minimum, such a binary tree is called the optimal binary tree, also called HuffmanTree.

Scenario simulation: You are given an array and asked to create a Huffman tree. Such as {13,7,8,3,29,6,1}

steps

1, sort first (this is not the point, how to achieve fast how to)

{1，3，6，7，8，13，29}

2. Add the first two values to get a weight and compare with the latter

3. Build a Huffman tree until you have processed all the numbers

The construction result is shown in figure

The difficulties in

1. How to determine if the supplied value is used up

With the set, the left and right nodes will be deleted after each row, and then the parent node will be added. When the number of elements in the final set is 1 (the set size always starts with -2 and then +1, and the last remaining is the weight of addition), it will be consumed

private static void huffmanBuild(int[] a) { Arrays.sort(a); List<Node> nodes = new ArrayList<>(); For (int value: a) {// Add node object nodes.add(new node (value)); } while (nodes.size() > 1) { Node leftNode = nodes.get(0); Node rigtNode = nodes.get(1); Node parent = new Node(leftNode.getValue() + rigtNode.getValue()); // Create a binary tree parent.setLeftNode(leftNode); parent.setRightNode(rigtNode); nodes.remove(leftNode); nodes.remove(rigtNode); nodes.add(parent); Sort (Nodes, new Comparator<Node>() {@override public int compare(Node o1, Node o2) { return o1.getValue() - o2.getValue(); }}); } Tree tree = new Tree(nodes.get(0)); tree.beforeTraversal(tree.getRoot()); System.out.println(); }Copy the code

Huffman coding

1. It belongs to a programming algorithm

2. Classical application in telecommunication

3, can be used for data file compression, compression rate between 20% – 90%

4, is a variable word length coding (VLC), called the best coding, is lossless compression

How to understand

If a string of text reads “I like Java”, it is converted to ASCII and then to binary, which is called fixed-length encoding

You wouldn’t normally do that, because it’s too long, so the communication world is dealing with variable-length encoding

First count the number of occurrences of each letter in the string. The more occurrences, the smaller the code. However, the encoding of each character cannot be a prefix of other characters. For example, A is represented by 1, and B cannot be represented by 10. In this way, the machine cannot decode when it scans 1, resulting in ambiguities.

The third kind of coding is called Huffman coding

The number of occurrences of each code is called the weight, and then a Huffman tree is constructed. The path to the left is 0, the path to the right is 1, and the path from the root node to the target node is the code

As shown in the figure, each letter has its own code, and there is no ambiguity

meaning

Compress the text

Use procedures to achieve the Huffman tree coding

The difficulties in

1, how to count the number of characters

Let’s say I have a set, and I’m going to put what I’ve walked through

How do I set the counter for each character

Set up a HashMap for statistics

steps

1. Obtain the leaves needed to form the Huffman tree

2. Use these nodes to construct a Huffman tree

3. Encoding the Huffman tree (involving traversal recursion)

4. Compress the generated code set (compress the binary code into a base 10 byte group)

Code implementation

public class HuffManCode { public static void main(String[] args) { String s = "i like like like java do you like a java"; List<Byte> encoding = encoding(s); System.out.println(" Length of text before compression: "+s.length()); System.out.println(" The length of the text before compression is: "+encoding.size()+". "+ (double-.valueof (s.length() - encoding.size())/double-.valueof (s.Length ()) * 100) + "%"); } private static List<Byte> Encoding (String s) {Byte [] bs = s.get_bytes (); List<HuffManTree> nodes = new ArrayList<>(); List<Byte> bytes = new ArrayList<>(); Map<Byte,Integer> flags = new HashMap<>(); NodeBuild (flags,bytes, Nodes,bs); HuffManTree = huffmanBuild(Nodes); // Set codec Map<Byte,String> Results = new HashMap<>(); HuffmanEncoding (huffManTree, results,""); Results. ForEach ((k,v) -> system.out. println(" data: "+k+"); The corresponding encoding value is: "+v)); Return zip(bs,results); return zip(bs,results); } /** * get the number of leaves needed to form the Huffman tree * @param flags * @param bytes into the result * @param nodes in the result set * @param BS raw data */ private static void nodeBuild(Map<Byte,Integer> flags, List<Byte> bytes,List<HuffManTree> nodes, byte[] bs) { for (byte b : Bs) {if (bytes.contains(b)) {// indicates that flags.put(b, flags.get(b)+1); continue; } // indicates the first traversal to flags.put(b, 1); bytes.add(b); } flags.forEach((k,v) -> nodes.add(new HuffManTree(k,v))); } private static List<Byte> zip(Byte [] bs, Map<Byte,String> results) {// Replace the original encoding StringBuffer sb = new StringBuffer(); List<Byte> bytes = new ArrayList<>(); System.out.print(" original data is: "); for (byte b : bs) { System.out.print(b + "\t"); } System.out.println(); // Replace the values of the original byte array with the corresponding encoding for (byte b: bs) {sb.append(results.get(b)); } String s; for (int i = 0; i < sb.length(); i+=8) { s = i+8 < sb.length() ? sb.substring(i,i+8) : sb.substring(i,sb.length()); byte a = (byte)Integer.parseInt(s, 2); bytes.add(a); } System.out.println(bytes); System.out.println(sb); System.out.println(" +sb.length()); return bytes; } @param huffManTree huffManTree @param Results hash table @param s record value */ private static void HuffmanEncoding (HuffManTree HuffManTree, Map<Byte,String> results, String s) { // if (huffmantree.b, s) {// if (huffmantree.b, s) {// If (huffmantree.b, s); } if (huffManTree.left ! HuffmanEncoding (huffManTree. Left, results, s + "0"); // Set huffmanEncoding(huffManTree. Left, results, s + "0"); } if (huffManTree.right ! = null) { huffmanEncoding(huffManTree.right, results, s + "1"); }} private static HuffManTree huffmanBuild(List<HuffManTree> List) {// Need to implement the Comparable interface to collections.sort (List);  while (list.size() > 1) { HuffManTree leftNode = list.get(0); HuffManTree rigtNode = list.get(1); HuffManTree parent = new HuffManTree(leftNode.weight + rigtNode.weight); // Create a binary tree parent. Left = leftNode; parent.right = rigtNode; list.remove(leftNode); list.remove(rigtNode); list.add(parent); Collections.sort(list); // Sort existing Collections. } // The last thing left is the head node of the Huffman tree system.out.println (" the tree was successfully constructed, the preceding traversal result is as follows "); preTraversal(list.get(0)); return list.get(0); } private static void preTraversal(HuffManTree node) { if (node ! = null) { System.out.println(node); } if (node.left ! = null) { preTraversal(node.left); } if (node.right ! = null) { preTraversal(node.right); }}}Copy the code

Huffman decoding

If you can do it all, you can do it the other way around

steps

1. Create a decoding set according to results of the encoding set

2. Convert the given byte encoding set to an 8-bit binary string

3, the binary string will be decoded according to the decoding set to get byte set

4. Convert the byte collection into a byte array

Code implementation

/** * @param results */ private static String decoding(List<Byte> bytes, Map<Byte,String> results) {// Decoding = new HashMap<>(); results.forEach((k,v) -> decoding.put(v,k)); StringBuilder sb = new StringBuilder(); for (int i = 0; i < bytes.size(); i++) { byte b = bytes.get(i); String = integer.tobinaryString (b); if (b < 0) { string = string.substring(string.length() - 8); } // indicates an 8-bit integer, which is not high enough to fill 0, and the last digit is positive. = bytes.size() - 1 && b > 0) { string = String.format("%08d",Integer.parseInt(string)); } sb.append(string); } String result = sb.toString(); // Create result set String temp = ""; List<Byte> byteResults = new ArrayList<>(); char[] array = result.toCharArray(); For (char c: array) {temp += c; Byte b = decoding.get(temp); if (b ! = null) { byteResults.add(b); temp = ""; Byte [] bs = new byte[byteResults.size()]; for (int i = 0; i < bs.length; i++) { bs[i] = byteResults.get(i); } return new String(bs); }Copy the code

Huffman encrypts the file

I/O stream into bytes, passed into the encoding method, get new bytes and encoding set, write into the object stream. Similarly, after reading bytes and encoding sets by object stream, the corresponding byte data is obtained by passing the decoding method

You can go to git to see the source code

Sequential storage of binary trees

It’s used when you’re doing heap sort

A binary tree is converted from an array of nodes in a set of contiguous storage cells

The sequential storage binary tree is characterized by

Sequential binary trees usually consider only complete binary trees
The left child of the NTH element is 2 times n plus 1
The right child of the NTH element is 2 times n plus 2
The parent of the NTH element is (n-1) /2
Where n is the number of elements in the binary tree, starting from 0

With these rules, it’s easy to write implementation code

An array of values is printed as a number traversal, such as pre-traversal code

/ / the index for the array subscript public void preOrder (int [] a, int index) {if (a = = null | | a. ength = = 0) {System. Out. Println (" array is empty, No need to traverse "); return; } System.out.println(a[index]); If ((2*index + 1) < a.length) {// if (2*index + 1) < a.length) { } if ((2*index + 2) < a.length) {// select preOrder(a, 2*index + 2); }}Copy the code

Cue binary tree

Relevant concepts

A node may have 0-2 null pointer fields. The null pointer fields = node +1, that is, n+1

How do you figure it out?

Because n nodes have 2N Pointers, and because n nodes have N-1 edges (lines between nodes are called edges, for example, two nodes have only one edge, three have two edges, and so on), the remaining empty chain fields are 2n-(n-1)= N +1, that is, N +1 empty pointer fields (edges indicate pointer dependence, A node has at most two edges, subtract the related edges (n-1), and the remaining N +1 is the null pointer field (n+1).

The binary tree of clue solves the problem that the node can not be directly found in a certain traversal sequence of the forward and subsequent nodes, and the problem of finding the left and right children of the binary list is difficult. The binary tree of clue is divided into pre-order cueing, middle-order cueing and post-order cueing, which are realized by different logic.

Binary sort tree

Concept, any non-leaf node, its left child is smaller, its right child is larger

Now, given an array, build the values into a binary sort tree

Code implementation

public static Node buildTree(int[] a) { Node node = new Node(a[0]); for (int i = 1; i< a.length; i++) { int temp = a[i]; findNullPoint(temp, node); } return node; } private static void findNullPoint(int a, Node node) { if (a <= node.value) { if (node.leftNode == null) { node.leftNode = new Node(a); return; } findNullPoint(a, node.leftNode); } if (a > node.value) { if (node.rightNode == null) { node.rightNode = new Node(a); return; } findNullPoint(a, node.rightNode); }}Copy the code

Delete nodes

Consider three scenarios

The deleted node has no child nodes
The deleted node has only one child node
The deleted node has two children

handling

Delete directly (no child nodes)
Point the parent of a deleted node to its child (only one child)
If the deleted node is the left child of the parent, replace it with the right-most subtree of the deleted node (traversing all the way to the right)
If you delete the right child of the parent node of the deleted node, the deletion position is replaced by the leftmost subtree of the deleted node

The difficulties in

1. What should be done when the deleted node has two child nodes

Put the values of all nodes under that node into an array, and then rebuild the tree node and put it under the parent node.

The second method is to find the smallest node N in the right subtree of the node to be deleted, and then take out a node and make it equal to node N. The left subtree points to the left subtree to be deleted, and the right subtree points to the right subtree to be deleted. Of course, if the node to be deleted has a right subtree, then link its parent node to it, as shown in the figure

From The Fourth Edition of Algorithms

Code implementation

// Delete node, need to consider the leaf node, have a child node, Public static void delete(Node Node, Node deleteNode) {if (deletenode.value == node.value) {// Indicates that the root Node is deleted. Return system.out. println(" Root cannot be removed!" ); return; } if (deletenode.value < node.value) {if (node.leftNode == null) {system.out.println (" no node to delete "); return; } if (node.leftNode.value == deletenode. value) {// If (node.leftNode.leftNode == null && Node.leftnode. rightNode == null) {// Specify a leaf node and set it to null. } else if(node.leftNode.leftNode ! = null && node.leftNode.rightNode ! = null) {// There are two children buildSort(node.leftNode); list.remove(Integer.valueOf(node.leftNode.value)); int[] temp = new int[list.size()]; for (int i = 0; i < list.size(); i++) { temp[i] = list.get(i); } Node tempNode = buildTree(temp); node.leftNode = tempNode; } else if (node.leftNode.leftNode ! = null) {// There is only one left child node, replace it with node.leftNode = node.leftNode.leftNode; } else {// There is only one right child, replace it with node.leftNode = node.leftNode.rightNode; } return; } delete(node.leftNode, deleteNode); return; } if (deletenode.value > node.value) {if (node.rightNode == null) {system.out.println (" no node to delete "); return; } if (node.rightNode.value == deletenode.value) {// If (node.rightNode.leftNode == null && Node.rightnode. RightNode == null) {// Specify a leaf node and set it to null. } else if(node.rightNode.leftNode ! = null && node.rightNode.rightNode ! = null) {// Specify two children buildSort(node.rightNode); list.remove(Integer.valueOf(node.rightNode.value)); int[] temp = new int[list.size()]; for (int i = 0; i < list.size(); i++) { temp[i] = list.get(i); } Node tempNode = buildTree(temp); node.rightNode = tempNode; } else if (node.rightNode.leftNode ! = null) {// Have only one left child node, replace it with node.rightNode = node.rightNode.leftNode; } else {// There is only one right child, replace it with node.rightNode = node.rightNode.rightNode; } return; } delete(node.rightNode, deleteNode); return; }} public static void buildSort(Node Node) {if (node.getLeftNode()! =null) { buildSort(node.getLeftNode()); } // List is the global static variable list.add(node.getValue()); If (node.getrightNode ()! =null) { buildSort(node.getRightNode()); }}Copy the code

Balanced binary tree (AVL)

Possible problems with binary trees (O (N) complexity)

This configuration is like a linked list

More like a single linked list, the query speed is significantly reduced

Solution: Balanced binary tree (AVL)

Why is it called AVL? (understand)

The highly balanced binary tree, also known as AVL tree according to the Scientist’s English name, was proposed by the former Soviet Union mathematicians AD Else-Velskil and Landis in 1962. I was wondering, how do you balance binary trees without B

Public static Node buildBalanceTree(int[] a) {Node Node = new Node(a[0]); int status; for (int i = 1; i < a.length; i++) { int temp = a[i]; Node.findNullPoint(temp, node); // Turn (node); } return node; }Copy the code

The characteristics of

The absolute value of the height difference between the left and right subtrees cannot exceed 1, and both subtrees are balanced binary trees

Balanced binary tree implementation methods include: red black tree, AVL (algorithm), scapegoat tree, Treap, stretch tree and so on.

Related concepts: sinistral, dextral, dual

The AVL pairs must be rotated twice to achieve equilibrium

The right subtree is high. Rotate it left

On the contrary, if the left subtree is of good height, rotate it right

The purpose of rotation: To reduce the height of the tree (not for good looks)

If the condition of a tree at this time is as above and the right subtree is high, the left rotation operation is carried out, which is divided into 6 steps

1, new a node, the value of the current node (default root node)

2. Point the left subtree of the new node to the left child of the current node

3. Point the right child of the new node to the left child of the right child of the current node

4. Change the value of the current node to the value of the right subtree

5. Point the left subtree of the current node to the new node

6. Point the right subtree of the current node to the right child of the current node

/** * @param node */ private static void turnLeft(node node) { Node temp = new Node(node.value); Temp. LeftNode = node.leftNode; temp. RightNode = node.rightNode.leftNode; // Set the new node's right subtree to the left subtree of the current node's right subtree. // change the value of the current node to the value of the current node's right subtree node node.value = node.rightNode.value; // set the left subtree of the current node to the new node node.leftNode = temp; RightNode = node.rightNode. RightNode; }Copy the code

You can turn it the other way around

/** * @param node */ private static void turnRight(node node) { Node temp = new Node(node.value); RightNode = node.rightNode; // Set the new node to the right subtree of the current node. Temp. LeftNode = node.leftNode.rightNode; // Set the left subtree of the new node to the right subtree of the current node. Node.value = node.leftNode.value; Node.rightnode = temp; // set the left subtree of the node to the left subtree of the node node.leftNode = node.leftnode. leftNode; }Copy the code

Conditions of rotation

The height difference is more than 1

The difficulties in

1. Determine the current tree height

 private static int getHeight(Node node) {
         return Math.max(node.leftNode == null ? 0 : getHeight(node.leftNode), node.rightNode == null ? 0 : getHeight(node.rightNode)) + 1;
     }
Copy the code

The beauty of this method is +1, if there is no +1 then it will be 0 when it returns the previous level, and the final result will always be 0, unchanged

/** * Check the tree status. 0: balanced binary tree * -1: left subtree height * 1: right subtree height * @param node * @return */ private static int isCheckNode(node node) {int lh = getLeftHeight(node); int rh = getRightHeight(node); if (lh > rh && lh - rh > 1) { return -1; } if(rh > lh && rh -lh > 1) { return 1; } return 0; }Copy the code

In the special case above, a rotation is not called a balanced binary tree, so a double rotation is required. It is necessary to make a judgment before rotation to see if double rotation is needed (one rotation is not enough, so two rotations are needed).

The difficulties in

1. Before left-rotation, determine whether the height of the left subtree of the right node of the current node is greater than that of the left subtree of the current node. If so, right-rotate the right subtree of the current node

2. Similarly, before right-rotation, judge whether the height of the right subtree of the left child of the current node is greater than that of the current node. If so, left-rotate the left subtree of the current node

Private static void turn(Node Node) {int status = isCheckNode(Node); If (status == -1) {// Perform a partial rotation if (getHeight(node.leftNode.rightNode) > getHeight(node.rightNode)) {// perform a partial rotation turnLeft(node.leftNode); } turnRight(node); } if (status == 1) {// Perform left rotation if (isCheckNode(node.rightNode.leftNode) > isCheckNode(node.leftNode)) {// perform partial rotation turnRight(node.rightNode); } turnLeft(node); }}Copy the code

Many tree

Why do we need multi-fork trees

Although the binary tree is relatively efficient, there are problems, the number of nodes = 2 to the height of -1. If the number of nodes is too many, multiple IO operations will be required during the construction of the binary tree. The speed will be affected, and the height will also be high, reducing the operation speed

Advantages of multi-fork trees

Reduce the height of the tree by reorganizing the nodes

The number of forks is the number of nodes

Designers of file systems and database systems use the principle of disk prefetch to set the size of a node to be equal to a page (usually 4k in size), so that each node can be fully loaded in only one IO. So B trees are widely used.

The 2-3 tree is the simplest b-tree structure and has the following characteristics

So what is a B tree?

B stands for balance, or equilibrium tree

1. All leaf nodes are in the same layer (also a characteristic of B-tree)

2. A node with two child nodes is called a two-node node, which has either no node or two child nodes

3. A node with three child nodes is called a two-node node. A three-node node has either no node or three child nodes

4. 2-3 tree is a tree composed of two nodes and three nodes

As is shown in

In addition to the two or three trees, there are two or three-four trees, and it’s the same thing

**B+ trees and B* trees**

B balanced, no B-tree, it’s a B-tree

Order of B tree: refers to the maximum number of nodes, for example, the order of 2-3 tree is 3

Data is distributed throughout the tree, that is, both leaf and non-leaf nodes store data

The search performance is equivalent to a binary search in the keyword set

B + tree is B variant of the tree, all the data stored in the leaf node, also called density index, and the list of keywords is ordered, can’t be in the leaf node, called the index data of the leaf node, not a leaf node data also called sparse index, so it is more suitable for the file system, so the tree B and B + tree each have use, Depending on the application scenario

Where does this idea come from, that given a single linked list with 27 items, it can be divided into 3 by 9 levels

The B* tree is a variant of the B+ tree in which Pointers to siblings are added to non-root and non-leaf nodes

Red-black tree (too complex, add code later)

Prerequisites: Binary sort tree (BST), balanced binary tree (AVL)

Similar to AVL, both are balanced binary trees. The difference is that AVL is limited by the height difference between the left and right subtrees not exceeding 1, so it is a global change, and performance problems will occur when the data quantity increases. The emergence of red-black trees solves this problem. It uses local changes to achieve a self-balance, relying on rotation and color change. The rotation operation has also been mentioned before, and color change is red to black, black to red. The hard part is when to spin? When does it change color? Because it is a kind of local self-equilibrium, it is not a perfect balanced binary search tree, but the black node layers of the left and right subtrees are equal, so we call this kind of equilibrium black perfect equilibrium

As with AVL trees, a rule is required to make a judgment, and if not, a balancing operation is performed

Red black trees have five rules to follow, or properties of red black trees

1. Nodes are either red or black.

2. The root node is black

3. Every leaf node is black.

4. Two children of each red node are black, and two consecutive red nodes cannot appear

5. Contain the same number of black nodes from any node to the leaf node

insert

Insert in accordance with the rules of the binary sorting tree to insert, insert one by one, after the insertion does not meet the conditions in balance. Insert nodes are red nodes

Discussion by scene

Scenario 1: The tree has no nodes at insertion time

Change the color of the red nodes

Scenario 2: Insert the value already exists

Find the value directly and reassign it

Scenario 3: The parent node is black during insertion

I can just insert it for the red-black tree

Scenario 4: The parent node is red during insertion

If property 4 is not satisfied, it can also be concluded that the inserted node must have a grandfather (the parent of the parent node) (according to property 2).

In the case of discussion

4.1: The uncle node is red

The current node is black red red, the easiest way to do this is red black red, and then on the left (note that uncle also needs to be black)

If the parent node of the PP node is black, no operation is required

If the parent node of PP node is red, it violates property 4 and needs to set PP node as the current node to continue the balancing process

4.2: The uncle node does not exist or is black and the parent node is the left child node

First of all, uncle cannot be a black node, otherwise it violates property 5

4.2.1: Insert the left child node of node P

What to do: First discoloration: the parent node becomes black, the grandfather is red, and then right-hand rotation

4.2.2: Insert the right child node of node P

Turn P left (as above), then change color, and finally turn PP right

4.3: The uncle node does not exist or is black, and the parent node is the right child node

4.3.1: Insert as left child node

4.3.2: Insert as right child node

Same thing, the other way around

Delete too complex, smooth and then add

Most of the above pictures come from the network and are deleted

Why is a tree a data structure

Common term for tree

Tree structure Java code implementation

Order traversal before, middle and after

Huffman tree (WPL smallest tree)

Huffman coding

meaning

steps

Code implementation

Huffman decoding

steps

Code implementation

Huffman encrypts the file

Sequential storage of binary trees

Cue binary tree

Binary sort tree

Delete nodes

Balanced binary tree (AVL)

The characteristics of

Many tree

B+ trees and B* trees

Red-black tree (too complex, add code later)

insert

Related Posts

An interaction design document that both upstream and downstream love to read

An example of the Python automatic o&M deployment project tool Fabric

OA system of file management, so that the file work simple and complex

**B+ trees and B* trees**