Im trying to build an AVL/Binary tree, but was not able to find a lot of code examples, only theory. My implementation for some reason has the AVL rotation function losing half the tree when the tree is 1 sided.
Here is my code:
function buildTree(dataSet){
let root = null
function rotateRight(node){
return rotate(node,true)
}
function rotateLeft(node){
return rotate(node,false)
}
function rotate(node,right){
const inputNodeSide = right ? "left" : "right"
const targetNodeSide = right ? "right" : "left"
const targetNode = node[ inputNodeSide]
const targetNodeChild = targetNode[targetNodeSide]
targetNode[targetNodeSide] = node
node[ inputNodeSide] = targetNodeChild
return targetNode // as this is at the top
}
function createNode(data){
return {
data,
left : null,
right : null,
get balance(){
return workOutHeight(this.left) -
workOutHeight(this.right)
},
get height(){
return workOutHeight(this)
},
}
} // END createNode
function workOutHeight(node){
if(null === node){
return -1
}
return Math.max(workOutHeight(node.left),
workOutHeight(node.right))+1
}
function avl(node){
const balanced = node.balance
if(2 === balanced){
if(0 > node.left.balance){
node.left = rotateLeft(node.left);
}
return rotateRight(node);
} else if(-2 === balanced){
if(0 < node.right.balance){
node.right = rotateRight(node.right);
}
return rotateLeft(node);
}
return node
}
this.add = function(data, perent){
perent = perent || root;
if(null === perent){
return root = createNode(data);
} else if(data < perent.data){
if(null === perent.left){
return perent.left = createNode(data);
}
this.add(data,perent.left)
avl(perent)
} else if(data > perent.data){
if(null === perent.right){
return perent.right = createNode(data);
}
this.add(data,perent.right)
avl(perent)
}
} // END addData
this.tree = function(){
return JSON.parse(JSON.stringify(root))
}
if(Array.isArray(dataSet)){
dataSet.forEach(val=>this.add(val))
}
} // END buildTree
console.log(new buildTree([2,6,9,4,7,0]).tree())
Thanks for any help on this.