差不多一周的时间没有记录学习ConcurrentHashMap类的笔记了，实在是因为这个类富含的知识太多，一开始看不懂，然后多花了不少的时间去看，之前在HashMap中没有关于红黑树的讲解，现在先将这个类的红黑树结构分析一下。
首先，当我们添加数据的时候，调用的是ConcurrentHashMap的内部方法putVal()，在该方法的最后有以下的语句：
if (binCount != 0) {
if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i);
if (oldVal != null)
return oldVal;
break;
}
如果是hash算法计算出来的位置刚刚好匹配首节点，那么binCount的值为0；链表和红黑树结构的情况下binCount都是大于0的，所以在结尾有这样的语句，然后进一步判断长度是否超过规定的长度8，如果超过，则调用treeifyBin()方法，这个方法我仔细进去读了一下，发现我以前进入到一个误区，就是当链表的长度大于8就会自动树化，其实不然，我们看下这个方法的源码：
private final void treeifyBin(Node<K,V>[] tab, int index) {
Node<K,V> b; int n, sc;
if (tab != null) {
//MIN_TREEIFY_CAPACITY的默认值为64
if ((n = tab.length) < MIN_TREEIFY_CAPACITY)
tryPresize(n << 1);
else if ((b = tabAt(tab, index)) != null && b.hash >= 0) {
synchronized (b) {
if (tabAt(tab, index) == b) {
TreeNode<K,V> hd = null, tl = null;
for (Node<K,V> e = b; e != null; e = e.next) {
TreeNode<K,V> p =
new TreeNode<K,V>(e.hash, e.key, e.val,
null, null);
if ((p.prev = tl) == null)
hd = p;
else
tl.next = p;
tl = p;
}
setTabAt(tab, index, new TreeBin<K,V>(hd));
}
}
}
}
}
在这段代码中我们知道，先对传进来的桶长度进行判断，如果桶的长度小于64，则会调用tryPresize()方法，这个方法的作用就是将容量翻倍，也就是当桶的长度大于8的时候，第一时间不是树化，而是扩大当前桶的长度，如果桶的长度大于64，则进行树化操作，看代码块中，同步锁锁的依旧是桶的首节点，然后使用一个for循环，遍历当前桶，注意两个语句：
1、if ((p.prev = tl) == null)
2、tl.next = p
在tl不等于null的情况下，也就是从桶的第二个节点开始，前一个节点的next指向后一个节点，后一个节点的prev指向前一个节点，通俗点说就是遍历这个链表，使它成为一个双端链表，然后再把这个双端链表的头结点作为参数传到TreeBin<K,V>()中，我们来看下这个构造方法的实现。
TreeBin(TreeNode<K,V> b) {
super(TREEBIN, null, null, null);
this.first = b;
TreeNode<K,V> r = null;
for (TreeNode<K,V> x = b, next; x != null; x = next) {
next = (TreeNode<K,V>)x.next;
x.left = x.right = null;
//将根节点设置为黑色，并且赋值给r
if (r == null) {
x.parent = null;
x.red = false;
r = x;
}
else {
K k = x.key;
int h = x.hash;
Class<?> kc = null;
//开始遍历
for (TreeNode<K,V> p = r;;) {
int dir, ph;
K pk = p.key;
if ((ph = p.hash) > h)
dir = -1;
else if (ph < h)
dir = 1;
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0)
dir = tieBreakOrder(k, pk);
TreeNode<K,V> xp = p;
if ((p = (dir <= 0) ? p.left : p.right) == null) {
x.parent = xp;
if (dir <= 0)
xp.left = x;
else
xp.right = x;
r = balanceInsertion(r, x);
break;
}
}
}
}
this.root = r;
assert checkInvariants(root);
}
通过他的构造方法，我们可以看出，红黑树在ConcurrentHashMap中不是以TreeNode方式存储，而是以TreeBin的方式，首先方法的第一行代码， super(TREEBIN, null, null, null);表示创建一个hash值为-2的TreeBin，所以回过头去看上边的代码，你会发现，链表和红黑树的区别在于链表首节点的hash大于0，而红黑树的首节点hash等于-2，接着往下看，插入的一个元素会默认设置为根节点，颜色为黑色，然后插入下一个元素就会开始往下遍历，介绍一下dir和ph的作用，ph就是表示当前指针所在节点的hash值，dir分为正负零三种情况，等dir为负数的时候，则往二叉树的左子树遍历，如果dir为正数，则往二叉树的右子树遍历，如果dir为0，则进行比较k和pk的两个哈希码，重新对dir进行赋值。当遍历的过程中，发现左子树或者右子树为空，则进入方法进一步根据dir<=0和dir>0两种情况来判断插入的位置，当数据插入到二叉树中时，调用balanceInsertion()方法进行调整二叉树结构，使之能够满足红黑树的规则。
红黑树的五条规则如下：
1、节点是红色或黑色。
2、根是黑色的
3、每个叶子节点（NIL或者空节点）是黑色
4、每个红色节点的子节点都是黑色，并且父节点也是黑色，也就是说不能出现连续的红节点
5、从任意节点到其每个叶子节点的所有路径的黑色节点数量是相同的
根据以上五种方法，我们来看下balanceInsertion()的代码：
static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root,
TreeNode<K,V> x) {
x.red = true;
for (TreeNode<K,V> xp, xpp, xppl, xppr;;) {
if ((xp = x.parent) == null) {
x.red = false;
return x;
}
else if (!xp.red || (xpp = xp.parent) == null)
return root;
if (xp == (xppl = xpp.left)) {
if ((xppr = xpp.right) != null && xppr.red) {
xppr.red = false;
xp.red = false;
xpp.red = true;
x = xpp;
}
else {
if (x == xp.right) {
root = rotateLeft(root, x = xp);
xpp = (xp = x.parent) == null ? null : xp.parent;
}
if (xp != null) {
xp.red = false;
if (xpp != null) {
xpp.red = true;
root = rotateRight(root, xpp);
}
}
}
}
else {
if (xppl != null && xppl.red) {
xppl.red = false;
xp.red = false;
xpp.red = true;
x = xpp;
}
else {
if (x == xp.left) {
root = rotateRight(root, x = xp);
xpp = (xp = x.parent) == null ? null : xp.parent;
}
if (xp != null) {
xp.red = false;
if (xpp != null) {
xpp.red = true;
root = rotateLeft(root, xpp);
}
}
}
}
}
}
讲这个代码块之前，我先将插入节点与其上层节点的关系先梳理以下，看下图
image.png
按照上图对比在代码块中的关系如下
插入节点代表x
父亲节点代表xp
祖父节点代表xpp
祖父节点xpp.left代表父亲节点
祖父节点xpp.right代表叔父节点
好知道了这层关系后，我们来讲解下代码，第一行代码就是将插入节点的颜色置为红色，因为如果不置为红色，将会违反第五条规则，黑色节点数量多了一个，所以所有刚插入节点的颜色都设置为红色，然后进行是否根节点判断，如果是根节点，则设置为黑色返回，否则继续往下走，如果插入节点的父节点为黑色或者祖父节点为空，那么直接返回，否则继续往下走，判断叔父节点叔父存在，如果叔父节点存在并且为红色，则将叔父节点和父亲节点同时置为黑色，祖父节点置为红色，插入节点的指针指向祖父节点，然后继续往上遍历，如果不满足叔父节点不为空和红色的条件，继续往下走，判断插入节点是否为内侧节点（左子树插入右节点代表内侧节点，右子树插入左节点代表内侧节点），以左子树为例，左子树的内侧节点为右节点，如果插入的节点是右节点，则左旋父亲节点，然后x和xp的关系要对调一下了，新插入节点变成了xp，而父亲节点变成了x，这个关系的转变可以自己动手操作一下就明白了，左旋完成后，进一步判断插入节点是否为空，不为空将插入节点设置为黑色，然后判断祖父节点是否为空，不为空则将祖父节点设置为红色，然后右旋祖父节点，到此完成了左子树的第一次调整工作，按照同样的顺序再次判断第二次调整，直到开头两个判断语句返回才算完成结构的重新规划，这个过程我绘制了左子树的流程图，流程图如下：
image.png
到此完成了红黑树的构建和插入节点的操作。
参考链接：
https://blog.csdn.net/u010723709/article/details/48007881
https://blog.csdn.net/AJ1101/article/details/79413939
https://blog.csdn.net/weixin_42340670/article/details/80503863
https://blog.csdn.net/sihai12345/article/details/79383766
附红黑树实现代码（借鉴网上的，地址找不着了，可以直接复制粘贴，然后进行测试）
<!DOCTYPE html>
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<title>在线生成红黑树（含变形步骤）</title>
</head>
<body>
<div>
<ul>
<li>增加节点</li>
<li>方式一：<input type="button" value="随机增加一个节点" title="随机增加一个节点" onclick="AddRandom()" /></li>
<li>方式二：<input id="numbertext" title="" placeholder="请用,(单字节)分割数字,0-999之间的数字" value="" /><input type="button" value="一个一个节点增加" title="增加一个节点" onclick ="AddOneNumber()" /></li>
<li></li>
<li>删除节点</li>
<li><input id="deleteNumberText" type="text" placeholder="请输入需要删除的节点" /><input type="button" value="删除" onclick="DeleteNumber()" /> </li>
<li></li>
<li>参考： http://www.cnblogs.com/skywang12345/p/3603935.html </li>
</ul>
</div>
<form>
<fieldset>
<legend>红黑树</legend>
<div id="currentView"></div>
</fieldset>
</form>
<form id="stepView"></form>
<!--我的博客： http://www.cnblogs.com/bbvi/ -->
<script>
var NodeColor = { Black: "black", Red: "red" };
var RBNode = function (_date, _paret, _color) {
this.Data = _date;
this.Parent = _paret;
this.Color = _color;
this.LeftNode = null;
this.RightNode = null;
}
var RedBlackBinaryTree = function () {
this.RootNode = null;//根节点
this.Insert = function (insertValue) {
if (this.RootNode == null) {
this.RootNode = new RBNode(insertValue, null, NodeColor.Black);
} else {
var newNode = insert.call(this, insertValue);
insertFixUp.call(this, newNode);
}
}
function insert(key) {
ClearStepView();//清空分解步骤
var node = this.RootNode;
var newNode = new RBNode(key, null, NodeColor.Red);
while (true) {
if (key > node.Data) {
if (node.RightNode == null) {
newNode.Parent = node;
node.RightNode = newNode;
break;
}
node = node.RightNode;
} else if (key < node.Data) {
if (node.LeftNode == null) {
newNode.Parent = node;
node.LeftNode = newNode;
break;
}
node = node.LeftNode;
} else {
break;
}
}
return newNode;
}
function insertFixUp(node) {
var parentNode = node.Parent;
if (parentNode != null && NodeColor.Red == parentNode.Color) {
var gprentNode = parentNode.Parent;
if (parentNode == gprentNode.LeftNode) {
var uncleNode = gprentNode.RightNode;
if (uncleNode != null && NodeColor.Red == uncleNode.Color) {
CreateStepView(this.RootNode, "insertCaseA1", node.Data);//记录分解步骤
parentNode.Color = NodeColor.Black;
uncleNode.Color = NodeColor.Black;
gprentNode.Color = NodeColor.Red;
CreateStepView(this.RootNode, "insertSolutionA1");//记录分解步骤
insertFixUp.call(this, gprentNode);
} else {
if (parentNode.RightNode == node) {
CreateStepView(this.RootNode, "insertCaseB1", node.Data);//记录分解步骤
leftRotation.call(this, parentNode);
CreateStepView(this.RootNode, "insertSolutionB1");//记录分解步骤
insertFixUp.call(this, parentNode);
} else if (parentNode.LeftNode == node) {
CreateStepView(this.RootNode, "insertCase3", node.Data);//记录分解步骤
parentNode.Color = NodeColor.Black;
gprentNode.Color = NodeColor.Red;
rightRotation.call(this, gprentNode);
CreateStepView(this.RootNode, "insertSolution3");//记录分解步骤
}
}
} else {
var uncleNode = gprentNode.LeftNode;
if (uncleNode != null && NodeColor.Red == uncleNode.Color) {
CreateStepView(this.RootNode, "insertCaseA1", node.Data);//记录分解步骤
parentNode.Color = NodeColor.Black;
uncleNode.Color = NodeColor.Black;
gprentNode.Color = NodeColor.Red;
CreateStepView(this.RootNode, "insertSolutionA1");//记录分解步骤
insertFixUp.call(this, gprentNode);
} else {
if (parentNode.LeftNode == node) {
CreateStepView(this.RootNode, "insertCase4", node.Data);//记录分解步骤
rightRotation.call(this, parentNode);
CreateStepView(this.RootNode, "insertSolution4");//记录分解步骤
insertFixUp.call(this, parentNode);
} else if (parentNode.RightNode == node) {
CreateStepView(this.RootNode, "insertCase5", node.Data);//记录分解步骤
parentNode.Color = NodeColor.Black;
gprentNode.Color = NodeColor.Red;
leftRotation.call(this, gprentNode);
CreateStepView(this.RootNode, "insertSolution5");//记录分解步骤
}
}
}
}
this.RootNode.Color = NodeColor.Black;
}
function leftRotation(node) {
var temp = node.RightNode;
node.RightNode = temp.LeftNode;
if (temp.LeftNode != null) {
temp.LeftNode.Parent = node;
}
temp.Parent = node.Parent;
if (node.Parent == null) {
this.RootNode = temp;
}
else {
if (node.Parent.LeftNode == node) {
node.Parent.LeftNode = temp;
} else {
node.Parent.RightNode = temp;
}
}
temp.LeftNode = node;
node.Parent = temp;
}
function rightRotation(node) {
var temp = node.LeftNode;
node.LeftNode = temp.RightNode;
if (temp.RightNode != null) {
temp.RightNode.Parent = node;
}
temp.Parent = node.Parent;
if (node.Parent == null) {
this.RootNode = temp;
} else {
if (node == node.Parent.RightNode) {
node.Parent.RightNode = temp;
} else {
node.Parent.LeftNode = temp;
}
}
temp.RightNode = node;
node.Parent = temp;
}
this.Remove = function (key) {
var node = search.call(this, this.RootNode, key);
if (node == null) {
return;
} else {
remove.call(this, node);
}
}
function remove(node) {
ClearStepView();//清空分解步骤
var child, parent, nodeColor;
if (node.LeftNode != null && node.RightNode != null) {
CreateStepView(this.RootNode, "deleteCase8", node.Data);//记录分解步骤
var tempNode = findMin(node.RightNode);
if (node.Parent == null) {
this.RootNode = tempNode;
} else {
if (node.Parent.LeftNode == node) {
node.Parent.LeftNode = tempNode;
} else {
node.Parent.RightNode = tempNode;
}
}
child = tempNode.RightNode;
parent = tempNode.Parent;
nodeColor = tempNode.Color;
if (parent.Data == node.Data) {
parent = tempNode;
} else {
if (child != null) {
child.Parent = parent;
}
parent.LeftNode = child;
tempNode.RightNode = node.RightNode;
node.RightNode.Parent = tempNode;
}
tempNode.Parent = node.Parent;
tempNode.Color = node.Color;
tempNode.LeftNode = node.LeftNode
node.LeftNode.Parent = tempNode;
CreateStepView(this.RootNode, "deleteSolution8");//记录分解步骤
if (nodeColor == NodeColor.Black) {
removeFixUp.call(this, child, parent);
}
} else {
CreateStepView(this.RootNode, "deleteCase9", node.Data);//记录分解步骤
if (node.LeftNode != null) {
child = node.LeftNode;
} else {
child = node.RightNode;
}
parent = node.Parent;
nodeColor = node.Color;
if (child != null) {
child.Parent = parent;
}
if (parent != null) {
if (parent.LeftNode != null && parent.LeftNode.Data == node.Data) {
parent.LeftNode = child;
} else {
parent.RightNode = child;
}
} else {
this.RootNode = child;
}
CreateStepView(this.RootNode, "deleteSolution9");//记录分解步骤
if (nodeColor == NodeColor.Black) {
removeFixUp.call(this, child, parent)
}
}
node = null;
}
function removeFixUp(node, parentNode) {
var otherNode;
while ((node == null || node.Color == NodeColor.Black) && (node != this.RootNode)) {
if (parentNode.LeftNode == node) {
otherNode = parentNode.RightNode;
if (otherNode.Color == NodeColor.Red) {
CreateStepView(this.RootNode, "deleteCase1");//记录分解步骤
otherNode.Color = NodeColor.Black;
parentNode.Color = NodeColor.Red;
leftRotation.call(this, parentNode);
otherNode = parentNode.RightNode;
CreateStepView(this.RootNode, "deleteSolution1");//记录分解步骤
}
if ((otherNode.LeftNode == null || otherNode.LeftNode.Color == NodeColor.Black) &&
(otherNode.RightNode == null || otherNode.RightNode.Color == NodeColor.Black)) {
CreateStepView(this.RootNode, "deleteCase3");//记录分解步骤
otherNode.Color = NodeColor.Red;
node = parentNode;
parentNode = node.Parent;
CreateStepView(this.RootNode, "deleteSolution3");//记录分解步骤
} else {
if (otherNode.RightNode == null || otherNode.RightNode.Color == NodeColor.Black) {
CreateStepView(this.RootNode, "deleteCase4");//记录分解步骤
otherNode.LeftNode.Color == NodeColor.Black;
otherNode.Color = NodeColor.Red;
rightRotation.call(this, otherNode);
otherNode = parentNode.RightNode;
CreateStepView(this.RootNode, "deleteSolution4");//记录分解步骤
}
CreateStepView(this.RootNode, "deleteCase6");//记录分解步骤
otherNode.Color = parentNode.Color;
parentNode.Color = NodeColor.Black;
otherNode.RightNode.Color = NodeColor.Black;
leftRotation.call(this, parentNode);
node = this.RootNode;
CreateStepView(this.RootNode, "deleteSolution6");//记录分解步骤
break;
}
} else {
otherNode = parentNode.LeftNode;
if (otherNode.Color == NodeColor.Red) {
CreateStepView(this.RootNode, "deleteCase2");//记录分解步骤
otherNode.Color = NodeColor.Black;
parentNode.Color = NodeColor.Red;
rightRotation.call(this, parentNode);
otherNode = parentNode.LeftNode;
CreateStepView(this.RootNode, "deleteSolution2");//记录分解步骤
}
if ((otherNode.LeftNode == null || otherNode.LeftNode.Color == NodeColor.Black) &&
(otherNode.RightNode == null || otherNode.RightNode.Color == NodeColor.Black)) {
CreateStepView(this.RootNode, "deleteCase3");//记录分解步骤
otherNode.Color = NodeColor.Red;
node = parentNode;
parentNode = node.parent;
CreateStepView(this.RootNode, "deleteSolution3");//记录分解步骤
} else {
if (otherNode.LeftNode == null || otherNode.LeftNode.Color == NodeColor.Black) {
CreateStepView(this.RootNode, "deleteCase5");//记录分解步骤
otherNode.RightNode.Color = NodeColor.Black;
otherNode.Color = NodeColor.Red;
leftRotation.call(this, otherNode);
otherNode = parentNode.LeftNode;
CreateStepView(this.RootNode, "deleteSolution5");//记录分解步骤
}
CreateStepView(this.RootNode, "deleteCase7");//记录分解步骤
otherNode.Color = parentNode.Color;
parentNode.Color = NodeColor.Black;
otherNode.LeftNode.Color = NodeColor.Black;
rightRotation.call(this, parentNode);
node = this.RootNode;
CreateStepView(this.RootNode, "deleteSolution7");//记录分解步骤
break;
}
}
}
if (node != null) {
node.Color = NodeColor.Black;
}
}
this.Search = function (key) {
return search.call(this, this.RootNode, key);
}
function search(node, key) {
if (node == null) {
return null;
}
if (node.Data > key) {
return search(node.LeftNode, key);
} else if (node.Data < key) {
return search(node.RightNode, key);
} else {
return node;
}
}
this.FindMin = function () {
return findMin(this.RootNode);
}
function findMin(node) {
if (node.LeftNode == null) {
return node;
}
return findMin(node.LeftNode);
}
this.FindMax = function () {
return findMax(this.RootNode)
}
function findMax(node) {
if (node.RightNode == null) {
return node;
}
return findMax(node.RightNode);
}
this.SearchRange = function (minKey, maxKey) {
return searchRange(minKey, maxKey, this.RootNode, []);
}
function searchRange(minKey, maxKey, node, nodeList) {
if (node == null) {
return nodeList;
}
if (node.Data > minKey) {
searchRange(minKey, maxKey, node.LeftNode, nodeList);
}
if (node.Data >= minKey && node.Data < maxKey) {
nodeList.push(node.Data);
}
if (node.Data < maxKey) {
searchRange(minKey, maxKey, node.RightNode, nodeList);
}
return nodeList;
}
this.LevelOrder = function (action) {
levelOrder(this.RootNode, action);
}
function levelOrder(node, action) {
var stack = [];
stack.push(node);
while (stack.length > 0) {
var temp = stack.pop();
action(temp);
if (temp.LeftNode != null) {
stack.push(temp.LeftNode);
}
if (temp.RightNode != null) {
stack.push(temp.RightNode);
}
}
}
this.PreOrder = function (action) {
treeOrder(this.RootNode, action, null, null);
}
this.InOrder = function (action) {
treeOrder(this.RootNode, null, action, null);
}
this.PostOrder = function (action) {
treeOrder(this.RootNode, null, null, action);
}
function treeOrder(node, preOrderAction, inOrderAction, postOrderAction) {
if (preOrderAction) {
preOrderAction(node);
}
if (node.LeftNode != null) {
treeOrder(node.LeftNode, preOrderAction, inOrderAction, postOrderAction);
}
if (inOrderAction) {
inOrderAction(node);
}
if (node.RightNode != null) {
treeOrder(node.RightNode, preOrderAction, inOrderAction, postOrderAction);
}
if (postOrderAction) {
postOrderAction(node);
}
}
}
</script>
<script>
var height = 50;//节点之间的高
var width = 15;//节点之间的宽
var tops = 40;//根节点离顶部的距离
var foot = 40;//树离底部距离
var spacing = 30;//树分别离两边的间距
var tree = new RedBlackBinaryTree();
function AddOneNumber() {
var numbertext = document.getElementById("numbertext").value;
var oneNums = numbertext.match(/[1-9][0-9]{0,2}\,?/);
document.getElementById("numbertext").value = numbertext.replace(/[1-9][0-9]{0,2}\,?/, "");
var num = (oneNums + "").match(/[1-9][0-9]{0,2}/);
if (!!num) {
AddNumber(parseInt(num));
}
}
function AddRandom() {
AddNumber(Math.floor(Math.random() * (1000)));
}
function AddAllNumber() {
while (true) {
AddOneNumber();
var numbertext = document.getElementById("numbertext").value;
if (!/[1-9][0-9]{0,2}/.test(numbertext)) {
break;
}
}
}
function AddNumber(number) {
tree.Insert(number);
RenewView(tree);
}
function DeleteNumber() {
var deleteNumberText = document.getElementById("deleteNumberText").value;
if (!deleteNumberText.match(/^[1-9][0-9]{0,2}$/)) {
alert("请正确输入1-999的整数");
return false;
}
var number = parseInt(deleteNumberText);
var isExist = tree.Search(number);
if (!isExist)
{
alert("不存在此节点");
return false;
}
tree.Remove(number);
document.getElementById("deleteNumberText").value = '';
RenewView(tree);
}
function RenewView(_tree) {
var currentView = document.getElementById("currentView");
currentView.innerHTML = '';
CreateTreeView(_tree.RootNode, currentView);
}
function CreateTreeView(rootNode, hostDocument) {
var size = SetCanvasWidthHeight(rootNode);
var canvas = document.createElement("canvas");
canvas.style.backgroundColor = "antiquewhite";
canvas.style.display = "block";
canvas.height = size.height;
canvas.width = size.width;
var context = canvas.getContext("2d");
hostDocument.appendChild(canvas);
SetPoint(rootNode);
PreOrder(rootNode, SetPreOrder, context, canvas.width);
}
function PreOrder(node, action, context, canvasWidth) {
action(node, context, canvasWidth);
if (node.LeftNode != null) {
PreOrder(node.LeftNode, action, context, canvasWidth);
}
if (node.RightNode != null) {
PreOrder(node.RightNode, action, context, canvasWidth);
}
}
function SetCanvasWidthHeight(rootNode) {
var level = Level(rootNode);
return {
height: height * level + tops + foot,
width: Math.pow(2, level + 1) * width + spacing * 2
};
}
function SetPreOrder(node, context, canvasWidth) {
var container = drawArc(
context,
node.Data,
canvasWidth / 2 + width * node.nodePoint,
(node.nodeLevel * height + parseInt(tops)),
node.Color);
if (node.Parent != null) {
var line = linkNode(
context,
(canvasWidth / 2 + width * node.Parent.nodePoint),
(node.Parent.nodeLevel * height + parseInt(tops)),
(node.Data, canvasWidth / 2 + width * node.nodePoint),
(node.nodeLevel * height + parseInt(tops)));
}
}
//生产节点
function drawArc(context, number, x, y, color) {
//圆
context.beginPath();
context.fillStyle = color;
context.arc(x, y, 15, (Math.PI / 180) * 0, (Math.PI / 180) * 360, false);
context.fill();
context.closePath();
//数字
var textX = x;
var textY = y + 5;
if (number < 10) {
textX -= 5;
} else if (number > 9 && number < 100) {
textX -= 8;
} else {
textX -= 12;
}
context.fillStyle = "white";
context.font = "bold 15px Arial";
context.fillText(number + "", textX, textY);
}
//链接节点
function linkNode(context, fatherNodeX, fatherNodeY, childrenNodeX, childrenNodeY) {
drawLine(context, fatherNodeX, fatherNodeY + 15, childrenNodeX, childrenNodeY - 15);
}
//生产线
function drawLine(context, x, y, toX, toY) {
context.moveTo(x, y);
context.lineTo(x, y);
context.lineTo(toX, toY);
context.stroke();
}
var maxLevel;
var level;
function Level(rootNode) {
maxLevel = 0;
level = 0;
return levels(rootNode);
}
function levels(node) {
if (node.LeftNode != null) {
level++;
levels(node.LeftNode);
}
maxLevel = Math.max(maxLevel, level);
if (node.RightNode != null) {
level++;
levels(node.RightNode);
}
level--;
return maxLevel;
}
function SetPoint(rootNode) {
var thisMaxLevel = Level(rootNode);
var childQuanty = Math.pow(2, thisMaxLevel);
rootNode.nodeLevel = 0;
rootNode.nodePoint = 0;
if (rootNode.LeftNode != null) {
setPointsLeft(rootNode.LeftNode, -1 * childQuanty / 2, 0, thisMaxLevel - 1);
}
if (rootNode.RightNode != null) {
setPointsRight(rootNode.RightNode, childQuanty / 2, 0, thisMaxLevel - 1);
}
}
function setPointsLeft(node, point, levels, thisMaxLevel) {
++levels;
node.nodeLevel = levels;
node.nodePoint = point;
if (node.LeftNode != null) {
setPointsLeft(node.LeftNode, point - Math.pow(2, thisMaxLevel - levels), levels, thisMaxLevel);
}
if (node.RightNode != null) {
setPointsLeft(node.RightNode, point + Math.pow(2, thisMaxLevel - levels), levels, thisMaxLevel);
}
}
function setPointsRight(node, point, levels, thisMaxLevel) {
++levels;
node.nodeLevel = levels;
node.nodePoint = point;
if (node.LeftNode != null) {
setPointsRight(node.LeftNode, point - Math.pow(2, thisMaxLevel - levels), levels, thisMaxLevel);
}
if (node.RightNode != null) {
setPointsRight(node.RightNode, point + Math.pow(2, thisMaxLevel - levels), levels, thisMaxLevel);
}
}
var stepRemark = {
"insertCaseA1": {
"title": "插入节点情况A1",
"remark": [
"当前节点的父节点是红色，且当前节点的祖父节点的另一个子节点（叔叔节点）也是红色"
]
},
"insertSolutionA1": {
"title": "插入节点情况A1的解决方案",
"remark": [
"(01) 将“父节点”设为黑色",
"(02) 将“叔叔节点”设为黑色",
"(03) 将“祖父节点”设为“红色",
"(04) 将“祖父节点”设为“当前节点”(红色节点)；即，之后继续对“当前节点”进行操作"
]
},
"insertCaseB1": {
"title": "插入节点情况2",
"remark": [
"当前节点的父节点是红色，叔叔节点是黑色，且当前节点是其父节点的右孩子"
]
},
"insertSolutionB1": {
"title": "插入节点情况2的解决方案",
"remark": [
"(01) 将“父节点”作为“新的当前节点”",
"(02) 以“新的当前节点”为支点进行左旋",
]
},
"insertCase3": {
"title": "插入节点情况3",
"remark": [
"当前节点的父节点是红色，叔叔节点是黑色，且当前节点是其父节点的左孩子"
]
},
"insertSolution3": {
"title": "插入节点情况3的解决方案",
"remark": [
"(01) 将“父节点”设为“黑色”",
"(02) 将“祖父节点”设为“红色”",
"(03) 以“祖父节点”为支点进行右旋"
]
},
"insertCase4": {
"title": "插入节点情况4",
"remark": [
"当前节点的父节点是红色，叔叔节点是黑色，且当前节点是其父节点的左孩子"
]
},
"insertSolution4": {
"title": "插入节点情况4的解决方案",
"remark": [
"(01) 将“父节点”作为“新的当前节点”",
"(02) 以“新的当前节点”为支点进行右旋",
]
},
"insertCase5": {
"title": "插入节点情况5",
"remark": [
"当前节点的父节点是红色，叔叔节点是黑色，且当前节点是其父节点的右孩子"
]
},
"insertSolution5": {
"title": "插入节点情况5的解决方案",
"remark": [
"(01) 将“父节点”设为“黑色”",
"(02) 将“祖父节点”设为“红色”",
"(03) 以“祖父节点”为支点进行左旋"
]
},
"deleteCase1": {
"title": "删除节点情况1",
"remark": [
"被删节点是“黑+黑”节点，被删除的节点是左节点，被删节点的兄弟节点是红色。(此时被删节点的父节点和x的兄弟节点的子节点都是黑节点)。"
]
},
"deleteSolution1": {
"title": "删除节点情况1解决方案",
"remark": [
"(01) 将x的兄弟节点设为“黑色”。",
"(02) 将x的父节点设为“红色”。",
"(03) 对x的父节点进行左旋。",
"(04) 左旋后，重新设置x的兄弟节点。"
]
},
"deleteCase2": {
"title": "删除节点情况2",
"remark": [
"被删节点是“黑+黑”节点，被删除的节点是右节点，被删节点的兄弟节点是红色。(此时被删节点的父节点和x的兄弟节点的子节点都是黑节点)。"
]
},
"deleteSolution2": {
"title": "删除节点情况2解决方案",
"remark": [
"(01) 将被删节点的兄弟节点设为“黑色”。",
"(02) 将被删节点的父节点设为“红色”。",
"(03) 对被删节点的父节点进行右旋。",
"(04) 右旋后，重新设置x的兄弟节点。"
]
},
"deleteCase3": {
"title": "删除节点情况3",
"remark": [
"被删节点是“黑+黑”节点，被删节点的兄弟节点是黑色，被删节点的兄弟节点的两个孩子都是黑色。"
]
},
"deleteSolution3": {
"title": "删除节点情况3解决方案",
"remark": [
"(01) 将被删节点的兄弟节点设为“红色”。",
"(02) 设置“被删节点的父节点”为“新的被删节点节点”。"
]
},
"deleteCase4": {
"title": "删除节点情况4",
"remark": [
"将被删节点是“黑+黑”节点，被删节点的兄弟节点是黑色；将被删节点的兄弟节点的左孩子是红色，右孩子是黑色的。"
]
},
"deleteSolution4": {
"title": "删除节点情况4解决方案",
"remark": [
"(01) 将被删节点兄弟节点的左孩子设为“黑色”。",
"(02) 将被删节点兄弟节点设为“红色”。",
"(03) 对被删节点的兄弟节点进行右旋。",
"(04) 右旋后，重新设置被删节点的兄弟节点。",
]
},
"deleteCase5": {
"title": "删除节点情况5",
"remark": [
"被删节点是“黑+黑”节点，被删节点的兄弟节点是黑色；被删节点的兄弟节点的左孩子是黑色，右孩子是红色的。"
]
},
"deleteSolution5": {
"title": "删除节点情况5解决方案",
"remark": [
"(01) 将被删节点兄弟节点的右孩子设为“黑色”。",
"(02) 将被删节点兄弟节点设为“红色”。",
"(03) 对被删节点的兄弟节点进行左旋。",
"(04) 左旋后，重新设置被删节点的兄弟节点。",
]
},
"deleteCase6": {
"title": "删除节点情况6",
"remark": [
"被删节点是“黑+黑”节点，被删节点的兄弟节点是黑色；被删节点的兄弟节点的右孩子是红色的，被删节点的兄弟节点的左孩子任意颜色。"
]
},
"deleteSolution6": {
"title": "删除节点情况6解决方案",
"remark": [
"(01) 将被删节点父节点颜色 赋值给 被删节点的兄弟节点。",
"(02) 将被删节点父节点设为“黑色”。",
"(03) 将被删节点兄弟节点的右子节点设为“黑色”。",
"(04) 对被删节点的父节点进行左旋。",
"(05) 设置“被删节点”为“根节点”。"
]
},
"deleteCase7": {
"title": "删除节点情况7",
"remark": [
"被删节点是“黑+黑”节点，被删节点的兄弟节点是黑色；被删节点的兄弟节点的左孩子是红色的，被删节点的兄弟节点的右孩子任意颜色。"
]
},
"deleteSolution7": {
"title": "删除节点情况7解决方案",
"remark": [
"(01) 将被删节点父节点颜色 赋值给 被删节点的兄弟节点。",
"(02) 将被删节点父节点设为“黑色”。",
"(03) 将被删节点兄弟节点的左子节设为“黑色”。",
"(04) 对被删节点的父节点进行右旋。",
"(05) 设置“被删节点”为“根节点”。"
]
},
"deleteCase8": {
"title": "删除节点情况8",
"remark": [
"被删节点有两个子节点"
]
},
"deleteSolution8": {
"title": "删除节点情况8解决方案",
"remark": [
"(01) 将被删节点右节点的子孙节点中找出小的节点，替换被删节点。",
]
},
"deleteCase9": {
"title": "删除节点情况9",
"remark": [
"被删节点只有一个子节点或无子节点"
]
},
"deleteSolution9": {
"title": "删除节点情况9解决方案",
"remark": [
"(01) 将唯一的子节点替换被删节点。",
]
}
};
function ClearStepView() {
var stepView = document.getElementById("stepView");
stepView.innerHTML = '';
}
function CreateStepView(_tree, step, currentNumber) {
var fieldset = document.createElement("fieldset");
var legend = document.createElement("legend");
var ul = document.createElement("ul");
var canvas = document.createElement("canvas");
legend.innerHTML = stepRemark[step].title;
if (!!currentNumber) {
var li = document.createElement("li");
li.innerHTML = "当前节点：" + currentNumber;
ul.appendChild(li);
}
for (var i = 0; i < stepRemark[step].remark.length; i++) {
var li = document.createElement("li");
li.innerHTML = stepRemark[step].remark[i];
ul.appendChild(li);
}
fieldset.appendChild(legend);
fieldset.appendChild(ul);
fieldset.appendChild(canvas);
var stepView = document.getElementById("stepView");
stepView.appendChild(fieldset);
CreateStepTreeView(_tree, canvas);
}
function CreateStepTreeView(rootNode, canvas) {
var size = SetCanvasWidthHeight(rootNode);
canvas.style.backgroundColor = "antiquewhite";
canvas.style.display = "block";
canvas.height = size.height;
canvas.width = size.width;
var context = canvas.getContext("2d");
SetPoint(rootNode);
PreOrder(rootNode, SetPreOrder, context, canvas.width);
}
</script>
</body>
</html>
网友评论