algorithmbook
algorithmbook copied to clipboard
Published
20 hours ago •
RubyLouvre
RubyLouvre
替罪羊树
class Node {
constructor(data) {
this.size = 1
this.data = data;
this.left = null;
this.right = null;
this.parent = null;
this.disposed = false;
}
update() {
var leftSize = this.left ? this.left.size : 0
var rightSize = this.right ? this.right.size : 0
this.size = leftSize + rightSize + (this.disposed ? 0 : 1)
}
};
class Scapegoat {
constructor() {
this.root = null;
this._size = 0;
}
size() {
return this.root ? this.root.size : 0
}
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 && !node.disposed) {
return node
}
return null
}
insert(data) {
if (!this.root) {
this.root = new Node(data)
this._size = 1
} else {
var node = this.root,
parent = null,
paths = []
while (node) {
parent = node;
paths.push(node)
var diff = data - node.data
if (diff == 0) {
return
} else if (diff < 0) {
node = node.left
} else {
node = node.right
}
}
var node = new Node(data)
this._size++;
node.parent = parent;
if (diff < 0) {
parent.left = node
} else {
parent.right = node;
}
var badNode
for (var i = paths.length - 1; i >= 0; i--) {
node = paths[i]
node.size++;
if (!this.isBalance(node)) {
badNode = node;
}
}
if (badNode) {
this.rebuild(badNode);
}
}
return true
}
inOrder(node, array) { //中序遍历
if (node) {
this.inOrder(node.left, array);
if (!node.disposed) {
array.push(node) // 构建序列
}
this.inOrder(node.right, array);
node.left = node.right = null; //清空孩子!!!
}
}
rebuild(node) {
var parent = node.parent;
var array = [];
this.inOrder(node, array)
var child = this.divide(array, 0, array.length)
//设置新子树的根的属性
child.parent = parent;
if (!parent) {
this.root = child;
} else {
if (parent.left == node) {
parent.left = child;
} else {
parent.right = child;
}
}
}
divide(array, l, r) {
if (l >= r) return null;
var mid = (l + r) >> 1;
var node = array[mid];
var child = this.divide(array, l, mid);
if (child) {
child.parent = node;
node.left = child;
}
child = this.divide(array, mid + 1, r);
if (child) {
child.parent = node;
node.right = child;
}
node.update() // 自底向上维护，先维护子树
return node
}
isBalance(node) {
// 左子树大小 < alpha * 根大小 并且 右子树大小 < alpha * 根大小
// alpha越小，树越稠密，插入效率低，查询效率高；
// alpha越大，树越稀疏，插入效率高，查询效率低；
var alpha = 0.65;
var size = node.size * alpha
var leftSize = node.left && node.left.size || 0
var rightSize = node.right && node.right.size || 0
return leftSize < size && rightSize < size;
}
remove(data) {
var node = this.find(data);
if (node && !node.disposed) {
this._size--;
node.disposed = true;
node.size--;
var p = node.parent
while (p) {
p.update()
p = p.parent;
}
}
}
toString(printNode) {
printNode = 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 tree = new Scapegoat(); // 30, 20, 60, 55, 54, 53, 52, 51, 56
[10, 50, 40, 30, 20, 60, 55, 54, 53, 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)
class Node {
constructor(data) {
this.size = 1;
this.data = data;
this.left = null;
this.right = null;
this.parent = null;
this.disposed = false;
}
maintain() {
this.size = this.disposed ? 0 : 1
if(this.left){
this.size += this.left.size
}
if(this.right){
this.size += this.right.size
}
}
}
class Scapegoat {
constructor() {
this.root = null;
}
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 && !node.disposed) {
return node;
}
return null;
}
insert(data) {
if (!this.root) {
this.root = new Node(data);
this._size = 1;
} else {
var node = this.root,
parent = null;
while (node) {
parent = node;
var diff = data - node.data;
if (diff == 0) {
return;
} 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;
}
var badNode;
while (parent) {
parent.size++;
if (!this.isBalance(parent)) {
badNode = parent;
break;
}
parent = parent.parent;
}
if (badNode) {
this.rebuild(badNode);
}
}
return true;
}
rebuild(node) {
var parent = node.parent;
var array = [];
function inOrder(node) {
//中序遍历
if (node) {
inOrder(node.left);
if (!node.disposed) {
array.push(node); // 构建序列
}
inOrder(node.right);
node.left = node.right = null; //清空孩子!!!
}
}
inOrder(node);
var child = this.divide(array, 0, array.length);
//设置新子树的根的属性
child.parent = parent;
if (!parent) {
this.root = child;
} else {
if (parent.left == node) {
parent.left = child;
} else {
parent.right = child;
}
}
}
divide(array, l, r) {
if (l >= r) return null;
var mid = (l + r) >> 1;
var node = array[mid];
var child = this.divide(array, l, mid);
if (child) {
child.parent = node;
node.left = child;
}
child = this.divide(array, mid + 1, r);
if (child) {
child.parent = node;
node.right = child;
}
node.maintain(); // 自底向上维护，先维护子树
return node;
}
isBalance(node) {
// 左子树大小 < alpha * 根大小 并且 右子树大小 < alpha * 根大小
// alpha越小，树越稠密，插入效率低，查询效率高；
// alpha越大，树越稀疏，插入效率高，查询效率低；
var alpha = 0.65;
var size = node.size * alpha;
var leftSize = (node.left && node.left.size) || 0;
var rightSize = (node.right && node.right.size) || 0;
return leftSize < size && rightSize < size;
}
remove(data) {
var node = this.find(data);
if (node && !node.disposed) {
node.disposed = true;
node.size--;
var p = node.parent;
while (p) {
p.maintain();
p = p.parent;
}
}
}
toString(printNode) {
printNode =
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 tree = new Scapegoat(); // 30, 20, 60, 55, 54, 53, 52, 51, 56
[10, 50, 40, 30, 20, 60, 55, 54, 53, 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);