preface
This article is mainly for self-study, reference is b station liu Si source video, here is for their own future study (like a lack of a red black tree to delete).
The definition of the tree
(2) Root: The node at the top of the tree is called root. A tree has only one root, and if a collection of nodes and edges is to be called a tree, there must be one and only one path from the root to every other node. A is the root node.
Parent node: If a node has children, the node is called the parent node of its children
(4) Child nodes: The nodes of a node’s subtree are called the child nodes of the node. F and G are children of C.
(5) Sibling nodes: nodes with the same parent node are called sibling nodes; F and G nodes are siblings of each other.
⑥ leaf node: nodes without child nodes are called leaf nodes, also known as leaf nodes. For example, H, E, F, and G in the figure above are leaf nodes.
Subtree: Each node can be used as the root of a subtree, and it and all its children, the children of the child node, and so on, are contained in the subtree.
(8) Node hierarchy: start from the root, the root is the first layer, the child node of the root is the second layer, and so on.
⑨ depth: For any node N, the depth of n is the unique path length from the root to n, and the depth of the root is 0. (Viewed from above)
⑩ Height: For any node N, the height of n is the longest path from n to a leaf, and the height of all leaves is 0. (Viewed from bottom up)
3. Binary search tree
Binary tree: Each node of a tree can have a maximum of two child nodes.
The first figure B node has DEF three child nodes, so it is not a binary tree and is called a multi-path tree. The second figure is a binary tree with only two nodes per node at most, and the child nodes of the binary tree are called “left child node” and “right child node”.
Binary search tree: If we add an extra condition to binary trees, we get a special kind of binary tree called binary search tree.
** Binary search tree requires: ** If its left subtree is not empty, the value of all nodes in the left subtree is less than the value of its root node; If its right subtree is not empty, the value of all nodes in the right subtree is greater than the value of its root node. Its left and right subtrees are also binary sort trees respectively.
Binary search tree – Find nodes: To find a node, we must start at the root. (1) If the search value is larger than the current node value, search the right subtree; ② The search value is equal to the current node value, stop the search (termination condition); (3) If the search value is less than the current node value, search the left subtree;
Binary search tree – Insert node: To insert a node, you must first find the insert location. Similar to the search operation, due to the particularity of binary search tree, the node to be inserted needs to be compared from the root node. If the node is smaller than the root node, it is compared with the left subtree of the root node; otherwise, it is compared with the right subtree. Until the left subtree is empty or the right subtree is empty, the node is inserted to the corresponding empty position.
Binary search tree – Traversal nodes:To traverse a tree is to visit each node of the tree in a particular order. More commonly used are pre-order traversal, order traversal and order traversal. The most commonly used binary search tree is middle order traversal. (1), middle order traversal: left subtree — “root node –” right subtree ②, front order traversal: root node — “left subtree –” right subtree ③, after order traversal: left subtree — “right subtree –” root node
Binary search tree – Find maximum and minimum valuesTo find the minimum, find the left node of the root, and then go all the way to the left node of this left node, until you find a node that has no left node, and that node is the minimum. Similarly, to find the maximum, keep looking for the right node of the root node until there are no right nodes, which is the maximum.
Delete the node that has no child nodeTo remove a leaf node, simply change the parent reference value of the node to NULL.
We know that nodes in a binary search tree are arranged according to keywords, and the second-highest keyword of a node is its middle-order traversal successor node. By replacing the deleted node with a successor node, it is clear that the binary search tree is still in order.
④ is it necessary to delete it? From the above discussion on deletion classification, we find that deletion is actually quite complicated. In fact, we can not actually delete the Node, just need to add an identification field isDelete in the Node class. When this field is true, it means that the Node has been deleted, otherwise, it is not deleted. This way, deleting nodes does not change the structure of the tree. The impact is that the query needs to determine whether the node has been deleted.
Binary search tree-time complexity analysis:
1. Review the classic binary search algorithm [1,2,3,4,5,6,7,8,9… 100] Violent algorithm: good luck performance, bad luck performance crash.. Binary search algorithm: The data source must be an ordered array, and the performance is very good, each iteration of the query can exclude half of the results.
2. What are the biggest defects of binary search algorithm? Force a dependency on ordered arrays to perform well.
3. What are the drawbacks of arrays? There’s no way to insert quickly, no way to expand
4. So how can we have the high performance of binary lookup and the flexibility of linked lists? Binary search tree!! 5. Time complexity calculation process of binary search algorithm
Number of queries Number of remaining elements to be queried 1N/22N/(2^2)3N/(2^3)KN/(2^K)
It can be seen from the above table that N/(2^K) must be greater than or equal to 1, that is, N/(2^K)>=1. We calculate the time complexity according to the worst case, that is, we only find the data we want when we look up the last remaining number. Is N / 2 ^ (K) = 1 = > 2 ^ K = N = > K = log2 (N) = > : the binary search algorithm time complexity O (log2 (N)) = > O (logN)
Fatal defect of ordinary binary search tree:
How to solve the problem of binary search tree degenerating into linear linked list? If the tree can automatically balance the two sides when inserting elements, it will maintain good lookup performance.
AVL tree Introduction:
What are the characteristics of AVL trees?
1. All features of binary search tree.
2. The height difference between the left and right subtrees of each node is at most equal to 1.
Compliance error
A balanced tree ensures that there are no large numbers of nodes leaning to one side! How to build an AVL tree? (That’s beside the point… This is not the content of this tutorial, if you are interested, please do your own search.
Why do you need a red black tree when you have a balanced tree? Although balanced tree solves the bintree degradation for approximate list shortcomings, to be able to find time control in O (logn), but it is not the best, because the left child of each node is balanced tree request tree and the height of the right subtree is poor at most equal to 1, this request is too strict, lead to every time to insert/delete nodes, Almost all of them break the second rule of a balanced tree, and we all need to make adjustments by turning left and right to make it a balanced tree again.
Obviously, the performance of the balanced tree would be compromised if it had to be adjusted frequently in a scenario where insertion and deletion were frequent. To solve this problem, red-black trees were created!
Properties of red-black trees:
Red-black tree example diagram
Property 2: The root node is black.
Property 3: Each leaf node (NIL) is black.
Property 4: Two children of every red node must be black. You can’t have two red nodes connected.
Property 5: The path from any node to each leaf node contains the same number of black nodes. Commonly known as: black high! From property 5, it can be inferred that:
Property 5.1: If a node has a sunspot node, then the node must have two child nodes
Red-black tree is not a perfectly balanced binary search tree. It can be seen from the figure that the left subtree of root node P is obviously higher than the right subtree, but the number of black nodes of the left and right subtrees is the same, that is, the path from any node to every leaf node contains the same number of black nodes (property 5). So we call it a red-black tree and this equilibrium is black perfect equilibrium.
So long as the tree satisfies the above properties, the tree is approaching equilibrium. Don’t ask why, the scientist who invented the red black tree is so awesome!
What does a red-black tree need to be self-balancing? Three operations: left rotation, right rotation and color change. 1. Color change: the color of the node changes from red to black or from black to red. 2. Left-rotation: a node is taken as the fulcrum (rotation node), and its right child becomes the parent of the rotation node, the left child of the right child becomes the right child of the rotation node, and the left child remains unchanged. 3. Right rotation: a node is taken as the fulcrum (rotation node), and its left child becomes the parent of the rotation node, the right child of the left child becomes the left child of the rotation node, and the right child remains unchanged
Left-handed graphic
Right here
** Red-black tree lookup: **
Red-black tree insertion:
The insert operation consists of two parts: 1. Find the insert position. 2
Note: insert node, must be red color{red}{red} red, the reason is simple, red when the parent node (if any) is black, the black balance of the red-black tree is not broken, do not need to do self-balance operation. But if the insertion node is black, then the black node in the subtree where the insertion is always one more, so it has to be self-balanced.
Before we start each scenario, let’s make a pact:
Red-black tree insertion node scenario analysis
Scenario 1: The red-black tree is empty
In the simplest case, we can just use the insert node as the root node and note that by red-black tree property 2, the root node is black. I also need to make the insert node black.
Scenario 2: The Key inserted into the node already exists
Process: Update the value of the current node to the value of the inserted node
Scenario 3: The parent of the inserted node is black
Since the nodes inserted are red, when black nodes are inserted, the balance of the red-black tree will not be affected. It can be directly inserted without self-balancing.
Scenario 4: The parent node of the inserted node is red
Again, remember property 2 of a red-black tree: the root is black. If the parent of the inserted node is a red node, then that parent cannot be the root, so the inserted node always has a grandparent. This is critical because subsequent rotation operations will definitely require grandparent.
Insert scenario 4.1: The uncle node exists and is red
According to property 4 of red-black tree, red nodes cannot be connected ==> Grandfather nodes must be black nodes.
Because you can’t have two connected red nodes at the same time. Then the number of red and black layers to be inserted into the subtree is: black, red and red. Obviously the easiest way to do this is to change it to: red black red:
1. Change the color of P and U to black
2. Change the PP to red
3. Set the PP to the current node and perform subsequent operations
Insert scenario 4.2: The uncle node does not exist or is black, and the father node of the insert node is the left child of the grandfather node
Note: From the purely insertion point, the uncle node is not a NIL node, otherwise it breaks red-black tree property 5 and this path will have one more black node than the other paths.
Insert scenario 4.2.1: Newly inserted node, the left child node of its parent node (LL red case)
2. Perform operations on the PP nodeRight hand
Insert scenario 4.2.2: Newly inserted node, the right child node of its parent node (LR red case)
1. Left-handed rotation of P
2. Set P to the current node to obtain LL red
3. Treat as LL red (1. Change color 2. Dextral PP)
Insertion scenario 4.3: The uncle node does not exist or is black, and the father node of the inserted node is the right child of the grandfather node
This scenario corresponds to scenario 4.2, but the direction is reversed and we look at the picture directly.
Insert scenario 4.3.1: The newly inserted node is the right child of its parent node (RR red)
1. Change color: set P to black and PP to red
2. Rotate the PP node left
Insert scenario 4.3.2: Newly inserted node, the left child of its parent node (RL red)
1. Right-handed rotation of P
2. Set P to the current node to obtain RR red
3. Treat as RR red (1. Change color 2. Left-handed PP)
Handwritten red black tree
ParentOf (node),isRed(node),setRed(node),setBlack(node),inOrderPrint(); 4. LeftRotate (node) 5. RightRotate (node) 6. Public insert interface method definition: insert(K key, V value); Internal insert interface method definition: insert(RBNode node); InsertFlxUp (RBNode node) 9 Test red-black tree correctness
Actual practice handwriting red black tree, I personally handwritten success, but I do not write notes, so or the original author of the example posted up.
重点！！！说在前面，有同学反映 红黑树 测试 2,4,6,8,10,12,14...就不平衡了...
这里说下原因：因为这是课程源码，考虑的并没那么多 我比对节点大小时 直接使用的是 node.key.compareTo(parent.key);
明眼的同学都能看出来，这个其实是按照字符串比对的！ 所以，大家尽量使用 a,b,c,d,e,f,g,h,i...这种风格去测试...
或者自己改改这块的逻辑，可以去参考HashMap的实现去改。
package com.study.struct;
/**
* ClassName: TreeOperation
* Description:
* date: 2020/1/12 16:46
*
* @author 巍巍老师
* @since 1.0.0
*/
public class TreeOperation {
/*
树的结构示例：
1
/ \
2 3
/ \ / \
4 5 6 7
*/
// 用于获得树的层数
public static int getTreeDepth(RBTree.RBNode root) {
return root == null ? 0 : (1 + Math.max(getTreeDepth(root.getLeft()), getTreeDepth(root.getRight())));
}
private static void writeArray(RBTree.RBNode currNode, int rowIndex, int columnIndex, String[][] res, int treeDepth) {
// 保证输入的树不为空
if (currNode == null) return;
// 先将当前节点保存到二维数组中
res[rowIndex][columnIndex] = String.valueOf(currNode.getKey() /*+ "-" + (currNode.isColor() ? "R" : "B") + ""*/);
// 计算当前位于树的第几层
int currLevel = ((rowIndex + 1) / 2);
// 若到了最后一层，则返回
if (currLevel == treeDepth) return;
// 计算当前行到下一行，每个元素之间的间隔（下一行的列索引与当前元素的列索引之间的间隔）
int gap = treeDepth - currLevel - 1;
// 对左儿子进行判断，若有左儿子，则记录相应的"/"与左儿子的值
if (currNode.getLeft() != null) {
res[rowIndex + 1][columnIndex - gap] = "/";
writeArray(currNode.getLeft(), rowIndex + 2, columnIndex - gap * 2, res, treeDepth);
}
// 对右儿子进行判断，若有右儿子，则记录相应的"\"与右儿子的值
if (currNode.getRight() != null) {
res[rowIndex + 1][columnIndex + gap] = "\\";
writeArray(currNode.getRight(), rowIndex + 2, columnIndex + gap * 2, res, treeDepth);
}
}
public static void show(RBTree.RBNode root) {
if (root == null) System.out.println("EMPTY!");
// 得到树的深度
int treeDepth = getTreeDepth(root);
// 最后一行的宽度为2的（n - 1）次方乘3，再加1
// 作为整个二维数组的宽度
int arrayHeight = treeDepth * 2 - 1;
int arrayWidth = (2 << (treeDepth - 2)) * 3 + 1;
// 用一个字符串数组来存储每个位置应显示的元素
String[][] res = new String[arrayHeight][arrayWidth];
// 对数组进行初始化，默认为一个空格
for (int i = 0; i < arrayHeight; i ++) {
for (int j = 0; j < arrayWidth; j ++) {
res[i][j] = " ";
}
}
// 从根节点开始，递归处理整个树
// res[0][(arrayWidth + 1)/ 2] = (char)(root.val + '0');
writeArray(root, 0, arrayWidth/ 2, res, treeDepth);
// 此时，已经将所有需要显示的元素储存到了二维数组中，将其拼接并打印即可
for (String[] line: res) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < line.length; i ++) {
sb.append(line[i]);
if (line[i].length() > 1 && i <= line.length - 1) {
i += line[i].length() > 4 ? 2: line[i].length() - 1;
}
}
System.out.println(sb.toString());
}
}
}
package com.study.struct;
/**
* ClassName: RBTree
* Description:
* date: 2020/1/12 11:07
*
* ①创建RBTree，定义颜色
* ②创建RBNode
* ③辅助方法定义：parentOf(node)，isRed(node)，setRed(node)，setBlack(node)，inOrderPrint(RBNode tree)
* ④左旋方法定义：leftRotate(node)
* ⑤右旋方法定义：rightRotate(node)
* ⑥公开插入接口方法定义：insert(K key, V value);
* ⑦内部插入接口方法定义：insert(RBNode node);
* ⑧修正插入导致红黑树失衡的方法定义：insertFIxUp(RBNode node);
* ⑨测试红黑树正确性
*
*
* @author 巍巍老师
* @since 1.0.0
*/
public class RBTree <K extends Comparable<K>, V> {
//定义颜色常量
private static final boolean RED = true;
private static final boolean BLACK = false;
//红黑树的树根
private RBNode root;
public RBNode getRoot() {
return root;
}
/**
* 公开的插入接口
* @param key 键
* @param value 值
*/
public void insert(K key, V value) {
RBNode node = new RBNode();
node.setKey(key);
node.setValue(value);
node.setColor(RED);
insert(node);
}
/**
* 内部插入接口定义
*/
private void insert(RBNode node) {
//1.找到插入的位置
RBNode parent = null;
RBNode x = this.root;
while(x != null) {
parent = x;
//a > b 则返回 1，否则返回 -1 ，相等返回0
int cmp = node.key.compareTo(parent.key);
if(cmp < 0) {
x = x.left;
} else if(cmp == 0) {
parent.setValue(node.value);
return;
} else {
x = x.right;
}
}
node.parent = parent;
if(parent != null) {
if(node.key.compareTo(parent.key) < 0) {
parent.left = node;
} else {
parent.right = node;
}
} else {
this.root = node;
}
//插入之后需要进行修复红黑树，让红黑树再次平衡。
insertFixUp(node);
}
/**
* 插入后修复红黑树平衡的方法
* |---情景1：红黑树为空树
* |---情景2：插入节点的key已经存在
* |---情景3：插入节点的父节点为黑色
*
* 情景4 需要咱们去处理
* |---情景4：插入节点的父节点为红色
* |---情景4.1：叔叔节点存在，并且为红色（父-叔 双红）
* |---情景4.2：叔叔节点不存在，或者为黑色，父节点为爷爷节点的左子树
* |---情景4.2.1：插入节点为其父节点的左子节点（LL情况）
* |---情景4.2.2：插入节点为其父节点的右子节点（LR情况）
* |---情景4.3：叔叔节点不存在，或者为黑色，父节点为爷爷节点的右子树
* |---情景4.3.1：插入节点为其父节点的右子节点（RR情况）
* |---情景4.3.2：插入节点为其父节点的左子节点（RL情况）
*/
private void insertFixUp(RBNode node) {
RBNode parent = parentOf(node);
RBNode gparent = parentOf(parent);
//存在父节点且父节点为红色
if(parent != null && isRed(parent)) {
//父节点是红色的，那么一定存在爷爷节点
//父节点为爷爷节点的左子树
if(parent == gparent.left) {
RBNode uncle = gparent.right;
//4.1：叔叔节点存在，并且为红色（父-叔 双红）
//将父和叔染色为黑色，再将爷爷染红，并将爷爷设置为当前节点，进入下一次循环判断
if(uncle != null && isRed(uncle)) {
setBlack(parent);
setBlack(uncle);
setRed(gparent);
insertFixUp(gparent);
return;
}
//叔叔节点不存在，或者为黑色，父节点为爷爷节点的左子树
if(uncle == null || isBlack(uncle)) {
//插入节点为其父节点的右子节点（LR情况）=>
//左旋（父节点），当前节点设置为父节点，进入下一次循环
if(node == parent.right) {
leftRotate(parent);
insertFixUp(parent);
return;
}
//插入节点为其父节点的左子节点（LL情况）=>
//变色（父节点变黑，爷爷节点变红），右旋爷爷节点
if(node == parent.left) {
setBlack(parent);
setRed(gparent);
rightRotate(gparent);
}
}
} else {//父节点为爷爷节点的右子树
RBNode uncle = gparent.left;
//4.1：叔叔节点存在，并且为红色（父-叔 双红）
//将父和叔染色为黑色，再将爷爷染红，并将爷爷设置为当前节点，进入下一次循环判断
if(uncle != null && isRed(uncle)) {
setBlack(parent);
setBlack(uncle);
setRed(gparent);
insertFixUp(gparent);
return;
}
//叔叔节点不存在，或者为黑色，父节点为爷爷节点的右子树
if(uncle == null || isBlack(uncle)) {
//插入节点为其父节点的左子节点（RL情况）
//右旋（父节点）得到RR情况，当前节点设置为父节点，进入下一次循环
if(node == parent.left) {
rightRotate(parent);
insertFixUp(parent);
return;
}
//插入节点为其父节点的右子节点（RR情况）=>
//变色（父节点变黑，爷爷节点变红），右旋爷爷节点
if(node == parent.right) {
setBlack(parent);
setRed(gparent);
leftRotate(gparent);
}
}
}
}
setBlack(this.root);
}
/**
* 左旋方法
* 左旋示意图：左旋x节点
* p p
* | |
* x y
* / \ ----> / \
* lx y x ry
* / \ / \
* ly ry lx ly
*
* 左旋做了几件事？
* 1.将y的左子节点赋值给x的右边，并且把x设置为y的左子节点的父节点
* 2.将x的父节点（非空时）指向y，更新y的父节点为x的父节点
* 3.将y的左子节点指向x，更新x的父节点为y
*/
private void leftRotate(RBNode x) {
RBNode y = x.right;
//将y的左子节点赋值给x的右边
x.right = y.left;
//并且把x设置为y的左子节点的父节点
if(y.left != null) {
y.left.parent = x;
}
//将x的父节点（非空时）指向y
if(x.parent != null) {
//如果x是parent左子树，则把y安放到parent的左边
if(x.parent.left == x) {
x.parent.left = y;
} else {//否则把y安放到parent的右边
x.parent.right = y;
}
//更新y的父节点为x的父节点
y.parent = x.parent;
} else {
this.root = y;
this.root.parent = null;
}
y.left = x;
x.parent = y;
}
/**
* 右旋方法
* 右旋示意图：右旋y节点
*
* p p
* | |
* y x
* / \ ----> / \
* x ry lx y
* / \ / \
*lx ly ly ry
*
* 右旋都做了几件事？
* 1.将x的右子节点 赋值 给了 y 的左子节点，并且更新x的右子节点的父节点为 y
* 2.将y的父节点（不为空时）指向x，更新x的父节点为y的父节点
* 3.将x的右子节点指向y，更新y的父节点为x
*/
private void rightRotate(RBNode y) {
//1.将x的右子节点赋值给y的左子节点，并将y赋值给x右子节点的父节点（x右子节点非空时）
RBNode x = y.left;
y.left = x.right;
if(x.right != null) {
x.right.parent = y;
}
//2.将y的父节点p（非空时）赋值给x的父节点，同时更新p的子节点为x（左或右）
x.parent = y.parent;
if(y.parent != null) {
if(y.parent.left == y) {
y.parent.left = x;
} else {
y.parent.right = x;
}
} else {
this.root = x;
this.root.parent = null;
}
//3.将x的右子节点赋值为y，将y的父节点设置为x
x.right = y;
y.parent = x;
}
/**
* 获取当前节点的父节点
*/
private RBNode parentOf(RBNode node) {
if(node != null) {
return node.parent;
}
return null;
}
/**
* node节点是否为红色
* @return boolean true 表示是红色 false 表示不是红色
*/
private boolean isRed(RBNode node) {
if(node != null) {
return node.isColor() == RED;
}
return false;
}
/**
* 设置节点为红色
*/
private void setRed(RBNode node) {
if(node != null) {
node.setColor(RED);
}
}
/**
* 设置节点为黑色
*/
private void setBlack(RBNode node) {
if(node != null) {
node.setColor(BLACK);
}
}
/**
* 中序打印，可以将二叉查找树有顺序的打印出来
*/
public void inOrderPrint() {
if(this.root != null) {
inOrderPrint(this.root);
}
}
private void inOrderPrint(RBNode node) {
if(node != null) {
inOrderPrint(node.left);
System.out.println("key -> " + node.key + ", value -> " + node.value);
inOrderPrint(node.right);
}
}
/**
* node节点是否为黑色
* @return boolean true 表示是黑色 false 表示不是黑色
*/
private boolean isBlack(RBNode node) {
if(node != null) {
return node.isColor() == BLACK;
}
return false;
}
/**
* 红黑树Node
*/
static class RBNode<K extends Comparable<K>, V> {
//颜色
private boolean color;
//左子节点
private RBNode left;
//右子节点
private RBNode right;
//父节点
private RBNode parent;
//key
private K key;
//value
private V value;
public RBNode(boolean color, RBNode left, RBNode right, RBNode parent, K key, V value) {
this.color = color;
this.left = left;
this.right = right;
this.parent = parent;
this.key = key;
this.value = value;
}
public RBNode() {
}
public boolean isColor() {
return color;
}
public void setColor(boolean color) {
this.color = color;
}
public RBNode getLeft() {
return left;
}
public void setLeft(RBNode left) {
this.left = left;
}
public RBNode getRight() {
return right;
}
public void setRight(RBNode right) {
this.right = right;
}
public RBNode getParent() {
return parent;
}
public void setParent(RBNode parent) {
this.parent = parent;
}
public K getKey() {
return key;
}
public void setKey(K key) {
this.key = key;
}
public V getValue() {
return value;
}
public void setValue(V value) {
this.value = value;
}
}
/*****************************************************************************
* Print Method
*****************************************************************************/
public void padding ( String ch, int n ) {
int i;
for ( i = 0; i < n; i++ )
System.out.printf(ch);
}
void print_node (RBNode root, int level ) {
if ( root == null ) {
padding ( "\t", level );
System.out.println( "NIL" );
} else {
print_node ( root.right, level + 1 );
padding ( "\t", level );
if(root.color == BLACK) {
System.out.printf(root.key + "(" + (root.isColor() ? "红" : "黑") +")" + "\n");
} else
System.out.printf(root.key + "(" + (root.isColor() ? "红" : "黑") +")" + "\n");
print_node ( root.left, level + 1 );
}
}
void print_tree() {
print_node(this.root,0);
System.out.printf("-------------------------------------------\n");
}
}
package com.study.struct;
import java.util.Scanner;
/**
* ClassName: TestRBTree
* Description:
* date: 2020/1/12 16:07
*
* @author 巍巍老师
* @since 1.0.0
*/
public class TestRBTree {
public static void main(String[] args) {
RBTree<String, Object> rbt = new RBTree();
//测试输入：ijkgefhdabc
while(true) {
Scanner sc = new Scanner(System.in);
System.out.println("请输入key:");
String key = sc.next();
rbt.insert(key, null);
TreeOperation.show(rbt.getRoot());
}
}
}
Copy the code