红黑树java代码实现
程序员文章站
2024-02-05 15:28:10
红黑树 思想源于:https://www.cnblogs.com/nananana/p/10434549.html有解释有图,很清晰(删除时需考虑根节点和兄弟节点的子节点是否存在) package tree; import jdk.nashorn.internal.ir.CallNode; impo... ......
红黑树 思想源于:https://www.cnblogs.com/nananana/p/10434549.html
有解释有图,很清晰(删除时需考虑根节点和兄弟节点的子节点是否存在)
package tree; import jdk.nashorn.internal.ir.callnode; import java.util.random; /** * 红黑树 * 思想源于:https://www.cnblogs.com/nananana/p/10434549.html */ public class rbtree { private rbtree.node root = null; private enum color {red, black} private enum child {left, right} private class node { private integer key; //key private object data; //value private node leftchild; //左子节点 private node rightchild; //右子节点 private node parent; //父节点 private color color; //红黑标示 private node() { } node(object key, object data, color color) { this.key = (integer) key; this.data = data; this.color = color; } public color getcolor() { return color; } public void setcolor(color color) { this.color = color; } boolean isred() { if (this.color.equals(color.red)) return true; return false; } } /** * 插入数据 * * @param value 插入数据 * @return 数据重复返回false */ boolean insertnode(integer key, object value) { return insertnode(root, key, value, null, child.left); } private boolean insertnode(node node, integer key, object value, node prenode, child child) { if (node == null) { node = new node(key, value, color.red); if (prenode == null) { //父节点为空,将node设为根节点 root = node; } else { if (child.equals(child.left)) { prenode.leftchild = node; } else { prenode.rightchild = node; } node.parent = prenode; } //通过rb_insert_fixup对红黑树的结点进行颜色修改以及旋转,让树仍然是一颗红黑树 rb_insert_fixup(node); return true; } else { if (key.compareto(node.key) == 0) { //root = node; return false; } else if (key.compareto(node.key) < 0) { if (!insertnode(node.leftchild, key, value, node, child.left)) { return false; } } else { if (!insertnode(node.rightchild, key, value, node, child.right)) { return false; } } return true; } } /** * @param node 插入节点 */ private void rb_insert_fixup(node node) { node pnode = node.parent; if (node == root) { //插入结点为跟节点,直接改变颜色 node.setcolor(color.black); return; } if (node == null || pnode.color.equals(color.black)) { //插入结点的父结点为黑结点,由于插入的结点是红色的,并不会影响红黑树的平衡,直接插入即可,无需做自平衡。 return; } else { //情景4:插入结点的父结点为红结点 node granode = node.parent.parent; if (pnode == granode.leftchild) { //父节点是祖父节点的左子节点 if (granode.rightchild != null && granode.rightchild.isred()) { //情景4.1:叔叔结点存在并且为红结点 /*将p和s设置为黑色(当前插入结点i)将gra设置为红色 把gra设置为当前插入结点*/ pnode.setcolor(color.black); granode.rightchild.setcolor(color.black); granode.setcolor(color.red); rb_insert_fixup(granode); } else { //情景4.2:叔叔结点不存在或为黑结点,并且插入结点的父亲结点是祖父结点的左子结点 if (node == pnode.leftchild) {//情景4.2.1 插入结点是其父结点的左子结点 /*将p设为黑色 将gra设为红色 对gra进行右旋*/ pnode.setcolor(color.black); granode.setcolor(color.red); rrotate(granode); } else { //情景4.2.2 插入结点是其父结点的右子结点 /*对p进行左旋 把p设置为插入结点,得到情景4.2.1 进行情景4.2.1的处理*/ lrotate(pnode); rb_insert_fixup(pnode); } } } else { //4.3 父节点是祖父节点的右子节点 if (granode.leftchild != null && granode.leftchild.isred()) { //情景4.3:叔叔结点存在并且为红结点+ /*将p和s设置为黑色(当前插入结点i)将gra设置为红色 把gra设置为当前插入结点*/ pnode.setcolor(color.black); granode.leftchild.setcolor(color.black); granode.setcolor(color.red); rb_insert_fixup(granode); } else { //情景4.3.1:叔叔结点不存在或为黑结点,并且插入结点的父亲结点是祖父结点的左子结点 if (node == pnode.rightchild) {//情景4.3.1:插入结点是其父结点的右子结点 /*将p设为黑色 将gra设为红色 对pp进行左旋*/ pnode.setcolor(color.black); granode.setcolor(color.red); lrotate(granode); } else { //情景4.3.2 插入结点是其父结点的右子结点 /*对p进行右旋 把p设置为插入结点,得到情景4.3.1 进行情景4.3.1的处理*/ rrotate(pnode); rb_insert_fixup(pnode); } } } } } /** * 右旋 * * @param t */ private void rrotate(node t) { node lc = t.leftchild; t.leftchild = lc.rightchild; if (t.leftchild != null) { t.leftchild.parent = t; } lc.rightchild = t; returnpnode(t, lc); } private node returnpnode(node t, node node) { if (t == root) { root = node; } else if (t.parent.leftchild == t) { t.parent.leftchild = node; } else { t.parent.rightchild = node; } node.parent = t.parent; t.parent = node; return node; } /** * 左旋 * * @param t */ private void lrotate(node t) { node rc = t.rightchild; t.rightchild = rc.leftchild; if (t.rightchild != null) { t.rightchild.parent = t; } rc.leftchild = t; returnpnode(t, rc); } /** * 中序 */ public void ldrtraversal() { ldrtraversal(root); } /** * 中序 */ private void ldrtraversal(node node) { if (node != null) { ldrtraversal(node.leftchild); system.out.print(node.key + ":" + node.color + ";"); //system.out.print("key:" + node.key + "-value" + node.data + ":" + node.color + ";"); ldrtraversal(node.rightchild); } } /** * 先序 */ public void dlrtraversal() { dlrtraversal(root); } /** * 先序 */ private void dlrtraversal(node node) { if (node != null) { system.out.print(node.key + ":" + node.color + ";"); dlrtraversal(node.leftchild); dlrtraversal(node.rightchild); } } /** * 后序 */ public void lrdtraversal() { lrdtraversal(root); } /** * 后序 */ private void lrdtraversal(node node) { if (node != null) { lrdtraversal(node.leftchild); lrdtraversal(node.rightchild); system.out.print("key:" + node.key + "-value" + node.data + ":" + node.color + ";"); } } /** * 搜索 * * @param key 传入key * @return 返回value */ public object search(integer key) { if (this.root != null) { return searchnode(key, root).data; } return null; } /** * @param key 删除key对应的node */ public boolean removen(integer key) { if (this.root != null) { node node = searchnode(key, root); if (node == null) { return false; } removennode(node); return true; } return false; } /** * @param node 删除的节点 */ private void removennode(node node) { if (node == null) { return; } if (node.leftchild == null && node.rightchild == null) { //情景1:若删除结点无子结点,直接删除。 changenode(node, null); } else if (node.leftchild != null && node.rightchild != null) { //情景3:若删除结点有两个子结点,用后继结点(大于删除结点的最小结点)替换删除结点。 node rnode = node.rightchild; while (rnode.leftchild != null) { //找到后继结点 rnode = rnode.leftchild; } // 交换位子 /*if (rnode == node.rightchild) { node.rightchild = null; rnode.leftchild = node.leftchild; } else { if (rnode.rightchild != null) { //后继节点如果有右节点 rnode.parent.leftchild = rnode.rightchild; rnode.rightchild.parent = rnode.parent; } rnode.leftchild = node.leftchild; rnode.rightchild = node.rightchild; }*/ changenode(node, rnode); //用后继节点替换要删除节点 } else { //情景2:若删除结点只有一个子结点,用子结点替换删除结点。 if (node.leftchild != null) { changenode(node, node.leftchild); } else { changenode(node, node.rightchild); } } } /** * 两节点位置交换 * 交换后删除替换节点fixupnode * @param delnode 要删除节点 * @param fixupnode 替换节点 */ private void changenode(node delnode, node fixupnode) { rb_delete_fixup(fixupnode); if (fixupnode == null) { if (delnode.parent.leftchild == delnode) { delnode.parent.leftchild = null; } else { delnode.parent.rightchild = null; } return; } object data = delnode.data; color color = delnode.color; integer key = delnode.key; if (delnode == root) { // 交换时如果删除节点是根节点,颜色直接改成黑色 delnode.setcolor(color.black); } else { delnode.color = fixupnode.color; } delnode.key = fixupnode.key; delnode.data = fixupnode.data; fixupnode.key = key; fixupnode.data = data; fixupnode.color = color; removennode(fixupnode); } public node searchnode(integer key, node node) { if (node == null) return null; if (node.key.compareto(key) == 0) { return node; } else if (key.compareto(node.key) < 0) { if (node.leftchild != null) { return searchnode(key, node.leftchild); } return null; } else { if (node.rightchild != null) { return searchnode(key, node.rightchild); } return null; } } private void rb_delete_fixup(node fixupnode) { if (fixupnode == null || fixupnode.isred()) { //情景1:替换结点是红色结点 /*颜色变为删除结点的颜色*/ return; } else { //情景2:替换结点是黑结点 node bnode = fixupnode.parent.rightchild; if (fixupnode == fixupnode.parent.leftchild) { //情景2.1:替换结点是其父结点的左子结点 //情景2.1.1:替换结点的兄弟结点是红结点 if (bnode.isred()) { bnode.setcolor(color.black); fixupnode.parent.setcolor(color.red); rrotate(fixupnode.parent); rb_delete_fixup(fixupnode); } else { //情景2.1.2: 替换结点的兄弟结点是黑结点 //情景2.1.2.1:替换结点的兄弟结点的右子结点是红结点,左子结点任意颜色 if (bnode.rightchild != null && bnode.rightchild.isred()) { /*将s的颜色设为p的颜色 将p设为黑色 将sr设为黑色 对p进行左旋*/ bnode.color = fixupnode.parent.color; fixupnode.parent.setcolor(color.black); bnode.rightchild.setcolor(color.red); lrotate(fixupnode.parent); } else if (bnode.leftchild != null && bnode.leftchild.isred()) { //情景2.1.2.2:替换结点的兄弟结点的右子结点为黑结点,左子结点为红结点 /*将s设为红色 将sl设为黑色 对s进行右旋,得到情景2.1.2.1 进行情景2.1.2.1的处理*/ bnode.setcolor(color.red); bnode.leftchild.setcolor(color.black); rrotate(bnode); rb_delete_fixup(fixupnode); } else {//删除情景2.1.2.3: 替换结点的兄弟结点的子结点都为黑结点 /*将s设为红色 把p作为新的替换结点 重新进行删除结点情景处理*/ bnode.setcolor(color.red); rb_delete_fixup(fixupnode.parent); } } } else { //删除情景2.2: 替换结点是其父结点的右子结点 //删除情景2.2.1: 替换结点的兄弟结点是红结点 if (bnode.isred()) { /*将s设为黑色 将p设为红色 对p进行右旋,得到情景2.2.2.3 进行情景2.2.2.3的处理*/ bnode.setcolor(color.black); fixupnode.parent.setcolor(color.red); lrotate(fixupnode.parent); rb_delete_fixup(fixupnode); } else { //删除情景2.2.2: 替换结点的兄弟结点是黑结点 //删除情景2.2.2.1: 替换结点的兄弟结点的左子结点是红结点,右子结点任意颜色 if (bnode.leftchild != null && bnode.leftchild.isred()) { /*将s的颜色设为p的颜色 将p设为黑色 将sl设为黑色 对p进行右旋*/ bnode.color = fixupnode.parent.color; fixupnode.parent.setcolor(color.black); bnode.leftchild.setcolor(color.black); rrotate(fixupnode.parent); } else if (bnode.rightchild != null && bnode.rightchild.isred()) {//删除情景2.2.2.2: 替换结点的兄弟结点的左子结点为黑结点,右子结点为红结点 /*将s设为红色 将sr设为黑色 对s进行左旋,得到情景2.2.2.1 进行情景2.2.2.1的处理*/ bnode.setcolor(color.red); bnode.rightchild.setcolor(color.black); lrotate(bnode); rb_delete_fixup(fixupnode); } else {//删除情景2.2.2.3:替换结点的兄弟结点的子结点都为黑结点 /*将s设为红色 把p作为新的替换结点 重新进行删除结点情景处理*/ bnode.setcolor(color.red); rb_delete_fixup(fixupnode.parent); } } } } } public static void main(string[] args) { //int[] data={8,6,4}; //int[] data={8,6,9,5,7,3}; //int[] data={8,6,7}; //int[] data={8,5,9,4,6,7}; //int[] data={8,5,9,4,7,6}; //int[] data = {8, 5, 9, 7, 6}; //object[] data = new object[100]; //object[] data = {2, 4, 15, 11, 19, 3, "f", "g", "b", "a", "d", "c", "e", new person("小王", 22)}; /*for (int i = 0; i < 100; i++) { random r = new random(); int n = r.nextint(100); data[i] = "数据" + n; //system.out.println(n); }*/ rbtree rbt = new rbtree(); int[] data = {2, 4, 15, 11, 19, 3, 12, 14, 16, 9, 13, 17, 7, 8, 5, 1, 18, 6}; for (int i = 0; i < data.length; i++) { if (data[i] == 9) { system.out.println(); } system.out.println(data[i]); rbt.insertnode(data[i], data[i]); rbt.dlrtraversal(); system.out.println("\n" + rbt.root.data); } rbt.removen(6); /*for (int i = 0; i < data.length; i++) { rbt.insertnode(string.valueof(i), data[i]); }*/ rbt.ldrtraversal(); system.out.println("\n" + rbt.root.data); rbt.dlrtraversal(); //system.out.println("\n" + rbt.search("0")); } }