AVL tree: Difference between revisions
Javascript
m (→{{header|J}}: word of caution about this approach) |
(Javascript) |
||
Line 7,952:
=== More elaborate version ===
See [[AVL_tree/Java]]
=={{header|Javascript}}==
<lang Javascript>function tree(less, val, more) {
return {
depth: 1+Math.max(less.depth, more.depth),
less: less,
val: val,
more: more,
};
}
function node(val) {
return tree({depth: 0}, val, {depth: 0});
}
function insert(x,y) {
if (0 == y.depth) return x;
if (0 == x.depth) return y;
if (1 == x.depth && 1 == y.depth) {
switch (Math.sign(y.val)-x.val) {
case -1: return tree(y, x.val, {depth: 0});
case 0: return y;
case 1: return tree(x, y.val, {depth: 0});
}
}
switch (Math.sign(y.val-x.val)) {
case -1: return balance(insert(x.less, y), x.val, x.more);
case 0: return balance(insert(x.less, y.less), x.val, insert(x.more, y.more));
case 1: return balance(x.less. x.val, insert(x.more, y));
}
}
function balance(less,val,more) {
if (2 > Math.abs(less.depth-more.depth))
return tree(less,val,more);
if (more.depth > less.depth) {
if (more.more.depth >= more.less.depth) {
// 'more' was heavy
return moreHeavy(less, val, more);
} else {
return moreHeavy(less,val,lessHeavy(more.less, more.val, more.more));
}
} else {
if(less.less.depth >= less.more.depth) {
return lessHeavy(less, val, more);
} else {
return lessHeavy(moreHeavy(less.less, less.val, less.more), val, more);
}
}
}
function moreHeavy(less,val,more) {
return tree(tree(less,val,more.less), more.val, more.more)
}
function lessHeavy(less,val,more) {
return tree(less.less, less.val, tree(less.more, val, more));
}
function remove(val, y) {
switch (y.depth) {
case 0: return y;
case 1:
if (val == y.val) {
return y.less;
} else {
return y;
}
default:
switch (Math.sign(y.val - val)) {
case -1: return balance(y.less, y.val, remove(val, y.more));
case 0: return insert(y.less, y.more);
case 1: return balance(remove(val, y.less), y.val, y.more)
}
}
}
function lookup(val, y) {
switch (y.depth) {
case 0: return y;
case 1: if (val == y.val) {
return y;
} else {
return {depth: 0};
}
default:
switch (Math.sign(y.val-val)) {
case -1: return lookup(val, y.more);
case 0: return y;
case 1: return lookup(val, y.less);
}
}
}</lang>
Some examples:
<lang Javascript>
function dumptree(t) {
switch (t.depth) {
case 0: return '';
case 1: return t.val;
default: return '('+dumptree(t.less)+','+t.val+','+dumptree(t.more)+')';
}
}
function example() {
let t= node(0);
for (let j= 1; j<20; j++) {
t= insert(node(j), t);
}
console.log(dumptree(t));
t= remove(2, t);
console.log(dumptree(t));
console.log(dumptree(lookup(5, t)));
console.log(dumptree(remove(5, t)));
}
example();</lang>
{{out}}<pre>(((((0,1,2),3,(4,5,)),6,((7,8,),9,)),10,(((11,12,),13,),14,)),15,(((16,17,),18,),19,))
(((((0,1,),3,(4,5,)),6,((7,8,),9,)),10,(((11,12,),13,),14,)),15,(((16,17,),18,),19,))
(4,5,)
(((((0,1,),3,4),6,((7,8,),9,)),10,(((11,12,),13,),14,)),15,(((16,17,),18,),19,))</pre>
=={{header|Julia}}==
| |||