Binary and red-black trees of the eight largest data structures in Java

Binary and red-black trees of the eight largest data structures in Java

A:

Data structure is the way that a computer stores and organizes data. It refers to the collection of data elements that have one or more specific relationships with each other.



Two: binary tree

Nodes: Typically represent entities. In Java object-oriented programming, nodes typically represent objects

Edges: Generally the only way to get from one node to another is to follow an edged path. In Java, references are commonly referred to.



1. The path: The path follows the edge of a node from one node to another, and the sequence of the nodes through it is called the “path”.

2. The root: The node at the top of the tree is called the root. A tree has only one root, and if a collection of nodes and edges is to be called a tree, then there must be one and only one path from the root to any other node. A is the root node.

3. The parent node: If a node contains children, this node is called the parent of its children; B is the parent of D.

4. The child nodes: The root node of the subtree of a node is called the child node of the node; D is a child of B.

5. Brother nodes: Nodes with the same parent are called sibling nodes; For example, D and E in the figure above are called sibling nodes.

6. Leaf nodes: A node without children is called a leaf node, also known as a leaf node. For example, H, E, F, and G in the figure above are leaf nodes

7. The subtree: Each node can be the root of a subtree, and it and all of its children, children of children, and so on are included in the subtree.

8. Hierarchy of nodes: The definition starts from the root, which is the first level, the children of the root are the second level, and so on.

The depth of the 9.: For any node n, the depth of n is the length of the unique path from root to n, and the depth of the root is 0;

10Height of the.: For any node n, the height of n is the longest path length from n to a leaf, and the height of all leaves is 0;

Binary tree features:

Binary tree: Each node of the tree can have at most two child nodes

Binary search tree: if its left subtree is not empty, then the value of all the nodes in the left subtree is less than the value of its root node; If its right subtree is not empty, then the value of all the nodes in the right subtree is greater than the value of its root node. Its left and right subtrees are binary sort trees, respectively.



Middle-order traversal: left subtree — root node — right subtree(Figure 4,5,8,9,10,11,15,20)

Preorder traversal: root node — left subtree — right subtree(Figure 10,8,4,5,9,15,11,20)

Back-order traversal: left subtree — “right subtree –” root node(Figure 5,4,9,8,11,20,15,10)

The implementation of binary tree increase, search, sort and so on

