AA Tree (balanced binary tree) data structure

9th January 2014

Binary trees are fast array-like structures that allow you to search for a value in a binary-search like manner. They should be used when fast traversal is neccessary for sorted lists.

function AATree(val) {
if (val===undefined) val = null;

this.val = val;
this.level = 1;
this.left = null;
this.right = null;
}

AATree.swap = function(obj, name, obj2, name2) {
var temp = obj[name];
obj[name] = obj2[name2];
obj2[name2] = temp;
};

AATree.prototype = {
isLeaf: function() {
return (this.left === null && this.right === null);
},
leftmost: function() {
var L = this;

do {
if (L.left === null) {
return L;

}
} while ((L = L.left));
},
successor: function() {
if (this.right!= null) {
return this.right.leftmost().val;
} else {
return null;
}
},
rightmost: function() {
var R = this;

do {
if (R.right === null) {
return R;
}
} while ((R = R.right));
},
predecessor: function() {
if (this.left != null) {
return this.left.rightmost().val;
} else {
return null;
}
},
skew: function() {
if (this.left != null && this.left.level == this.level) {
AATree.swap(this, 'val', this.left, 'val');

AATree.swap(this.left, 'right', this, 'right');
AATree.swap(this.left, 'left', this, 'right');
AATree.swap(this, 'left', this, 'right');
}
},
split: function() {
if (this.right != null && this.right.right != null && this.level == this.right.right.level) {
AATree.swap(this, 'val', this.right, 'val');
AATree.swap(this, 'level', this.right, 'level');

AATree.swap(this, 'left', this.right, 'right');
AATree.swap(this.right, 'left', this.right, 'right');
AATree.swap(this, 'left', this, 'right');

this.level++;
}
},
decreaseLevel: function() {
var requiredLevel = 1;

if (this.left != null) {
requiredLevel = this.left.level + 1;
}

if (this.right != null) {
requiredLevel = Math.min(requiredLevel, this.right.level + 1);
}

if (requiredLevel < this.level) {
this.level = requiredLevel;
if (this.right != null && requiredLevel < this.right.level) {
this.right.level = requiredLevel;
}
}
},

insert: function(val) {
if (this.val === null) {
this.val = val;
return;
}

if (val < this.val) {
if (this.left === null) {
this.left = new AATree(val);
} else {
if (this.left.insert(val) === false) {
return false;
}
}
} else if (val > this.val) {
if (this.right === null) {
this.right = new AATree(val);
} else {
if (this.right.insert(val) === false) {
return false;
}
}
} else {
return false;
}

this.skew();
this.split();
},

remove: function(val) {
if (val<this.val) {
if (this.left===null) return;
if (this.left.remove(val) === false) {
this.left = null;
return;
}
} else if (val>this.val) {
if (this.right===null) return;
if (this.right.remove(val) === false) {
this.right = null;
return;
}
} else {
// If we're a leaf, easy, otherwise reduce to leaf case.
if (this.isLeaf()) {
this.val = null;
return false;
} else if (this.left === null) {
// Get successor value and delete it from right tree,
// and set root to have that value
var Succ = this.successor();
if (this.right.remove(Succ)===false) {
this.right = null;
}

this.val = Succ;
} else {
// Get predecessor value and delete it from left tree,
// and set root to have that value
var Pred = this.predecessor();
if (this.left.remove(Pred)===false) {
this.left = null;
}

this.val = Pred;
}
}

this.decreaseLevel();
this.skew();

if (this.right) {
this.right.skew();
if (this.right.right) this.right.right.skew();
}

this.split();
if (this.right) this.right.split();
},
contains: function(val) {
var P = this;

while (P != null) {
if (val < P.val) {
P = P.left;
} else if (val > P.val) {
P = P.right;
} else {
return true;
}
}

return false;
},
first: function() {
return this.leftmost().val;
},
last: function() {
return this.rightmost().val;
},
isEmpty: function() {
return this.val === null;
},
count: function() {
if (this.val === null) {
return 0;
} else {
var count = 1;
if (this.left) count+= this.left.count();
if (this.right) count+= this.right.count();
return count;
}
},
overlapping: function(val) {
if (this.val === null) {
return null;
} else {
if (val < this.val) {
return this.left.overlapping(val);
} else if (val > this.val) {
return this.right.overlapping(val);
} else {
return this.val;
}
}
},
print: function(indent) {
indent = indent || 1;

var str = "";

if (this.right) str += this.right.print(indent+1);
str += "\n" + (new Array(indent).join(" ")) + this.val;
if (this.left) str += this.left.print(indent+1);

return str;
}
};

Usage

The above class would be used mainly like such:

var newTree = new AATree();
newTree.insert(4);
newTree.contains(4); //returns true
newTree.remove(4);
newTree.contains(4); //return false

Make a comment

Contribute to this article and have your say.