An overview,
Red-black trees are self-balancing trees in computer science. Each node of a binary tree has an extra bit, which is usually interpreted as the node’s color (red or black). These color bits are used to ensure that the tree remains approximately balanced during insertion and deletion. Balance is preserved by drawing each node of the tree in one of two colors in a way that satisfies certain properties that collectively limit how unbalanced the tree can be at worst. When the tree is modified, the new tree is then rearranged and redrawn to restore the coloring properties. These properties are designed so that this rearrangement and recolor can be performed efficiently. The balance of the tree is not perfect, but it is sufficient to warrant a search in order log n time, where n is the total number of elements in the tree. Insert and delete operations, as well as tree rearrangement and recolor, are also performed in O(log n) time. Tracking the color of each node requires only 1 bit of information per node because there are only two colors. The tree does not contain any other red-black tree-specific data, so its memory footprint is almost the same as that of a classical (colorless) binary search tree. In many cases, additional information can be stored without additional storage costs.
Second, properties,
1. Each node is either red or black. 2. The root node is black. (The root node can always change from red to black, so this rule has no effect on analysis.) 3. All leaves (NIL) are black. 4. If the node is red, its two child nodes must be black. 5. From any node to any reachable leaf node (NIL), the path contains the same number of black nodes. (Extremely important, this ensures that red-black trees are self-balanced binary trees.)
Note:
1) Attributes 4 and 5 guarantee that red-black trees are self-balanced binary trees. Therefore, ensuring that red-black trees satisfy 4 and 5 can guarantee self-equilibrium.
2) In the path from root node to all leaf nodes in red-black tree, the longest path length is less than two times of the shortest path length.
3) Leaf node NIL: the parent pointer field of the root node of the previous binary tree, and the left and right child fields of the node; Sometimes when you reach the leaves, it’s empty. In red-black trees, the empty pointer field points to NIL nodes as leaf nodes.
3. Nodes and whole of red-black tree
Public class RedBlackTree<T extends Comparable<T>> {/** * static class RedBlackNode<T extends Comparable<T>> { T key; // Node value Boolean red; // is the red node RedBlackNode<T> parent; // RedBlackNode<T> leftChild; // parent RedBlackNode<T> rightChild; Public RedBlackNode() {} public RedBlackNode(T key) {this(); this.key = key; } public boolean isRed() { return red; } @Override public String toString() { return key + ""; } } private final RedBlackNode<T> NIL = new RedBlackNode<>(); Private RedBlackNode<T> root = NIL; // Root node private int size; Public RedBlackTree() {root.parent = NIL; root.leftChild = NIL; root.rightChild = NIL; } // Insert data public void insert(T key){} private void insert(RedBlackNode<T> node) {} // Insert correction private void InsertFixup (RedBlackNode<T> node) {} private void rightRotate(RedBlackNode<T> node) { LeftRotate (RedBlackNode<T> node) {} private Boolean isNil(RedBlackNode<T> node) {} public void leftRotate(RedBlackNode<T> node) { PreOrderErgodic (){} public void preOrderErgodic(RedBlackNode node){} public int getSize() {} // Remove node public Private void removeNode(RedBlackNode<T> v) {} Private void removeNode(RedBlackNode<T> v) { Private RedBlackNode<T> treeSuccessor(RedBlackNode<T> waitRemoveNode) { Private RedBlackNode<T> treeMinimum(RedBlackNode<T> node) {} private RedBlackNode<T> search(T key) {} }Copy the code4. Insert operation
Inserting nodes into a red-black tree is accomplished in two steps: inserting data and trimming the tree according to the properties of the red-black tree. Data is inserted in the same way as data is inserted in a binary tree. The new node must be a red node. To trim the tree according to the properties of the red-black tree is to carry out color transformation and rotation of the red-black tree, and to insert data so that the red-black tree still satisfies the five properties above.
Insert data:
Private void insert(RedBlackNode<T> node) {RedBlackNode<T> parent = NIL; // RedBlackNode<T> index = root; // while (! IsNil (index)) {parent = index; if (node.key.compareTo(index.key) < 0) { index = index.leftChild; } else if (node.key.compareTo(index.key) > 0) { index = index.rightChild; } else {// Find equal node, end program return; } // Point the child to the parent node. Parent = parent; size++; If (isNil(parent)) root = node; if (isNil(parent)) root = node; Else if (node.key.compareTo(parent.key) < 0) parent.leftChild = node; // 3. Parent's rightChild else parent. RightChild = node; // Initialize the child and color (the newly added node must be red) Node. leftChild = NIL; node.rightChild = NIL; node.red = true; // 2. InsertFixup (node); }Copy the codeRed black tree fixes four cases:
Case 1: The newly inserted node N is the root node
// The root of the color is always black // Case 1: the newly inserted node N is the root node root.red = false;Copy the codeCase 2: The parent node of newly added node N is black
If the father of node N is a black node, the insertion of a new node N has no effect on the tree, and the tree still satisfies the five properties of red-black trees. So don’t do anything.
Case 3: The parent node of the newly added node N is red, and the tertiary node (the brother node of the father) is red
CousinNode () {node.parent. Red = false; // Node's parent is cousinNode.red = false; Red = true; // Node.parent. Parent. // Red node = node.parent. Parent; }Copy the codeCase 4: The parent node of the newly inserted node N is red, and the tertiary node (the brother node of the father) is black
Else if (node == node.parent. LeftChild) {// Rotate node.parent false; node.parent.parent.red = true; rightRotate(node.parent.parent); CousinNode is [black node] and its parent is [right child] else {// cousinNode's parent is left-handed node = node.parent; leftRotate(node); }Copy the codeThe complete post-insert fix code is as follows:
Private void insertFixup(RedBlackNode<T> node) {RedBlackNode<T> cousinNode = NIL; // The father of the newly inserted node is red, then property 4 is not satisfied (if the node is red, While (node.parent. IsRed ()) {// The parent of node is the left child of node if (node.parent == Node. The parent. The parent. LeftChild) {/ / initializes the node's uncle (the parent node's brother) cousinNode = node. The parent, the parent, rightChild; CousinNode () {node.parent. Red = false; // Node's parent is cousinNode.red = false; Red = true; // Node.parent. Parent. // Red node = node.parent. Parent; Else if (node == node.parent. LeftChild) {// Rotate node.parent false; node.parent.parent.red = true; rightRotate(node.parent.parent); CousinNode is [black node] and its parent is [right child] else {// cousinNode's parent is left-handed node = node.parent; leftRotate(node); }} / / node [father] of a node is the child [right] [grandpa] node else {/ / initializes the node's uncle (the parent node's brother) cousinNode = node. The parent, the parent, leftChild; CousinNode () {node.parent. Red = false; // Node's parent is cousinNode.red = false; Red = true; // Node.parent. Parent. // Red node = node.parent. Parent; Else if (node == node.parent. LeftChild) {node = node.parent; // Use the parent of node to rightRotate(node); // cousinNode is [black] and its parent is [right child] else {// Reset the color to node.parent. Red = false; node.parent.parent.red = true; leftRotate(node.parent.parent); }}} // The root of the color is always black // Case 1: the newly inserted node N is the root node root.red = false; }Copy the codeFive, left and right rotation operation
After data is inserted, the tree needs to be repaired to meet the five properties of red-black tree. In the process of repair, it is necessary to adjust the position of the node, which is to use left rotation and right rotation operation.
Private void leftRotate(RedBlackNode<T> node) {RedBlackNode<T> nodeRightChild = node.rightChild; // Node.rightChild = noderightChild.leftChild; // Adopt node's right child's left child as its right child if (! IsNil (nodeRightChild leftChild)) / / the left child node's right child not to NIL nodeRightChild. LeftChild. Parent = node; // Make node its parent noderightChild.parent = node.parent; NIL if (isNil(node.parent)) root = nodeRightChild; // Set nodeRightChild's parent field to node's parent. Else if (node.parent. LeftChild == node) node.parent. LeftChild = nodeRightChild; // node is the rightChild of its parent else node.parent. RightChild = nodeRightChild; // The last rotation noderightChild. leftChild = node; node.parent = nodeRightChild; Private void rightRotate(RedBlackNode<T> node) {RedBlackNode<T> nodeLeftChild = node.leftChild; // node leftChild node.leftChild = nodeleftchild.rightchild; // Adopt node's left child's right child as its left child if (! IsNil (nodeLeftChild rightChild)) / / the right child node's left child not to NIL nodeLeftChild. RightChild. Parent = node; // Make node its parent nodeleftchild.parent = node.parent; NIL if (isNil(node.parent)) root = nodeLeftChild; // Set nodeLeftChild's parent field to node's parent. Else if (node.parent. LeftChild == node) node.parent. LeftChild = nodeLeftChild; // node is the rightChild of its parent else node.parent. RightChild = nodeLeftChild; // The last rotation nodeleftChild.rightChild = node; node.parent = nodeLeftChild; }Copy the code6. Delete the node
The operation of deleting a node is similar to that of inserting, directly into the code
Private void removeNode(RedBlackNode<T> v) {RedBlackNode<T> waitRemoveNode = search(v.key); RedBlackNode<T> successorNode = NIL; // RedBlackNode<T> successorChild = NIL; // waitRemoveNode has no child, Or have a child node of the if (isNil (waitRemoveNode. LeftChild) | | isNil (waitRemoveNode. RightChild)) successorNode = waitRemoveNode; Else // waitRemoveNode has two children successorNode = treeSuccessor(waitRemoveNode); if (! IsNil (SuccessorNode.leftChild)) // Get subsequent children successorChild = SuccessorNode.leftChild; else successorChild = successorNode.rightChild; successorChild.parent = successorNode.parent; If (isNil(SuccessOrNode.parent)) // If (isNil(SuccessorNode.parent)) // If the parent is empty root = successorChild; // else if (! isNil(successorNode.parent.leftChild) && successorNode.parent.leftChild == successorNode) successorNode.parent.leftChild = successorChild; Else if (! isNil(successorNode.parent.rightChild) && successorNode.parent.rightChild == successorNode) successorNode.parent.rightChild = successorChild; // The node to be deleted has been removed from the tree. If (successorNode! = waitRemoveNode) waitRemoveNode.key = successorNode.key; if (! Successornode.red) // removeFixup(successorChild) is balanced if the next node is black; } /** * private void removeFixup(RedBlackNode<T> node) {RedBlackNode<T> nodeBrothers; // Node is not the root node and the color is black while (node! Red == false) {// if node is the leftChild of its father if (node.parent. LeftChild == node) {nodeBrothers = node.parent.rightChild; If (nodeBrothers. Red == true) {nodeBrothers. Red = false; if (nodeBrothers. nodeBrothers.parent.red = true; leftRotate(nodeBrothers.parent); nodeBrothers = node.parent.rightChild; } / / 2. The node brother nodes around children to black if (nodeBrothers. LeftChild. Red = = false && nodeBrothers. RightChild. Red = = false) { nodeBrothers.red = true; node = node.parent; } else {/ / 3. The node's right child node brother is black the if (nodeBrothers. RightChild. Red = = false) {nodeBrothers. LeftChild. Red = false; nodeBrothers.red = true; rightRotate(nodeBrothers); nodeBrothers = node.parent.rightChild; } // 4. The sibling node is black and the right child of the sibling node is red nodeBrothers. Red = node.parent. node.parent.red = false; nodeBrothers.rightChild.red = false; leftRotate(node.parent); node = root; }} // nodeBrothers = node.parent.leftChild else {nodeBrothers = node.parent. // 1. NodeBrothers is red if (nodeBrothers. Red == true) {nodeBrothers. nodeBrothers.parent.red = true; rightRotate(nodeBrothers.parent); nodeBrothers = node.parent.leftChild; } / / 2. NodeBrothers child node is black the if (nodeBrothers. LeftChild. Red = = false && nodeBrothers. RightChild. Red = = false) { nodeBrothers.red = true; node = node.parent; } else {/ / 3. NodeBrothers left child is black the if (nodeBrothers. LeftChild. Red = = false) {nodeBrothers. RightChild. Red = false; nodeBrothers.red = true; leftRotate(nodeBrothers); nodeBrothers = node.parent.leftChild; } // 4. NodeBrothers is black, and nodeBrothers' left child is red nodeBrothers. Red = node.parent. node.parent.red = false; nodeBrothers.leftChild.red = false; rightRotate(node.parent); node = root; }}} // Set the node to black to ensure that it meets the red-black tree feature. } private RedBlackNode<T> treeSuccessor(RedBlackNode<T> waitRemoveNode) { if (! isNil(waitRemoveNode.leftChild)) return treeMinimum(waitRemoveNode.rightChild); return null; } private RedBlackNode<T> treeMinimum(RedBlackNode<T> node) {while (! isNil(node.leftChild)) node = node.leftChild; return node; }Copy the codeVii. The complete code is as follows
import com.sun.org.apache.xalan.internal.xsltc.dom.NodeIteratorBase;
import org.hamcrest.core.IsNull;
/**
* 红黑树
*/
public class RedBlackTree<T extends Comparable<T>> {
/**
* 红黑树节点
*/
static class RedBlackNode<T extends Comparable<T>> {
T key; // 节点值
boolean red; // 是否是红色节点
RedBlackNode<T> parent; // 父节点
RedBlackNode<T> leftChild; // 父节点
RedBlackNode<T> rightChild; // 父节点
public RedBlackNode() {
}
public RedBlackNode(T key) {
this();
this.key = key;
}
public boolean isRed() {
return red;
}
@Override
public String toString() {
return key + "";
}
}
private final RedBlackNode<T> NIL = new RedBlackNode<>(); // 哨兵节点(叶子结点)
private RedBlackNode<T> root = NIL; // 根节点
private int size; // 元素数量
public RedBlackTree() { // 构造方法
root.parent = NIL;
root.leftChild = NIL;
root.rightChild = NIL;
}
// 插入数据分两步：1.数据插入 2.根据红黑树性质修正树
public void insert(T key) {
if (key == null || key == "") // 数据检查
return;
insert(new RedBlackNode<T>(key));
}
// 1.数据插入
private void insert(RedBlackNode<T> node) {
RedBlackNode<T> parent = NIL; // index的父节点
RedBlackNode<T> index = root; // 索引
while (!isNil(index)) { // 循环遍历，找到插入位置和父节点
parent = index;
if (node.key.compareTo(index.key) < 0) {
index = index.leftChild;
} else if (node.key.compareTo(index.key) > 0) {
index = index.rightChild;
} else { // 找到相等节点，结束程序
return;
}
}
// 将孩子指向父亲
node.parent = parent;
size++;
// 将父亲指向孩子，分情况讨论：
// 1.父节点是NIL(当前树为空，没有根节点)
if (isNil(parent))
root = node;
// 2.父亲的左孩子
else if (node.key.compareTo(parent.key) < 0)
parent.leftChild = node;
// 3.父亲的右孩子
else
parent.rightChild = node;
// 初始化孩子和颜色(新添加的节点一定是红色)
node.leftChild = NIL;
node.rightChild = NIL;
node.red = true;
// 2.红黑树插入修正
insertFixup(node);
}
/**
* 插入修正
*
* @param node 插入的节点
*/
private void insertFixup(RedBlackNode<T> node) {
RedBlackNode<T> cousinNode = NIL; //叔节点
// 循环修正节点
// 新插入节点的父亲为红色，则不满足性质4(如果该节点是红色，则其两个孩子节点必须是黑色)
while (node.parent.isRed()) {
// node节点的 [父亲] 是 [爷爷] 节点的 [左孩子]
if (node.parent == node.parent.parent.leftChild) {
// 初始化node的叔叔(父节点的兄弟)
cousinNode = node.parent.parent.rightChild;
// 情况3.cousinNode(叔叔节点)是红节点
if (cousinNode.isRed()) {
node.parent.red = false; // node父节点置为黑
cousinNode.red = false; // node叔节点置为黑
node.parent.parent.red = true; // node的爷爷节点置红
node = node.parent.parent;
}
// 情况4.cousinNode节点为[黑节点]且为父节点[左孩子]
else if (node == node.parent.leftChild) {
// 重置颜色、以node的爷爷旋转
node.parent.red = false;
node.parent.parent.red = true;
rightRotate(node.parent.parent);
}
// 情况4.cousinNode节点为[黑节点]且为父节点[右孩子]
else {
// 以node的父亲左旋
node = node.parent;
leftRotate(node);
}
}
// node节点的 [父亲] 是 [爷爷] 节点的 [右孩子]
else {
// 初始化node的叔叔(父节点的兄弟)
cousinNode = node.parent.parent.leftChild;
// 情况1.cousinNode(叔叔节点)是红节点
if (cousinNode.isRed()) {
node.parent.red = false; // node父节点置为黑
cousinNode.red = false; // node叔节点置为黑
node.parent.parent.red = true; // node的爷爷节点置红
node = node.parent.parent;
}
// 情况2.cousinNode节点为[黑节点]且为父节点[左孩子]
else if (node == node.parent.leftChild) {
node = node.parent;
// 以node的父亲右旋
rightRotate(node);
}
// 情况3.cousinNode节点为[黑节点]且为父节点[右孩子]
else {
// 重置颜色、以node的爷爷旋转
node.parent.red = false;
node.parent.parent.red = true;
leftRotate(node.parent.parent);
}
}
}
// 颜色根部始终为黑色
// 情况1：新插入节点N为根节点
root.red = false;
}
/**
* 右旋操作
*
* @param node 旋转的轴节点
*/
private void rightRotate(RedBlackNode<T> node) {
RedBlackNode<T> nodeLeftChild = node.leftChild; // node左孩子
node.leftChild = nodeLeftChild.rightChild; // 将node的左孩子的右孩子过继给node，作为它的左孩子
if (!isNil(nodeLeftChild.rightChild)) // node的左孩子的右孩子不为NIL
nodeLeftChild.rightChild.parent = node; // 将node作为它的父亲
nodeLeftChild.parent = node.parent; // 将nodeLeftChild的父域指向node的父亲
// 如果node的父亲NIL
if (isNil(node.parent))
root = nodeLeftChild;
// node是其父节点的左孩子
else if (node.parent.leftChild == node)
node.parent.leftChild = nodeLeftChild;
// node是其父节点的右孩子
else
node.parent.rightChild = nodeLeftChild;
// 最后的旋转
nodeLeftChild.rightChild = node;
node.parent = nodeLeftChild;
}
/**
* 左旋操作
*
* @param node 旋转的轴节点
*/
private void leftRotate(RedBlackNode<T> node) {
RedBlackNode<T> nodeRightChild = node.rightChild; // node的右孩子
node.rightChild = nodeRightChild.leftChild; // 将node的右孩子的左孩子过继给node，作为它的右孩子
if (!isNil(nodeRightChild.leftChild)) // node的右孩子的左孩子不为NIL
nodeRightChild.leftChild.parent = node; // 将node作为它的父亲
nodeRightChild.parent = node.parent; // 将nodeRightChild的父域指向node的父亲
// 如果node的父亲NIL
if (isNil(node.parent))
root = nodeRightChild;
// node是其父节点的左孩子
else if (node.parent.leftChild == node)
node.parent.leftChild = nodeRightChild;
// node是其父节点的右孩子
else
node.parent.rightChild = nodeRightChild;
// 最后的旋转
nodeRightChild.leftChild = node;
node.parent = nodeRightChild;
}
// 判断节点是否是Nil(哨兵)
private boolean isNil(RedBlackNode<T> node) {
return node == this.NIL;
}
public void preOrderErgodic(){
preOrderErgodic(this.root);
}
/**
* 前序遍历红黑树
* @param node
*/
public void preOrderErgodic(RedBlackNode node){
if (node != this.NIL) {
System.out.print(node.key + "\tC:" + (node.red ? "Red" : "Black") + "\t\t");
if (node.leftChild != this.NIL)
System.out.print( "(L)" + node.leftChild.key + "\t\t");
else
System.out.print("(L)Null\t\t");
if (node.rightChild != this.NIL)
System.out.print("(R)" + node.rightChild.key + "\t\t");
else
System.out.print("(R)Null\t\t");
System.out.println();
preOrderErgodic(node.leftChild);
preOrderErgodic(node.rightChild);
}
}
// 返回树节点数
public int getSize() {
return size;
}
/**
* 删除节点
*
* @param t 要删除的节点
*/
public void remove(T t) {
if (t == null || t == "") // 简单的错误检查
return;
removeNode(new RedBlackNode<T>(t));
size--;
}
// 移除节点
private void removeNode(RedBlackNode<T> v) {
RedBlackNode<T> waitRemoveNode = search(v.key); // 查找待删除节点
RedBlackNode<T> successorNode = NIL; // 后继节点
RedBlackNode<T> successorChild = NIL; // 后继的子节点
// waitRemoveNode没有孩子节点，或者有一个孩子节点的情况
if (isNil(waitRemoveNode.leftChild) || isNil(waitRemoveNode.rightChild))
successorNode = waitRemoveNode;
else // waitRemoveNode有两个孩子节点的情况
successorNode = treeSuccessor(waitRemoveNode);
if (!isNil(successorNode.leftChild)) // 获取后继的孩子
successorChild = successorNode.leftChild;
else
successorChild = successorNode.rightChild;
successorChild.parent = successorNode.parent; //successorChild父域指向successorNode父亲
if (isNil(successorNode.parent)) // 如果successorNode父亲为空
root = successorChild;
// 左孩子
else if (!isNil(successorNode.parent.leftChild) && successorNode.parent.leftChild == successorNode)
successorNode.parent.leftChild = successorChild;
// 右孩子
else if (!isNil(successorNode.parent.rightChild) && successorNode.parent.rightChild == successorNode)
successorNode.parent.rightChild = successorChild;
// 待删除节点已从树中移除，复制值
if (successorNode != waitRemoveNode)
waitRemoveNode.key = successorNode.key;
if (!successorNode.red) // 如果后继为黑节点，需要平衡红黑树
removeFixup(successorChild);
}
/**
* 删除节点后修复红黑树
*
* @param node 为黑色的后继节点
*/
private void removeFixup(RedBlackNode<T> node) {
RedBlackNode<T> nodeBrothers; // node的兄弟节点
// node不是根节点，且颜色为黑色
while (node != root && node.red == false) {
// 如果node是其父亲的左孩子
if (node.parent.leftChild == node) {
nodeBrothers = node.parent.rightChild; // node父亲的右孩子即为node的兄弟
// 1.node兄弟节点为红色
if (nodeBrothers.red == true) {
nodeBrothers.red = false;
nodeBrothers.parent.red = true;
leftRotate(nodeBrothers.parent);
nodeBrothers = node.parent.rightChild;
}
// 2.node兄弟节点的左右孩子都为黑色
if (nodeBrothers.leftChild.red == false && nodeBrothers.rightChild.red == false) {
nodeBrothers.red = true;
node = node.parent;
} else {
// 3.node兄弟节点的右孩子为黑色
if (nodeBrothers.rightChild.red == false) {
nodeBrothers.leftChild.red = false;
nodeBrothers.red = true;
rightRotate(nodeBrothers);
nodeBrothers = node.parent.rightChild;
}
// 4.node兄弟节点为黑色, node兄弟节点的右孩子为红色
nodeBrothers.red = node.parent.red;
node.parent.red = false;
nodeBrothers.rightChild.red = false;
leftRotate(node.parent);
node = root;
}
}
// node是父亲的右孩子
else {
nodeBrothers = node.parent.leftChild; // node父亲的左孩子即为node的兄弟
// 1.nodeBrothers为红色
if (nodeBrothers.red == true) {
nodeBrothers.red = false;
nodeBrothers.parent.red = true;
rightRotate(nodeBrothers.parent);
nodeBrothers = node.parent.leftChild;
}
// 2.nodeBrothers的孩子节点都是黑色
if (nodeBrothers.leftChild.red == false && nodeBrothers.rightChild.red == false) {
nodeBrothers.red = true;
node = node.parent;
} else {
// 3.nodeBrothers的左孩子是黑色
if (nodeBrothers.leftChild.red == false) {
nodeBrothers.rightChild.red = false;
nodeBrothers.red = true;
leftRotate(nodeBrothers);
nodeBrothers = node.parent.leftChild;
}
// 4.nodeBrothers是黑色，nodeBrothers的左孩子是红色
nodeBrothers.red = node.parent.red;
node.parent.red = false;
nodeBrothers.leftChild.red = false;
rightRotate(node.parent);
node = root;
}
}
}
// 设置节点为黑色，保证满足红黑树的特性
node.red = false;
}
private RedBlackNode<T> treeSuccessor(RedBlackNode<T> waitRemoveNode) {
if (!isNil(waitRemoveNode.leftChild))
return treeMinimum(waitRemoveNode.rightChild);
return null;
}
// 获取以node为根节点的子树的最小节点
private RedBlackNode<T> treeMinimum(RedBlackNode<T> node) {
while (!isNil(node.leftChild))
node = node.leftChild;
return node;
}
/**
* 根据值寻找节点
*
* @param key 指定的值
* @return 节点
*/
private RedBlackNode<T> search(T key) {
RedBlackNode<T> index = root; // 指针
while (!isNil(index)) { // 循环遍历
if (key.equals(index.key)) // 找到了直接返回
return index;
else if (key.compareTo(index.key) < 0) // 小于取左
index = index.leftChild;
else // 大于取右
index = index.rightChild;
}
return null; // 未找到节点返回null
}
}
Copy the codeThe test code is as follows:
public class RedBlackTreeDemo { public static void main(String[] args) { RedBlackTree tree = new RedBlackTree(); // tree.insert(10); // tree.insert(9); // tree.insert(8); // tree.insert(7); // tree.insert(6); // tree.insert(5); // tree.insert(4); // tree.insert(3); // tree.insert(2); // tree.insert(1); tree.insert(40); tree.insert(30); tree.insert(50); tree.insert(25); tree.insert(51); tree.insert(66); tree.insert(66); System.out.println("The number of node in the tree: " + tree.getSize()); tree.preOrderErgodic(); // tree.remove(7); tree.remove(40); System.out.println("The number of node in the tree: " + tree.getSize()); tree.preOrderErgodic(); }}Copy the codeEight, reference
Github.com/Arsenalist/…
En.wikipedia.org/wiki/Red%E2…