红黑树大家知道吧，那你们知道红黑树的底层实现原理是什么吗?这次我们就来详细了解一下吧。
一、红黑树是什么?
红黑树，顾名思义就是节点是红色或者黑色的一棵平衡二叉树，它会通过颜色的约束来维持二叉树的平衡。
对于一棵合格的红黑树必须有着下面的规则：
1、它的每个节点必须是红色或黑色
2、根节点必须是黑色
3、每个叶节点(NIL节点，空节点)都要是黑色的。
4、如果它的一个结点是红的，那它的另外两个子节点都必须是黑的。也就是说在一条路径上不能出现相邻的两个红色结点。
5、从它的任一节点到其每个叶子的所有路径都要包含相同数目的黑色节点。
这些约束强制了红黑树的关键性质: 从根到叶子的最长的可能路径不会多于最短的可能路径的两倍长。结果是这棵树大致上是平衡的。因为操作比如插入、删除和查找某个值的最坏情况时间都要求与树的高度成比例，这个在高度上的理论上限允许红黑树在最坏情况下都是高效的，而不同于普通的二叉查找树。所以红黑树它是复杂而高效的，其检索效率O(log n)。
二、红黑树底层实现原理有哪些?
红黑树其实也叫红黑二叉树，它的原理造就了它必须首先是一个二叉树，它具备二叉树的所有特性，同时也是一颗自平衡的排序二叉树。
我们得知道，一棵二叉树的基本都需要满足一个基本性质，即一颗二叉树中的任何节点的值必须大于它的左子节点，且小于它的右子节点。这样会使树的检索效率极大的提高。
一个合格的平衡二叉树必须具备如下特性：
1. 它是一棵空树。
2. 它的左右两棵子树高度差的绝对值不会超过1，且左右两棵树子树都是一棵平衡二叉树。意思就是说这个二叉树的任何一个等子节点，啊左右子树的高度都相近。
红黑树实现实例：
package RBTree;
/**
* 红黑树
*
*/
public class RBTreeDemo >
{
Node root; //根节点
Node min; //最左节点
Node max; //最右节点
Boolean RED = true;
Boolean BLACK = false;
/**
* 新增
* @param val
*/
public void add(T val)
{
if (this.root == null)
{
//根节点为黑色
this.root = new Node(val, this.BLACK, null, null, null);
return;
}
Node node = this.root;
//当前节点
Node current = new Node(val, this.RED, null, null, null);
//遍历树，进行插入
while (true)
{
if (val.compareTo((T) node.val) > 0)
{ //放右子节点
if (node.right == null)
{
node.right = current;
current.parent = node;
break;
}
node = node.right;
}
else
{ //放左子节点
if (node.left == null)
{
node.left = current;
current.parent = node;
break;
}
node = node.left;
}
}
//插入完进行自平衡
fixUp(current);
}
/**
* 自平衡
*/
public void fixUp(Node node)
{
//当前节点没父节点，则涂黑
if (node.parent == null)
{
node.color = this.BLACK;
this.root = node;
return;
}
//当前节点没有祖父节点
if (node.parent.parent == null)
{
return;
}
//叔父节点 可以为空
Node uncleNode = this.getUncleNode(node);
//当前节点为红，且父节点为红
if (node.color == this.RED && node.parent.color == this.RED)
{
//叔父节点为空或者为红，就进行涂色
if (uncleNode == null || uncleNode.color == this.RED)
{
node.parent.color = this.BLACK;
if (uncleNode != null)
{
uncleNode.color = this.BLACK;
}
node.parent.parent.color = this.RED;
this.fixUp(node.parent.parent);
}
else if (uncleNode.color == this.BLACK)
{
//自己是左子叶
if (node.parent.left.equals(node))
{
this.right(node);
this.fixUp(node.parent); //右旋后，修改当前节点颜色
}
else
{ //自己是右子叶
this.left(node);
this.fixUp(node.left); //曾经的父节点
}
}
}
}
/**
* 叔父节点，可以为空
* @param node
* @return
*/
private Node getUncleNode(Node node)
{
Node uncleNode = node.parent.parent.left;
if (uncleNode == null || node.parent.equals(uncleNode))
{
uncleNode = node.parent.parent.right;
}
return uncleNode;
}
/**
* 当前结点为红，且处于右子叶上。父节点为红，叔父节点为黑或空时。以当前节点为轴进行左旋
* 当前节点的祖父节点，变成自己的父节点
* 当前节点的父节点，变成自己的左节点
* 当前节点的左节点，变成当前右节点的右节点
*/
private void left(Node node)
{
Node parent = node.parent;
Node left = node.left;
Node pParent = node.parent.parent;
//祖父节点
pParent.left = node;
//父节点
parent.parent = node;
parent.right = left;
//左节点
left.parent = parent;
//当前节点
node.parent = pParent;
node.left = parent;
}
/**
* 当前结点为红，且处于左子叶上。父节点为红，叔父节点为黑时。以父节点为轴进行右旋
*/
private void right(Node node)
{
Node parent = node.parent;
Node right = parent.right;
Node pParent = node.parent.parent;
Node ppParent = node.parent.parent.parent;
//涂色
pParent.color = this.RED;
parent.color = this.BLACK;
if (ppParent != null)
{
//祖祖父节点
if (ppParent.right.equals(pParent))
{
ppParent.right = parent;
}
else
{
ppParent.left = parent;
}
}
//祖父节点
pParent.left = right;
pParent.parent = parent;
//父节点
parent.right = pParent;
parent.parent = ppParent;
//右子节点
right.parent = pParent;
}
/**
* 前序遍历 从根开始遍历
*/
private String preOrder(Node node)
{
if (node == null)
{
return null; //如果左侧树遍历完成，返回null
}
String strLeft = this.preOrder(node.left);
if (strLeft == null)
{
strLeft = "";
}
String strRight = this.preOrder(node.right);
if (strRight == null)
{
strRight = "";
}
return strLeft + node.toString() + strRight;
}
@Override
public String toString()
{
//前序遍历
return preOrder(this.root);
}
/**
* 结点类
*/
private class Node
{
public T val;
public Boolean color; //红为true
public Node left;
public Node right;
public Node parent;
public Node(T val, Boolean color, Node left, Node right, Node parent)
{
super();
this.val = val;
this.color = color;
this.left = left;
this.right = right;
this.parent = parent;
}
@Override
public String toString()
{
String left = "-";
String right = "-";
if (this.left != null)
{
left = this.left.val.toString();
}
if (this.right != null)
{
right = this.right.val.toString();
}
return "[" + left + ", " + this.val.toString() + ", " + right + ", " +
getColorName(this.color) + "]";
}
private String getColorName(Boolean color)
{
return color == true ? "红" : "黑";
}
@Override
public boolean equals(Object obj)
{
Node obj1 = (Node) obj;
return obj1.val == this.val;
}
}
}以上就是关于红黑树的一些整理了，更多java常见问答相关内容请关注我们的网站了解吧。
推荐阅读：