红黑树java操作代码 红黑树是java里面遍历性能最好数据结构

package com.my1.testocr.Until; import android.util.Log; import java.util.LinkedList; import java.util.NoSuchElementException; import java.util.Queue; /** * @author YC * @date 2022/10/15 14:23 * 红黑树的实现:结点插入、删除、树深度、前中后序加层次遍历、或取最小最大值 */ class RedBlackTree<Key extends Comparable<Key>,Value>{ /** * 红黑树结点 * @param <Key> * @param <Value> */ private class Node<Key,Value> { //存储键 public Key key; //存储值 private Value value; //记录左子结点 public Node left; //记录右子结点 public Node right; //由其父结点指向它的链接的颜色 public boolean color; /** * 新建结点构造函数 * @param key * @param value * @param left * @param right * @param color */ public Node(Key key, Value value, Node left, Node right, boolean color) { this.key = key; this.value = value; this.left = left; this.right = right; this.color = color; } } /** *根节点 */ private Node root; /** *记录树中元素的个数 */ private int N; /** * 红色结点标识 */ private static final boolean RED = true; /** * 黑色结点标识 */ private static final boolean BLACK = false; /** * 判断当前结点的指向链接是否为红色 * @param x * @return */ private boolean isRed(Node x){ if(x == null) { return false; } return x.color == RED; } /** * 左旋调整 * @param h * @return */ private Node rotateLeft(Node h) { //找出当前结点h的右子结点 Node x = h.right; //让x的左子结点变为h的右子结点 h.right = x.left; //让h成为x的左子结点 x.left = h; //让h的color属性变为x的color属性值 x.color = h.color; //让h的color属性变为RED h.color = RED; //返回左旋后的结点 return x; } /** * 右旋调整 * @param h * @return */ private Node rotateRight(Node h) { //找出当前结点h的左子结点 Node x = h.left; //让x的右子结点变为h的左子结点 h.left = x.right; //让h成为x的右子结点 x.right = h; //让h的color属性变为x的color属性值 x.color = h.color; //让h的color属性变为RED h.color = RED; //返回右旋后的结点 return x; } /** * 颜色反转,相当于完成拆分4-结点 * @param h */ private void flipColors(Node h) { //当前结点的左右子结点的color属性值都变为黑色 h.left.color = BLACK; h.right.color = BLACK; //当前结点变为红色 h.color = RED; } /** * 在整个树上完成插入操作 * @param key * @param val */ public void put(Key key, Value val) { //在root整个树上插入key-val,返回root root = put(root,key,val); //让根结点的颜色变为BLACK root.color = BLACK; } /** * 在指定树中，完成插入操作,并返回添加元素后新的树 * @param h * @param key * @param val * @return */ private Node put(Node h, Key key, Value val){ //如果h为空，则为第一个结点 if(h == null) { N++; return new Node(key,val,null,null,RED); } //当前插入节点的key与root根节点key比较 int cmp = key.compareTo((Key) h.key); if(cmp < 0) { //插入到当前结点的左子树 h.left = put(h.left,key,val); } else if(cmp > 0) { //插入到当前结点的右子树 h.right = put(h.right,key,val); } else { //相等则覆盖 h.value = val; } //使得树恢复平衡 h = balance(h); return h; } /** * 根据key，从树中找出对应的值 * @param key * @return */ public Value get(Key key){ return get(root,key); } /** * 从指定的树x中，找出key对应的值 * @param x * @param key * @return */ private Value get(Node x, Key key){ //如果当前结点为空，则没有找到,返回null if (x == null) { return null; } //key与根节点key进行比较 int cmp = key.compareTo((Key) x.key); if(cmp > 0) { return (Value) get(x.right,key); } else if(cmp < 0) { return (Value) get(x.left,key); } else { return (Value) x.value; } } /** * 根据key，删除树中对应的键值对 * @param key */ public void delete(Key key) { if (key == null) { return; } // 如果root的两个子节点均为黑色，则将root设置为red // 维护不变量invariant if (!isRed(root.left) && !isRed(root.right)) { root.color = RED; } root = delete(root, key); if (N > 0) { root.color = BLACK; } } /** * 删除指定树x上的键为key的键值对，并返回删除后的新树 * @param h * @param key * @return */ private Node delete(Node h, Key key) { if (key.compareTo((Key) h.key) < 0) { if (!isRed(h.left) && !isRed(h.left.left)) { // 此时h为红h.left为黑，moveRedLeft把红色推到左子树以便调用下面的delete h = moveRedLeft(h); } h.left = delete(h.left, key); } else { if (isRed(h.left)) { // 如果h.left为红则右旋，使h.right变红，方便从右子树里删除 h = rotateRight(h); } // 此时h为红或者h.right为红。 if (key.compareTo((Key) h.key) == 0 && (h.right == null)) { // h.right == null所以上面的旋转没有发生 // 右子树null，左子树不为红，只能也是null，不然黑高不平衡 return null; } // 要删的结点在右子树 // 如果要删的是h，与右子树的min对调key-value后删除右子树的min if (!isRed(h.right) && !isRed(h.right.left)) { h = moveRedRight(h); } if (key.compareTo((Key) h.key) == 0) { Node x = min(h.right); h.key = x.key; h.value = x.value; h.right = deleteMin(h.right); } else { h.right = delete(h.right, key); } } return balance(h); } /** * 获取树中元素的个数 * @return */ public int size(){ return N; } /** * 找出树中最小的键 * @return */ public Key min() { return (Key) min(root).key; } /** * 找出指定树x中，最小键所在的结点 * @param x * @return */ private Node min(Node x){ if(x.left != null) { return min(x.left); } else { return x; } } /** * 找出树中最大的键 * @return */ public Key max() {