RubyLouvre
commented
6 years ago 
Open RubyLouvre opened 6 years ago
RubyLouvre
commented
6 years ago
RubyLouvre
commented
6 years ago 这里有一个以递归方式实现的SBT https://blog.csdn.net/u012763794/article/details/50973773
RubyLouvre
commented
6 years ago 更好的实现
toString() {
var node = this.root;
var out = []
this.preOrder(function (node) {
var parent = node.parent
if (parent) {
var isRight = parent.right === node;
out.push(parent.prefix + (isRight ? '└── ' : '├── ') + node.data);
var indent = parent.prefix + (isRight ? ' ' : '│ ');
node.prefix = indent
} else {
node.prefix = " "
out.push("└──" + node.data)
}
})
return out.join("\n")
};另一个打印实现
height() {
return this.getNodeHeight(this.root);
}
//获取指定结点的度
getNodeHeight(node) {
if (node === null) {//递归出口
return 0;
}
var leftChildHeight = this.getNodeHeight(node.left);
var rightChildHeight = this.getNodeHeight(node.right);
var max = Math.max(leftChildHeight, rightChildHeight);
return max + 1; //加上自己本身
}
breadthFirstTraval(callback) {
var queue = []
var out = []
var node = this.root;
node && queue.push(node)
while (queue.length) {
node = queue.shift()//先进先出
callback(node)
if (node.left) {
queue.push(node.left)
}
if (node.right) {
queue.push(node.right)
}
}
}
multiplyString(string, times) {
var str = "";
for (var i = 0; i < times; ++i) {
str += string;
}
return str;
}
getSpaceBetweenLeftRightBranch(height) {
var noOfNodesBetweenLeftRightBranch = Math.pow(2, height - 1) - 1;
return this.multiplyString(" ", noOfNodesBetweenLeftRightBranch);
}
getSpaceBetweenRightLeftBranch(height) {
var noOfNodesBetweenLeftRightBranch = Math.pow(2, height - 1);
return this.multiplyString(" ", noOfNodesBetweenLeftRightBranch);
}
getStartingSpace(height) {
return this.multiplyString(" ", (Math.pow(2, height - 1)) >> 1);
}
getUnderScores(height) {
var noOfElementsToLeft = (Math.pow(2, height) - 1) >> 1;
var noOfUnderScores = noOfElementsToLeft
- (Math.pow(2, height - 1) >> 1);
return this.multiplyString("__", noOfUnderScores);
}
getSpaceBetweenTwoNodes(height) {
if (height == 0)
return "";
var noOfNodesInSubTreeOfNode = Math.pow(2, height - 1) >> 1;
/** Sum of spaces of the subtrees of nodes + the parent node */
var noOfSpacesBetweenTwoNodes = noOfNodesInSubTreeOfNode * 2 + 1;
console.log("noOfSpacesBetweenTwoNodes", noOfSpacesBetweenTwoNodes)
return this.multiplyString(" ", noOfSpacesBetweenTwoNodes);
}
printNodes(queueOfNodes, noOfNodesAtCurrentHeight, height, out) {
var nodesAtHeight = []
console.log(queueOfNodes.concat(), height)
nodesAtHeight.append = function (a) {
this.push(a)
return this
}
var startSpace = this.getStartingSpace(height);
var spaceBetweenTwoNodes = this.getSpaceBetweenTwoNodes(height);
var underScore = this.getUnderScores(height);
var underScoreSpace = this.multiplyString(" ", underScore.length);
nodesAtHeight.append(startSpace)
for (var i = 0; i < noOfNodesAtCurrentHeight; i++) {
var node = queueOfNodes[i]
if (node == null) {
nodesAtHeight.append(underScoreSpace)
.append(" ")
.append(underScoreSpace)
.append(spaceBetweenTwoNodes);
} else {
nodesAtHeight
.append(node.left != null ? underScore
: underScoreSpace)
.append(node.data)
.append(node.right != null ? underScore
: underScoreSpace)
.append(spaceBetweenTwoNodes);
}
}
var s = nodesAtHeight.join("").replace(/\s+$/, "");
out.push(s)
}
printBranches(queueOfNodes, noOfNodesAtCurrentHeight, height, out) {
if (height <= 1)
return;
var brachesAtHeight = [];
brachesAtHeight.append = function (a) {
this.push(a)
return this
}
var startSpace = this.getStartingSpace(height);
var leftRightSpace = this.getSpaceBetweenLeftRightBranch(height);
var rightLeftSpace = this.getSpaceBetweenRightLeftBranch(height);
brachesAtHeight
.append(startSpace.substring(0, startSpace.length - 1));
for (var i = 0; i < noOfNodesAtCurrentHeight; i++) {
var node = queueOfNodes[i]
if (node == null) {
brachesAtHeight.append(" ")
.append(leftRightSpace)
.append(" ")
.append(rightLeftSpace);
} else {
// brachesAtHeight.append(" ".repeat(node.data.length - 1))
brachesAtHeight.append(node.left != null ? "/" : " ")
.append(leftRightSpace)
.append(node.right != null ? "\\" : " ")
.append(rightLeftSpace);
}
}
var str = brachesAtHeight.join("").replace(/\s+$/, "");
out.push(str)
}
prettyPrintTree() {
var queueOfNodes = []
var height = this.height()
var level = 0;
var noOfNodesAtCurrentHeight = 0;
if (this.root) {
queueOfNodes.push(this.root);
}
var out = []
while (queueOfNodes.length && level < height) {
noOfNodesAtCurrentHeight = Math.pow(2, level);
//由空白，下划线与数字组成
this.printNodes(queueOfNodes, noOfNodesAtCurrentHeight, height - level, out);
this.printBranches(queueOfNodes, noOfNodesAtCurrentHeight, height
- level, out);
for (var i = 0; i < noOfNodesAtCurrentHeight; i++) {
var currNode = queueOfNodes[0]
// console.log(currNode)
queueOfNodes.shift();
if (currNode != null) {
queueOfNodes.push(currNode.left);
queueOfNodes.push(currNode.right);
} else {
queueOfNodes.push(null);
queueOfNodes.push(null);
}
}
level++;
}
console.log(out)
console.log(out.join("\n"))
}
//新的实现
class Node {
constructor(data) {
this.data = data;
this.size = 1
this.left = null;
this.right = null;
this.count = 1;
this.parent = null;
}
maintain() {
this.size = this.count;
if (this.left) {
this.size += this.left.size;
}
if (this.right) {
this.size += this.right.size;
}
}
};
function rotateImpl(tree, node, dir, setParent) {
var other = dir == "left" ? "right" : "left";
if (!node[other]) {
return;
}
var top = node[other]; //会上浮的子节点
node[other] = top[dir]; //过继孩子
if (setParent) {
if (!node.parent) {
tree.root = top;
} else if (node == node.parent.left) {
node.parent.left = top;
} else {
node.parent.right = top;
}
Object(top[dir]).parent = node; //父属性修正1
top.parent = node.parent; //父属性修正2
node.parent = top; //父属性修正3
}
top[dir] = node; //旋转
node.maintain(); //先处理下面的再处理上面的
top.maintain();
return top;
}
class SBT {
constructor() {
this.root = null;
}
leftRotate(node) {
return rotateImpl(this, node, "left", true);
}
rightRotate(node) {
return rotateImpl(this, node, "right", true);
}
getSize(node) {
return node ? node.size : 0
}
maintain(node, rightDeeper) {
if (!node) {
return
}
var left = node.left;
var right = node.right;
if (!rightDeeper) {
if (!left) {
return
}
var rightSize = this.getSize(right)
var llSize = this.getSize(left.left)
var lrSize = this.getSize(left.right)
if (llSize > rightSize) {
this.rightRotate(node);
} else if (lrSize > rightSize) {
this.leftRotate(left);
this.rightRotate(node);
} else {
return;
}
} else {
if (!right) {
return
}
var leftSize = this.getSize(left)
var rrSize = this.getSize(right.right)
var rlSize = this.getSize(right.left)
if (rrSize > leftSize) {
this.leftRotate(node);
} else if (rlSize > leftSize) {
this.rightRotate(right);
this.leftRotate(node);
} else {
return;
}
}
this.maintain(left, false);
this.maintain(right, true);
this.maintain(node, false);
this.maintain(node, true);
}
find(data) {
var node = this.root;
while (node) {
var diff = data - node.data
if (diff == 0) {
break
} else if (diff < 0) {
node = node.left;
} else {
node = node.right;
}
}
if (node) {
return node
}
return null
}
insert(data) {
if (!this.root) {
this.root = new Node(data);
return true;
}
var node = this.root,
parent
while (node) {
var diff = data - node.data;
parent = node;
if (diff == 0) {
return false;
} else if (diff < 0) {
node = node.left;
} else {
node = node.right;
}
}
var node = new Node(data);
node.parent = parent
if (diff < 0) {
parent.left = node;
} else {
parent.right = node;
}
while (parent) {
parent.size++;
this.maintain(parent, data >= parent.data);
parent = parent.parent;
}
return true;
}
remove(data) {
if (!this.root) {
return false
}
var node = this.find(data);
if (node) {
//两个孩子的情况
if (node.left && node.right) {
var succ = this.maxNode(node.left); //求后继
node.data = succ.data;
node = succ; //转为一个孩子的情况
}
//一个或零个孩子的情况
var child = node.left || node.right || null;
var parent = node.parent;
if (parent.left == node) {
parent.left = child
} else {
parent.right = child
}
if (child) {
child.parent = parent; //parent的size发生变化
}
while (parent) {
parent.size--
this.maintain(parent, data >= parent.data);
parent = parent.parent
}
}
}
maxNode(node) {
var current = node || this.root;
while (current.right) {
current = node.right
}
return current;
}
getRank(value) {
var node = this.find(value);
if (node) {
return this.getSize(node.left) + 1;
} else {
return 0;
}
}
getKth(k) {
var node = this.root;
while (node) {
if (k <= this.getSize(node.left)) {
node = node.left;
} else if (k > this.getSize(node.left) + node.count) {
k -= this.getSize(node.left) + node.count;
node = node.right;
} else {
return node.data;
}
}
return null;
}
inOrder(cb) {
function recursion(node) {
if (node) {
recursion(node.left);
cb(node);
recursion(node.right);
}
}
recursion(this.root);
}
keys() {
var ret = [];
this.inOrder(function (p) {
ret.push(p.data);
});
return ret;
}
toString(printNode) {
if (printNode === void 0) printNode = function (n) {
return n.data;
};
var out = [];
printRow(this.root, '', true, function (v) {
return out.push(v);
}, printNode);
return out.join('');
};
}
function printRow(root, prefix, isTail, out, printNode) {
if (root) {
out(("" + prefix + (isTail ? '└── ' : '├── ') + (printNode(root)) + "\n"));
var indent = prefix + (isTail ? ' ' : '│ ');
if (root.left) {
printRow(root.left, indent, false, out, printNode);
}
if (root.right) {
printRow(root.right, indent, true, out, printNode);
}
}
}
var array = [7, 11, 13, 8, 44, 78, 15, 9, 77, 89, 1, 2] //[11,7,14,3,9,18,16,15]
var t = new SBT();
array.forEach(function (el) {
t.insert(el)
})
var rank = t.find(44)
console.log('t.find(44)', rank, t)
var a = t.getRank(44)
console.log('t.getRank(44)', a);
var b = t.getKth(a)
console.log(`t.getKth(${a})`, b);
t.remove(11);
t.remove(44);
t.remove(77);
console.log("移除11,44,77后");
console.log(t.keys(1) + "");
t.insert(11)
t.insert(43)
t.insert(76)
t.insert(77)
var tree = new SBT();
[7, 11, 13, 8, 44, 78, 15, 9, 77, 89, 1, 2, 52, 51, 56].forEach(function (el, i) {
tree.insert(el)
console.log(tree + "")
})
console.log("delete...")
tree.remove(60)
console.log(tree + "")
console.log(tree)