不是吧，就因为他和面试官多聊了半个小时红黑树，进了腾讯
static class RBNode<K extends Comparable<K>,V>{
// 节点是双向的
private RBNode parent;
private RBNode left;
private RBNode right;
private boolean color;
private K key;
private V value;
public RBNode() {
}
public RBNode(RBNode parent, RBNode left, RBNode right, boolean color, K key, V value) {
this.parent = parent;
this.left = left;
this.right = right;
this.color = color;
this.key = key;
this.value = value;
}
public RBNode getParent() {
return parent;
}
public void setParent(RBNode parent) {
this.parent = parent;
}
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 boolean isColor() {
return color;
}
public void setColor(boolean color) {
this.color = color;
}
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;
}
}
}
复制代码
左旋代码实现
/**
围绕 p 左旋
/ | / \
pl pr(r) => p rr
左旋的时候
p-pl 和 pr-rr 的关系不变
pr-rl 要变为 p-rl
还有就是要判断 p 是否有父节点
如果没有
如果有
最后
@param p
*/
priv
ate void leftRotate(RBNode p){
if(p != null){
RBNode r = p.right;
// 1.设置 pr-rl 要变为 p-rl
// 把 rl 设置到 p 的右子节点
p.right = r.left;
if(r.left != null){
// 设置 rl 的父节点为 p
r.left.parent = p;
}
// 2.判断 p 的父节点情况
r.parent = p.parent; // 不管 p 是否有父节点，都把这个父节点设置为 r 的父节点
if(p.parent == null){
root = r; // p 没有父节点 则 r 为 root 节点
}else if(p.parent.left == p){
p.parent.left = r; // 如果 p 为 p.parent 的左子节点 则 r 也为 p.parent 的左子节点
}else{
p.parent.right = r; // 反之设置 r 为 p.parent 的右子节点
}
// 最后 设置 p 为 r 的左子节点
r.left = p;
p.parent = r;
}
}
复制代码
右旋实现：
/**
围绕 p 右旋
@param p
*/
public void rightRotate(RBNode p){
if(p != null){
RBNode r = p.left;
p.left = r.right;
if(r.right != null){
r.right.parent = p;
}
r.parent = p.parent;
if(p.parent == null){
root = r;
}else if(p.parent.left == p){
p.parent.left = r;
}else{
p.parent.right = r;
}
r.right = p;
p.parent = r;
}
}
复制代码
2 新增节点
2-3-4 树中结点添加需要遵守以下规则：
插入都是向最下面一层插入
升元：将插入结点由 2-结点升级成 3-结点，或由 3-结点升级成 4-结点；
向 4-结点插入元素后，需要将中间元素提到父结点升元，原结点变成两个 2-结点，再把元素插入 2-结点中，如果父结点也是 4-结点，则递归向上层升元，至到根结点后将树高加 1；
而将这些规则对应到红黑树里，就是：
新插入的结点颜色为 红色 ，这样才可能不会对红黑树的高度产生影响。
2-结点对应红黑树中的单个黑色结点，插入时直接成功（对应 2-结点升元）。
3-结点对应红黑树中的 黑+红 子树，插入后将其修复成 红+黑+红 子树（对应 3-结点升元）；
4-结点对应红黑树中的 红+黑+红 子树，插入后将其修复成 红色祖父+黑色父叔+红色孩子 子树，然后再把祖父结点当成新插入的红色结点递归向上层修复，直至修复成功或遇到 root 结点；
公式：红黑树+新增一个节点（红色）**=**对等的 2-3-4 树+新增一个节点
2.1 新增节点示例
我们通过新增 2-3-4 树的过程来映射对应的红黑树的节点新增
2-3-4 树的新增（全部在叶子节点完成）
1.新增一个节点，2 节点
2.新增一个节点，与 2 节点合并，直接合并
3.新增一个节点，与 3 节点合并，直接合并
插入的值的位置会有 3 种情况
对应的红黑树为：
4.新增一个节点，与 4 节点合并，此时需要分裂、
插入值的位置可能是
对应的红黑树的结构为
2.2 新增代码实现
红黑树的新增规则我们理清楚了，接下来就可以通过 Java 代码来具体的实现了。
先实现插入节点，这就是一个普通的二叉树的插入
/**
新增节点
@param key
@param value
*/
public void put(K key , V value){
RBNode t = this.root;
if(t == null){
// 说明之前没有元素，现在插入的元素是第一个
root = new RBNode<>(key , value == null ? key : value,null);
return ;
}
int cmp ;
// 寻找插入位置
// 定义一个双亲指针
RBNode parent;
if(key == null){
throw new NullPointerException();
}
// 沿着跟节点找插入位置
do{
parent = t;
cmp = key.compareTo((K)t.key);
if(cmp < 0){
// 左侧找
t = t.left;
}else if(cmp > 0){
// 右侧找
t = t.right;
}else{
// 插入节点的值==比较的节点。值替换
t.setValue(value==null?key:value);
return;
}
}while (t != null);
// 找到了插入的位置 parent 指向 t 的父节点 t 为 null
// 创建要插入的节点
RBNode<K, Object> e = new RBNode<>(key, value == null ? key : value, parent);
// 然后判断要插入的位置 是 parent 的 左侧还是右侧
if(cmp < 0){
parent.left = e;
}else{
parent.right = e;
}
// 调整 变色 旋转
fixAfterPut(e);
}
复制代码
然后再根据红黑树的特点来实现调整(旋转，变色)
private boolean colorOf(RBNode node){
return node == null ? BLACK:node.color;
}
private RBNode parentOf(RBNode node){
return node != null ? node.parent:null;
}
private RBNode leftOf(RBNode node){
return node != null ? node.left:null;
}
private RBNode rightOf(RBNode node){
return node != null ? node.right:null;
}
private void setColor(RBNode node ,boolean color){
if(node != null){
node.setColor(color);
}
}
/**
插入节点后的调整处理
还未添加个人签名 2021.03.18 加入
还未添加个人简介
评论