红黑树以及JAVA实现( 二 ) _红黑树

文章插图

如果向上和父节点构成节点，但是父节点已经是4节点了，这个时候父节点就需要继续分裂，在往上的情况一次类推，进行递归分裂

文章插图

1.4 2-3-4树的删除相对于插入，B树的删除就相对复杂，需要分情况讨论
1.4.1 当删除节点是叶子节点当删除节点是叶子节点的时候，又分为以下情况
1.4.1.1 当删除节点为非2节点直接删除即可，因为从一个非2节点中删除一个键值以后，并不违反B树的定义
1.4.1.2 当删除节点为2节点这种情况又要分多种情况
1.4.1.2.1 兄弟节点是非2节点当兄弟节点是非2节点，我们可以直接从兄弟节点借一个元素过来，让当前删除节点形成非2节点，这样情况就转换为了2.3.3.1的情况，直接删除要删除的节点既可

文章插图

1.4.1.2.2 兄弟节点是2节点如果兄弟节点是2节点，那么此时就需要从父节点借元素了，待删除结点和父节点、兄弟节点构成一个4节点，然后将待删除节点删。
如果父节点是非2节点，那么借走就接走了，如果是2节点，借走了当前位置就空了，所以需要再从这个节点的兄弟或父节点借一个元素，如果直到根节点也没有找到一个非2节点，那么这个B树的高度就会减一。

文章插图

1.4.2 如果删除节点是非叶子节点

如果被删除节点是非叶子节点，那么我们就需要找到他的后继元素，然后将后继元素的值覆盖被删除元素，再将后继元素删除即可
那么如何寻找后继节点呢？一般来说就是key大小最接近被删除元素的叶子节点中的元素，这个元素可以大于key也可以小于key，这个是我们可以自己定义，这里我们选小于被删除元素的那个。也就是左子树节点中最大的元素。

文章插图

二、红黑树通过上一节，我们了解了红黑树的前身或者说是其本源B树之后我们再来看红黑树，相信你能够更容易理解红黑树，看出其操作的底层逻辑
在讲解之前我先讲红黑树的类结构放出来

public class RedBlackBST<Key extends Comparable<Key>, Value> {//很明显，这个常量用来代指红或黑private static final boolean Red = true;private static final boolean Black = false;//根节点private Node root;//节点类结构private class Node {Key key;Value value;Node left, right, parent;int N;boolean color;public Node(Key key, Value value, Node parent, int n, boolean color) {this.key = key;this.value = https://www.isolves.com/it/cxkf/sf/2022-08-15/value;N = n;this.color = color;this.parent = parent;}}public RedBlackBST() {}//用来判断一个节点是还是黑色private boolean isRed(Node x) {if (x == null) return false;return x.color == Red;}}

2.1 红黑树的定义【红黑树以及JAVA实现】红黑树，本质上其实就是将一个B树（我们这里讨论2-3-4树）转化为一个二叉树。那么如何去转化的同时又能继承B树绝对平衡性呢？答案就是通过染色和旋转，到这里打住，让我们先来看红黑树的定义