Public class MyTree {private Node Root; Public class Node {int data; Private Node LeftChild; Private Node RightChild; private Node RightChild; Public Node(int data) {this.data = data; } public void display() {System.out.println(data); }} // Find a node, we must start from the root node variable, 1 search value is greater than the current node, then search the right subtree, search value is equal to the current node value, stop searching, search value is less than the current node value, then search the left subtree; public Node find(int key) { Node current = root; while (current ! = null) {if (Current. Data > Key) {// Current = Current. LeftChild; } else if (Current. Data < Key) {// Current = Current. RightChild; } else { return current; } } return null; Public Boolean insert(int data) {Node newNode = newNode (data); If (root == null) {// The tree is empty, no node is left; return true; } else { Node current = root; Node parentNode = null; while (current ! = null) { parentNode = current; If (current.data > data) {// Current = current.leftChild; If (current == null) {parentNode.leftChild = newNode; return true; } } else { current = current.rightChild; If (current == null) {parentNode.rightChild = newNode; return true; } } } } return false; } public void InfixOrder (Node Current){if(Current! = null){ infixOrder(current.leftChild); System.out.print(current.data+" "); infixOrder(current.rightChild); }} public void preOrder(Node current){if(current! = null){ System.out.print(current.data+" "); preOrder(current.leftChild); preOrder(current.rightChild); }} public void PostOrder (Node current){if(current! = null){ postOrder(current.leftChild); postOrder(current.rightChild); System.out.print(current.data+" "); }} public Node findMax(){Node current = root; Node maxNode = current; while(current ! = null){ maxNode = current; current = current.rightChild; } return maxNode; } public Node findMin(){Node current = root; Node minNode = current; while(current ! = null){ minNode = current; current = current.leftChild; } return minNode; }}

call

MyTree myTree=new MyTree(); MyTree. INSERT (10); myTree. INSERT (10); myTree. myTree.insert(8); myTree.insert(15); myTree.insert(4); myTree.insert(9); myTree.insert(11); myTree.insert(20); myTree.insert(5); MyTree.infixOrder (myTree.find(10)); myTree.find(10); // myTree.preOrder(myTree.find(10)); MyTree.postOrder (myTree.find(10)); System.out.println(myTree.findMax().data); System.out.println(myTree.findmin ().data); System.out.println(myTree.find(9)); // result // result // result // result // result // result // result // result / 5 4 9 8 November 20 15 10 / / Max System. Out: 20 / / minimum System. Out: 4 / / gain values for 9 nodes, reference com. Ruan. Mygitignore. MyTree $Node @ c115983

Three: red-black trees

A Red-Black Tree “RBT” is a self-balancing (but not perfectly balanced) binary search Tree (BST). Each node in the Tree follows the following rules:

1. Each node is red or black

2. The roots of the tree are always black.

3. All the leaves are black. (The leaf is a NIL node)

4. Two children of each red node are black. There cannot be two consecutive red nodes on all paths from each leaf to the root.

5. Every path from the node (including the root) to any of its descendants NULL nodes (two empty nodes hanging below the leaf node and considered black) has the same number of black nodes



When we add data to the existing red-black tree, we may break the rules of the red-black tree

(1) Add a new node with the value of 14 into the original red-black tree:



(2) Insert a new node with value of 21 into the original red-black tree:



Since the parent node 22 is a red node, this situation breaks rule 4 of the red-black tree (two children of each red node are black) and must be adjusted to conform to the red-black tree rule again.

The ways of adjustment are:discoloration.Left rotation.Right rotation

Color:

To re-conform to the rules of the red-black tree, try turning the red nodes black, or turning the black nodes red.

The figure below represents a portion of the red-black tree. Note that node 25 is not the root node. Since node 21 and node 22 appear red continuously, which does not conform to rule 4, change node 22 from red to black:



This is not the end of the story, however, because rule 5 is broken by the addition of black nodes out of thin air, which in turn causes a chain reaction to change node 25 from black to red:



At this point, there is still no end, because node 25 and node 27 form two consecutive red nodes again, so we need to continue changing node 27 from red to black:



Left rotation:

Rotating the two nodes of the red-black tree counterclockwise causes the parent node to be replaced by its right child and it to become its left child. It’s weird, but look at the picture below:



In the picture, the child on the right takes the place of the child on the right, and the child on the left becomes the child on the right. This is a left rotation.

Right rotation:

Rotate the two nodes of the red-black tree clockwise so that the parent node is replaced by its left child and it becomes its right child. Look at the following picture:



In the picture, Y, the child on the left, takes the place of X, and X becomes the child on the right. This is a right rotation.

Let’s take the case of inserting node 21 as an example:

First, what we need to do is to change color, which is to change the color of node 25 and the node below it:



In this case, node 17 and node 25 are two consecutive red nodes, so turn node 17 into black node? I’m afraid not. Not only does this break rule 4, but according to rule 2 (the root node is black), it is also impossible to turn node 13 into a red node.

The problem cannot be solved by changing color. Let’s regard node 13 as X and node 17 as Y, and rotate left as shown in the schematic above:





Since the root node must be a black node, it needs to change color. The discoloration results are as follows:



Is that the end of it? Don’t. Because two paths (17->, 8->, 6-> NIL) have 4 black nodes, and the other paths have 3 black nodes, which does not comply with rule 5.

In this case, we need to view node 13 as X and node 8 as Y, and rotate right as shown in the previous diagram:





Finally, according to the rules to change color:



In this way, our red-black tree becomes regular-compliant again. The adjustment process of this example is relatively complex, and it goes through the following steps:

Color change -> left rotation -> color change -> right rotation -> color change

I think it can and can be done:



See blog:https://blog.csdn.net/qq_3661…

END: Give time to life, give time to civilization