Skip to content

Instantly share code, notes, and snippets.

@GlulkAlex

GlulkAlex/balanced_Binary_Search_Tree.js

Created March 3, 2017 13:33
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save GlulkAlex/52a03cabf2fc67e892385a6cf2dd8b36 to your computer and use it in GitHub Desktop.
Save GlulkAlex/52a03cabf2fc67e892385a6cf2dd8b36 to your computer and use it in GitHub Desktop.
Download ZIP
An AVL tree (Georgy Adelson-Velsky and Landis' self-balancing binary search tree, named after the inventors)
Raw
balanced_Binary_Search_Tree.js
"use strict";
//
var binary_Search_Tree_Name_Space = {};
//
// Done: implement `get_UnBalanced_Sub_Tree`
// recursive, but not @tail recursive | stack safe
// traversal from top to bottom
/** it must return:
- [unBalanced_Sub_Tree object, balance_Factor] if any
- or [null, 0] if not found|search fails
*/
function get_UnBalanced_Sub_Tree(
// root
sub_Tree
){
//
// early return|break
var s_T_BF = get_Balance_Factor(sub_Tree);
//
if (s_T_BF < -1 || s_T_BF > 1) {
return [sub_Tree, s_T_BF];
} else {
//
var search_Result = [null, 0];
var l_S_T = sub_Tree.left_S_T;
var r_S_T = sub_Tree.right_S_T;
//
if (
l_S_T == null &&
r_S_T == null
){
// is leaf
return search_Result;
} else if (
l_S_T != null &&
r_S_T != null
){
// has both children
/*var l_S_T_BF = get_Balance_Factor(l_S_T);
var r_S_T_BF = get_Balance_Factor(r_S_T);
// early return|break
if (l_S_T_BF < -1 || l_S_T_BF > 1) {
return [l_S_T, l_S_T_BF];
}
if (r_S_T_BF < -1 || r_S_T_BF > 1) {
return [r_S_T, r_S_T_BF];
}*/
var left_Results = get_UnBalanced_Sub_Tree(l_S_T);
//
if (left_Results[0] == null) {
return get_UnBalanced_Sub_Tree(r_S_T);
} else {
return left_Results;
}
} else if (
l_S_T != null &&
r_S_T == null
){
/*var l_S_T_BF = get_Balance_Factor(l_S_T);
// early return|break
if (l_S_T_BF < -1 || l_S_T_BF > 1) {
return [l_S_T, l_S_T_BF];
} else {*/
// recursion
return get_UnBalanced_Sub_Tree(l_S_T);
//}
} else {//if (l_S_T == null && r_S_T != null){
// recursion
return get_UnBalanced_Sub_Tree(r_S_T);
}
//
//return void;
}
}
// recursive
// Done: prevent creation of a circular reference inside a tree data structure (as graph)
// Done: return resulting new|current|updated|promoted|changed root
// Done?: in|for easy|short|final case unBalanced_Sub_Tree.parent info needed for|to proper sub tree relinking|concatenation
/**
Cases:
initial state|case:
BFs: +2 -> +1 -> 0 <= same sign (+)
left->left heavy => to balanced -> +2.left = +1.right => +1.right = +2
4:+2 3:0
3:+1 2:0 4:0
2:0
BFs: +2 -> -1 -> 0 <= from (+) to (-)
left->right heavy => reduce to left->left heavy -> -1.right = 0.left => 0.left = -1 => +2.left = 0
4:+2
2:-1
3:0
mirror:
BFs: -2 -> -1 -> 0 <= same sign (-)
right->right heavy => to balanced -> -2.right = -1.left => -1.left = -2
2:-2 3:0
3:-1 2:0 4:0
4:0
BFs: -2 -> +1 -> 0 <= from (-) to (+)
right->left heavy => reduce to right->right heavy -> +1.left = 0.right => 0.right = +1 => -2.right = 0
2:-2
4:+1
3:0
*/
function swap_Relink(
unBalanced_Sub_Tree,
tree_Balance_Factor //: +|-2
) {
// assuming that: 'unBalanced_Sub_Tree'.hasChild():true.hasChild():true => .height >= 2
// determine the case:
// toDo: not very DRY (and Copy-Paste MUST DIE !), but who cares ?
if (tree_Balance_Factor > 1) {
// check left sub_Tree|child
var l_S_T = unBalanced_Sub_Tree.left_S_T;
var l_S_T_BF = get_Balance_Factor(l_S_T);
//
if (l_S_T_BF > 0) {
// easy|short|final case: +2.left = +1.right => +1.right = +2
unBalanced_Sub_Tree.left_S_T = l_S_T.right_S_T;
l_S_T.right_S_T = unBalanced_Sub_Tree;
//
return l_S_T;
} else if (l_S_T_BF < 0) {
// composite 2 stage case:
var l_R_S_T = l_S_T.right_S_T;
//
l_S_T.right_S_T = l_R_S_T.left_S_T;// || null;
l_R_S_T.left_S_T = l_S_T;
unBalanced_Sub_Tree.left_S_T = l_R_S_T;
// finally
// recursion
return swap_Relink( unBalanced_Sub_Tree, tree_Balance_Factor );
} else {
// assumption fails
console.error(
"`Balance_Factor` of the `unBalanced_Sub_Tree.left_S_T` fails to meet required conditions:",
l_S_T_BF, "< 0 or", l_S_T_BF, "> 0"
);
//
return unBalanced_Sub_Tree;
}
} else if (tree_Balance_Factor < -1) {
// check right sub_Tree|child
var r_S_T = unBalanced_Sub_Tree.right_S_T;
var r_S_T_BF = get_Balance_Factor(r_S_T);
//
if (r_S_T_BF < 0) {
// easy|short|final case: -2.right = -1.left => -1.left = -2
unBalanced_Sub_Tree.right_S_T = r_S_T.left_S_T;// || null;
r_S_T.left_S_T = unBalanced_Sub_Tree;
//
return r_S_T;
} else if (r_S_T_BF > 0) {
// composite 2 stage case: +1.left = 0.right => 0.right = +1 => -2.right = 0
var r_L_S_T = r_S_T.left_S_T;
//
if (1 == 0){ console.log(
"`r_L_S_T`:", r_L_S_T
);}
r_S_T.left_S_T = r_L_S_T.right_S_T;// || null;
r_L_S_T.right_S_T = r_S_T;
unBalanced_Sub_Tree.right_S_T = r_L_S_T;
// finally
// recursion
return swap_Relink( unBalanced_Sub_Tree, tree_Balance_Factor );
} else {
// assumption fails
console.error(
"`Balance_Factor` of the `unBalanced_Sub_Tree.right_S_T` fails to meet required conditions:",
r_S_T_BF, "< 0 or", r_S_T_BF, "> 0"
);
//
return unBalanced_Sub_Tree;
}
} else {
// assumption fails
console.error(
"`Balance_Factor` of the `unBalanced_Sub_Tree` fails to meet required conditions: < -1 or > 1",
Balance_Factor
);
//
return unBalanced_Sub_Tree;
}
}
//
// toDo: implement "general" tree traversal
// ? of which ordering: level (parent > left child | right child) | inOrder (left > root > right) ?
// Basically, only one traversal needed
// to collect all children dependent properties
// But then, those properties would be not computed|by name|on demand,
// but stored|cached as result values, after once set (and can be mutated|updated if needed)
// toDo: problem traversal is top -> down, so, how to propagate changes from the `leafs` back to the `root` ?
/*> var a_M = new Map([["leaf", function leaf(){}]]);
undefined
> a_M
Map { 'leaf' => [Function: leaf] }
> var a_M = new Map([["leaf", () => "anon leaf"]]);
undefined
> a_M
Map { 'leaf' => [Function] }
> a_M.get("leaf");
[Function]
> a_M.get("leaf")();
'anon leaf'
*/
function tree_Update_Traversal(
// root
sub_Tree,
//new Map(
// [
// ["is_Leaf", () => {}],
// ["has_Only_Left", () => {}],
// ["has_Only_Right", () => {}],
// ["has_Both_Children", () => {}] ] );
actions_Map
){
//
var l_S_T = sub_Tree.left_S_T;
var r_S_T = sub_Tree.right_S_T;
//
if (
l_S_T == null &&
r_S_T == null
){
// is leaf
actions_Map.get("is_Leaf")();
} else if (
l_S_T != null &&
r_S_T != null
){
// has both children
actions_Map.get("has_Both_Children")();
} else if (
l_S_T != null &&
r_S_T == null
){
actions_Map.get("has_Only_Left")();
} else {//if (l_S_T == null && r_S_T != null){
actions_Map.get("has_Only_Right")();
}
//
//return void;
}
//
// Done: implement sub tree size, using 'this' as container|owner object reference
// recursive, but not a @tail recursive
function get_Sub_Tree_Size(root, is_DeBug_Mode){
//
var sub_Tree = {};
var sub_Tree_Size = 0; // neuter to addition|subtraction
// sub_Tree = self|this from function binding
if (root == null || sub_Tree == root) {
if (1 == 1 && is_DeBug_Mode) {
console.log(
"typeof 'this':" + typeof(this) +
", 'this':" + this
);
//typeof 'this':undefined, 'this':undefined
}
sub_Tree = this;
} else {
// in this case
// it must be: next_S_T.get_Sub_Tree_Size(next_S_T)
sub_Tree = root;
}
if (
sub_Tree.hasOwnProperty('left_S_T') &&
sub_Tree.hasOwnProperty('right_S_T') ) {
//
var l_S_T = sub_Tree.left_S_T;
var r_S_T = sub_Tree.right_S_T;
//
if (
l_S_T == null &&
r_S_T == null ){
// is leaf
sub_Tree_Size = 1;
} else /*if (
l_S_T != null ||
r_S_T != null
)*/ {
// not a leaf, has at least one child
//sub_Tree_Size = l_S_T.get_Sub_Tree_Size() + r_S_T.get_Sub_Tree_Size() + 1;
sub_Tree_Size = 1;
//TypeError: Cannot read property 'hasOwnProperty' of null
if (l_S_T != null/* || l_S_T.hasOwnProperty('get_Sub_Tree_Size')*/) {sub_Tree_Size += l_S_T.get_Sub_Tree_Size();}
if (r_S_T != null) {sub_Tree_Size += r_S_T.get_Sub_Tree_Size();}
}
}
//
return sub_Tree_Size;
}
//
/** cases:
- for is leaf => size:1
- for sub tree with left or right or both children => sum(children.size) + 1
*/
/** balanceFactor = height(left subtree) - height(right subtree)
cases:
- for is leaf => 0
- for has left sub tree only => 0 - height(right subtree)
- for has right sub tree only => height(left subtree) + 0
- for has both sub trees => height(left subtree) - height(right subtree)
*/
function get_Balance_Factor(sub_Tree){
var l_S_T = sub_Tree.left_S_T;
var r_S_T = sub_Tree.right_S_T;
var balance_Factor = 0;
//
if (
l_S_T == null &&
r_S_T == null
){
// leaf
//balance_Factor = 0;
} else if (
l_S_T != null &&
r_S_T != null
){
balance_Factor = l_S_T.get_Tree_Height() - r_S_T.get_Tree_Height();
} else if (
l_S_T != null &&
r_S_T == null
){
balance_Factor = l_S_T.get_Tree_Height();
} else {//if (l_S_T == null && r_S_T != null){
balance_Factor = -r_S_T.get_Tree_Height();
}
//
return balance_Factor;
}
// iterative ? <=> in_Order_Traversal ?
// recursive, but not tail recursive ?
// toDo: too many repetitions, generalization needed ?
// root show_Tree://.<2:1=0>.\<3:4=-2>/.<4:3=-2>/.<5:2=-1>/.<6:1=0>.\\\\
function sub_Tree_Info(root, with_Height){
var l_S_T = root.left_S_T;
var r_S_T = root.right_S_T;
var l_S_T_Label = ".";
var r_S_T_Label = ".";
var node_Info = root.node_Val;
var method_Name = "show_Tree";
var balance_Factor = 0;
//
if (with_Height) {
node_Info += ":" + root.get_Tree_Height()
method_Name = "show_Tree_Height";
}
//
if (
l_S_T == null &&
r_S_T == null
){
// leaf
//balance_Factor = 0;
} else if (
l_S_T != null &&
r_S_T != null
){
// computed field|property
l_S_T_Label = l_S_T[method_Name]();
r_S_T_Label = r_S_T[method_Name]();
if (with_Height) {
balance_Factor = l_S_T.get_Tree_Height() - r_S_T.get_Tree_Height();}
} else if (
l_S_T != null &&
r_S_T == null
){
l_S_T_Label = l_S_T[method_Name]();
if (with_Height) {
balance_Factor = l_S_T.get_Tree_Height();}
} else {//if (l_S_T == null && r_S_T != null){
r_S_T_Label = r_S_T[method_Name]();
if (with_Height) {
balance_Factor = -r_S_T.get_Tree_Height();}
}
//
if (with_Height) {node_Info += "=" + balance_Factor;}
//
return "/" + l_S_T_Label + "<" + node_Info + ">" + r_S_T_Label + "\\";
}
function show_Tree(root){
// closure (if ? anonymous ? function warper added):
// Done?: when a circular reference exist|occurs inside a tree data structure (as graph)
//RangeError: Maximum call stack size exceeded
return () => sub_Tree_Info(root, 1 == 0);
};
function show_Tree_Height(root){
// closure:
return () => sub_Tree_Info(root, 1 == 1);
};
//
/** it must return:
- 0 for empty sub tree
- 1 for leaf
- max leafs chain (of left or right sub trees) for non empty sub tree
*/
function get_Tree_Height(root){
// l_S_T:[object Object] = function tree_Height(){ ... } <- !!! WTF !!!
// closure:
return function(){
var l_S_T = root.left_S_T;
var r_S_T = root.right_S_T;
var l_S_T_Height = -1;
var r_S_T_Height = -1;
//
if (l_S_T != null){
l_S_T_Height = l_S_T.get_Tree_Height();
};
if (r_S_T != null){
r_S_T_Height = r_S_T.get_Tree_Height();
};
if (1 == 0) {
console.log(
"l_S_T:" + l_S_T + " = " + l_S_T_Height +
",r_S_T:" + r_S_T + " = " + r_S_T_Height
);
}
//
return Math.max(
// ? 'leaf' case ?
1,
l_S_T_Height + 1,
r_S_T_Height + 1
);
};
};
//
// Done?: fix 'level_Order_Traversal' for empty|null 'root'
// Done: extend|refactor, to store an 'Sub_Tree' instances, not just extracted fields data
/** must return array|Map|Dictionary of pairs:
sub_Tree | node_Val | node_Label -> node level
*/
function level_Order_Traversal(
root
){
var result_Accum_Arr = [];
var is_DeBug_Mode = 1 == 0;
/// ### initialization ### ///
var stack_List = [];
var curr_Tier = 0;
var last_Level_Elem_Pos = 0;
var left_Offset_Size = 0;
var left_Offset = "";
var curr_Node = {};
// ? prepend (at the left|to the top) ?
// The .push() method
// adds one or more elements to the end of an array
// and returns the new length of the array
// The .pop() method
// removes the last element from an array
// and returns that element.
// This method changes the length of the array.
// The .unshift() method
// adds one or more elements to the beginning of an array
// and returns the new length of the new array.
// The .shift() method
// removes the first element from an array
// and returns that element.
// This method changes the length of the array.
stack_List.push(
[root, 1]
);
//System.err.println(String.format("stack_List: %s", stack_List));
//System.err.printf("initial stack_List: %s\n", stack_List);
// endless loop
while(
curr_Node != null &&
stack_List.length > 0
){
// pop() last
var curr_Pair = stack_List.pop();
curr_Node = curr_Pair[0];//.sub_Tree;
var curr_Depth = curr_Pair[1];//.tier;
//var curr_Parent_Index = curr_Pair.parent_Index;
// update .property
curr_Node.node_Level = curr_Depth;
//TypeError: Cannot read property 'node_Val' of null
result_Accum_Arr.push(
[
// key
curr_Node.node_Val,
// value
curr_Node
//curr_Depth
]
)
//
if (curr_Tier < curr_Depth) {
// level start
// update|reset
curr_Tier = curr_Depth;
//result_Accum_Str += "\n[" + curr_Tier + "]";
// reset only on level start
last_Level_Elem_Pos = 0;
//left_Offset_Size = curr_Level_Elem_Pos;// >= 0
} else {
// same level
//left_Offset_Size = curr_Level_Elem_Pos - last_Level_Elem_Pos - 1;
}
//
left_Offset = "";
for (var i = 0; i < left_Offset_Size; i++) {
left_Offset += '\t';
}
// reset|update
//last_Level_Elem_Pos = curr_Level_Elem_Pos;
//
if (curr_Node.left_S_T != null) {
stack_List.push(
//curr_Node.left
[curr_Node.left_S_T, curr_Depth + 1]//, curr_Node.val]
);
//result_Accum_Str += left_Offset + "+";
} else {
//result_Accum_Str += left_Offset + ".";
}
// toDo: ideally it must sum all previous items length, like scan()
/*result_Accum_Str += curr_Node.val +
"h" + curr_Node.ht +
"p" + curr_Parent_Index;*/
//
if (curr_Node.right_S_T != null) {
stack_List.push(
//curr_Node.right
[curr_Node.right_S_T, curr_Depth + 1]//, curr_Node.val]
);
//result_Accum_Str += "+";
} else {
//result_Accum_Str += ".";
}
}
//
// Use the regular Map constructor to transform a 2D key-value Array into a map
var result_Accum_Map = new Map(result_Accum_Arr);
//return result_Accum_Arr;
return result_Accum_Map;
}
//
/** must return -> sorted list (ascending)
*/
function in_Order_Traversal(
root,
is_DeBug_Mode
){
// stack: add|append last & pop|remove last
// it must be LIFO: last in first out
var stack = [];
var head = {};
var result_Arr = [];
//var result_Map = new Map();
//myMap.set(1, 'one');
//for (var [key, value] of myMap) {...}
var in_Order_Index = 0;
// to track|check explored roots
var explored_Set = new Set();
//var mySet = new Set();
//mySet.add(1);
//mySet.size; // 5
//mySet.delete(5); // removes 5 from the set
//mySet.has(5); // false, 5 has been removed
//mySet.forEach(function(value) {...}
stack.push(root);
// endless loop
while(
root != null &&
//head != null &&
stack.length > 0
){
// check last|most recent added
//var
head = stack[stack.length - 1];//.peek();
//
if (1 == 0 && is_DeBug_Mode) {
Console.log(
"head.val:" + head.node_Val +
",head.left:" + head.left_S_T +
",head.right:" + head.right_S_T +
",stack:" + stack +
",result_Map:" + result_Map +
",explored_Set:" + explored_Set
);
}
//TypeError: Cannot read property 'left_S_T' of null
if (head == null) {
// skip ?
// reduce to empty to end the while loop
stack.pop();
} else {
if (
head.left_S_T == null &&
head.right_S_T == null
) {
// is_Leaf: true
result_Arr.push(head.node_Val)
//result_Map.set(head.node_Val, in_Order_Index);
in_Order_Index += 1;
// reduce to empty to end the while loop
stack.pop();
} else if (
//head != null &&
head.left_S_T == null && head.right_S_T != null
) {
// has_No_Left_Sub_Tree: true
result_Arr.push(head.node_Val)
//result_Map.set(head.node_Val, in_Order_Index);
in_Order_Index += 1;
// reduce to empty to end the while loop
stack.pop();
stack.push(head.right_S_T);
} else {//if (head.left != null && head.right != null) {
// Done?: how to ensure|enforce it to do it exactly once ?
// assuming that .val is unique or store object reference
if (explored_Set.has(head.node_Val)) {
// is_Left_SubTree_Done: true
result_Arr.push(head.node_Val)
//result_Map.set(head.node_Val, in_Order_Index);
in_Order_Index += 1;
// reduce to empty to end the while loop
stack.pop();
stack.push(head.right_S_T);
} else {//if (!explored_Set.get(head.val)) {
explored_Set.add(head.node_Val);
stack.push(head.left_S_T);
}
}
}
}
//
//return result_Map;
return result_Arr
}
//
// Done: extend|refactor, to facilitate|use an 'Sub_Tree' instances, not just extracted fields data
/** from:
`level_Order_Traversal`:
Map { 1 => 1, 3 => 2, 2 => 2, 5 => 3, 4 => 3 }
and `in_Order_Traversal`:
[ 4, 2, 5, 1, 3 ]
*/
function hierarchical_Drop_Down(
in_Order_Labels_Arr,
// Map(node_Val -> Sub_Tree)
level_Order_Labels_Map,
//char
padding,
is_Reversed,
with_Height
) {
var result_Accum_Str = "";
//result_Accum_Str += "hierarchical drop down:\n";
var times = in_Order_Labels_Arr.length;
//var numbers = [1, 2, 3]
//numbers.fill(1);
//var a = ['Wind', 'Rain', 'Fire'];
//a.join(); // 'Wind,Rain,Fire'
//a.join('-'); // 'Wind-Rain-Fire'
// Generate a sequence of numbers
// Since the array is initialized with `undefined` on each position,
// the value of `v` below will be `undefined`
//Array.from({length: 5}, (v, i) => i);
// [0, 1, 2, 3, 4]
//'abc'.repeat(1);
//str.substr(start [, length])
var padding_Str = padding.repeat(times);
//
// Array.prototype.reverse()
in_Order_Labels_Arr
.forEach(
function(item, index, array) {
//
var curr_S_T = level_Order_Labels_Map.get(item);
var size = curr_S_T.get_Sub_Tree_Size();
var height = curr_S_T.get_Tree_Height();
var label = item;
// starting from 1 (not 0 based)
var tier = curr_S_T.node_Level;
var balance_Factor = get_Balance_Factor(curr_S_T);
var prefix = padding_Str.substring(0, tier - 1)
// Done: add 'BF' info
var node_Info = label + " [s:" + size + ", h:" + height + ", BF:" + balance_Factor + "]";
//
/*if (with_Height) {
node_Info += "\n" + b_T.get_Tree_Height();
} else {
// skip
}*/
// mutation
if (is_Reversed) {
result_Accum_Str = prefix + node_Info + "\n" + result_Accum_Str;
} else {
result_Accum_Str += prefix + node_Info + "\n";
}
}
);
//
//result_Accum_Str = "hierarchical drop down:\n" + result_Accum_Str;
//
return "hierarchical drop down:\n" + result_Accum_Str;
}
//
/// ### main data structure ### ///
// toDo: add | refactor custom properties | methods
//class Super | Parent | Trait | Interface
function Sub_Tree() {
var default_S_T = {
node_Val: -1, //Value
left_S_T: null,
right_S_T: null,
node_Level: 0//,
//tree_Height: 0,
//tree_Height: function(){}
};
default_S_T.get_Tree_Height = get_Tree_Height(default_S_T);
default_S_T.show_Tree = show_Tree(default_S_T);
default_S_T.show_Tree_Height = show_Tree_Height(default_S_T);
default_S_T.get_Sub_Tree_Size = get_Sub_Tree_Size//(default_S_T);
/**/
.bind(
default_S_T
//this <- undefined
//Sub_Tree <- function body text
);/**/
//
return default_S_T;
}
function Inner_Node(
node_Val,
left_S_T,
right_S_T
) {
var s_T = Sub_Tree();
s_T.node_Val = node_Val;
s_T.left_S_T = left_S_T;
s_T.right_S_T = right_S_T;
return s_T;
}
function Leaf(
node_Val
) {
var s_T = Sub_Tree();
s_T.node_Val = node_Val;
return s_T;
}
//
// Done: fix 'insert_Sub_Tree' for insertions order: [1, 4, 3, 5, 2] <- [3, 2]: fails
/** insert new node|sub tree in the right place on|of the existing tree
rebalance in necessary
*/
function insert_Sub_Tree(
root, // where to insert
node_Val, // what has to be inserted
is_DeBug_Mode// = 1 == 1;
) {
if (1 == 1 && is_DeBug_Mode) {
var tree_Str = "Empty tree (null)";
if (root == null) {} else {tree_Str = root.show_Tree();}
console
//.log(
.error(
"inserting :" + node_Val +
' to :' + tree_Str
);
}
if (1 == 1 && is_DeBug_Mode && root != null) {
var in_Order = in_Order_Traversal(root, 1 == 0);
console
//.log(
.error(
"initial 'in_Order_Traversal' was:" + in_Order);
console
.error(
level_Order_Traversal(root, in_Order)
);
}
// ancestry_List[0]
var Great_GrandParent = null;
// ancestry_List[1]
var GrandParent = null;
// ancestry_List[2]
var Parent = null;
// ancestry_List[3]
var new_Leaf = Leaf(node_Val);
// Great_GrandParent -> GrandParent -> Parent|current_Root -> Child|new_Leaf
// and it must ? rotate ? from right to the left
// last added value forces|makes first added to be removed|popped out
// for array: .shift() oldest val && .push(new val)
var ancestry_List = [/*Great_GrandParent, */GrandParent, Parent];//, new_Leaf];
// simple case|early return|break
// balanced
if (root == null) {
console.log(
"after inserting first element:", node_Val,
"Tree is balanced, no rotation needed");
return new_Leaf;
}
//
var current_Root = root;
//
// Terminated due to timeout
while(
// reset to force loop break|exit
// stop when ? hit the empty sub tree|leaf ?
current_Root != null
) {
// traverse further|deeper
ancestry_List.shift(); // oldest val &&
ancestry_List.push(current_Root); // new val)
//Parent = current_Root;
//Parent = ancestry_List[ancestry_List.length - 1)]
if (1 == 1 && is_DeBug_Mode) {
console.error(
"current_Root :" + current_Root.show_Tree()
);
}
// Done?: keep track of GrandParent & Parent
// Done: keep track of GrandParent.Parent
// height update <- ? auto ?
//current_Root.tree_Height = current_Root.tree_Height + 1;
//
if (current_Root.node_Val >= node_Val) {
if (current_Root.left_S_T == null) {
current_Root.left_S_T = new_Leaf;
// ! WTF ? <- stop condition
current_Root = null;
} else {
// reset -> check next|traverse deeper
current_Root = current_Root.left_S_T;
//GrandParent = Parent;
GrandParent = ancestry_List[0];
}
} else {//if (root.data < value) {
if (current_Root.right_S_T == null) {
current_Root.right_S_T = new_Leaf;
// stop condition|break while loop
current_Root = null;
} else {
current_Root = current_Root.right_S_T;
//GrandParent = Parent;
GrandParent = ancestry_List[0];
//?Parent = current_Root;
}
}
}
// Done?: insert|add is_Balanced check & rotations if needed (when check fails)
// root show_Tree:///.<7:1=0>.\<10:2=0>/.<12:1=0>.\\<14:5=-2>///.<16:2=-1>/.<19:1=0>.\\<21:3=1>/.<23:1=0>.\\<25:4=1>/.<26:2=-1>/.<30:1=0>.\\\\
// toDo: unbalanced node|sub_Tree is not the same as 'GrandParent' <- regardless, ? only ? 3 sub trees involved in rotation
// changing|swapping their relations between: GrandParent -> Parent|Child -> Child|GrandChild
// and might be closer to the root ?,
// So, ? traversal needed ?
// or ? just the right building|insertion sequence|method implementation ?
/* until .insert(19), tree was perfectly balanced -> 14.BF:(10.h:2 - 25.h:3 = -1)
hierarchical drop down:
###30 [s:1, h:1, BF:0]
##26 [s:2, h:2, BF:-1]
#25 [s:7, h:4, BF:1]
###23 [s:1, h:1, BF:0]
##21 [s:4, h:3, BF:1]
####19 [s:1, h:1, BF:0]
###16 [s:2, h:2, BF:-1]
14 [s:11, h:5, BF:-2]
##12 [s:1, h:1, BF:0]
#10 [s:3, h:2, BF:0]
##7 [s:1, h:1, BF:0]
*/
var balance_Factor = 0;
//GrandParent = ancestry_List[0];
//
if (GrandParent != null) {
balance_Factor = get_Balance_Factor(GrandParent);
//Great_GrandParent = ancestry_List[0];
}
//
if (balance_Factor > 1) {
console.log(
"after inserting:", node_Val,
"typeof `Great_GrandParent`:", typeof(Great_GrandParent),
"'GrandParent'[", GrandParent.node_Val, "]", GrandParent.show_Tree(),
"became unbalanced, \nleft -> right && left -> left rotation needed",
root.show_Tree()
);
if (GrandParent == root) {
console.log("root change");
root = swap_Relink( root, +2 );
} else {
GrandParent = swap_Relink( GrandParent, +2 );
}
} else if (balance_Factor < -1) {
console.log(
"after inserting:", node_Val,
"typeof `Great_GrandParent`:", typeof(Great_GrandParent),
"'GrandParent'[", GrandParent.node_Val, "]", GrandParent.show_Tree(),
"became unbalanced, \nright -> left && right -> right rotation needed",
root.show_Tree()
);
//GrandParent = swap_Relink( GrandParent, -2 );
if (GrandParent == root) {
console.log("root change");
root = swap_Relink( root, -2 );
} else {
GrandParent = swap_Relink( GrandParent, -2 );
}
} else {
console.log(
"after inserting:", node_Val,
"Tree is balanced, no rotation needed",
root.show_Tree()
);
}
//
if (1 == 1 && is_DeBug_Mode) {
var in_Order = in_Order_Traversal(root, 1 == 0);
console
//.log(
.error("final 'in_Order_Traversal' is:", level_Order_Traversal(root, in_Order));
}
// updated|mutated state
// Done?: after 'swap_Relink()' tree 'Root' might be different sub tree|not the same as initial
// Done?: how to track it|mitigate|compensate|workaround this issue ?
/* after inserting: 7 'GrandParent'[ 14 ] ///.<7>.\<10>.\<14>.\ became unbalanced,
left -> right && left -> left rotation needed ////.<7>.\<10>.\<14>.\<21>//.<23>.\<25>.\\
then [7, 10] was lost|no longer exist in the tree
*/
// strangely enough but use of an 'ancestry_List' seems to fix the issue
return root;
}
/// ### unit test ### ///
const ANSI_BOLD = "\u001B[1m";
const ANSI_UNDERLINED = "\u001B[4m";
const ANSI_REVERSED = "\u001B[7m";
const ANSI_RESET = "\u001B[0m";
const ANSI_BLACK = "\u001B[30m";
const ANSI_BLACK_B = "\u001B[40m";
const ANSI_RED = "\u001B[31m";
const ANSI_RED_B = "\u001B[41m";
const ANSI_GREEN = "\u001B[32m";
const ANSI_GREEN_B = "\u001B[42m";
const ANSI_YELLOW = "\u001B[33m"
const ANSI_YELLOW_B = "\u001B[43m";
const ANSI_BLUE = "\u001B[34m";
const ANSI_BLUE_B = "\u001B[44m";
const ANSI_MAGENTA = "\u001B[35m";
const ANSI_MAGENTA_B = "\u001B[45m";
const ANSI_CYAN = "\u001B[36m";
const ANSI_CYAN_B = "\u001B[46m";
const ANSI_WHITE = "\u001B[37m";
const ANSI_WHITE_B = "\u001B[47m";
//
function test_0() {
var description = "Create a `binary_Search_Tree` instance ...";
console.log(description);
var b_T = Inner_Node(1, Leaf(2), Leaf(3));
console.log("for Inner_Node(1, Inner_Node(2), Leaf(3))");
console.log(b_T);
var toString = Object.prototype.toString;
console.log("b_T -> " + toString.call(b_T));
console.log("b_T: " + b_T.constructor.name + ":" + toString.call(b_T.constructor.name));
console.log("b_T.left_S_T -> " + toString.call(b_T.left_S_T));
console.log(
"b_T.left_S_T: " + b_T.left_S_T.constructor.name +
":" + toString.call(b_T.left_S_T.constructor.name)
);
console.log("b_T.right_S_T -> " + toString.call(b_T.right_S_T));
console.log(
"b_T.right_S_T: " + b_T.right_S_T.constructor.name +
":" + toString.call(b_T.right_S_T.constructor.name)
);
}
function test_1() {
var description = "Checking a `binary_Search_Tree` instance 'tree_Height' ...";
console.log(description);
var b_T = Inner_Node(1, Inner_Node(2, Leaf(4), Leaf(5)), Leaf(3));
console.log("for Inner_Node(1, Inner_Node(2, Leaf(4), Leaf(5)), Leaf(3))");
console.log("root Height:" + b_T.get_Tree_Height());
console.log("left_S_T Height:" + b_T.left_S_T.get_Tree_Height());
console.log("right_S_T Height:" + b_T.right_S_T.get_Tree_Height());
}
function test_2() {
var description = "Checking `level_Order_Traversal`...";
console.log(description);
var b_T = Inner_Node(1, Inner_Node(2, Leaf(4), Leaf(5)), Leaf(3));
console.log("for Inner_Node(1, Inner_Node(2, Leaf(4), Leaf(5)), Leaf(3))");
console.log(level_Order_Traversal(b_T));
}
function test_3() {
var description = "Checking `in_Order_Traversal`...";
console.log(description);
// it must return -> sorted list (ascending by used key values comparison results)
var b_T = Inner_Node(1, Inner_Node(2, Leaf(4), Leaf(5)), Leaf(3));
console.log("for Inner_Node(1, Inner_Node(2, Leaf(4), Leaf(5)), Leaf(3))");
console.log(in_Order_Traversal(b_T));
}
function test_4() {
var description = "Checking `hierarchical_Drop_Down`...";
console.log(description);
var b_T = Inner_Node(1, Inner_Node(2, Leaf(4), Leaf(5)), Leaf(3));
console.log("for Inner_Node(1, Inner_Node(2, Leaf(4), Leaf(5)), Leaf(3))");
var in_Order_Labels_Arr = in_Order_Traversal(b_T);
var level_Order_Labels_Map = level_Order_Traversal(b_T);
var padding = "#";
var drop_Down_Str = hierarchical_Drop_Down(
in_Order_Labels_Arr,
level_Order_Labels_Map,
padding,
true
);
//
console.log(drop_Down_Str);
//
drop_Down_Str = hierarchical_Drop_Down(
[1, 2, 4, 5, 3],
level_Order_Labels_Map,
padding,
false
);
console.log(drop_Down_Str);
}
function test_5() {
var description = "Checking a `binary_Search_Tree` instance 'show_Tree' ...";
console.log(description);
var b_T = Inner_Node(1, Inner_Node(2, Leaf(4), Leaf(5)), Leaf(3));
console.log("for Inner_Node(1, Inner_Node(2, Leaf(4), Leaf(5)), Leaf(3))");
console.log("root show_Tree:" + b_T.show_Tree());
console.log("left_S_T show_Tree:" + b_T.left_S_T.show_Tree());
console.log("right_S_T show_Tree:" + b_T.right_S_T.show_Tree());
}
function test_6() {
var description = "Checking an `insert_Sub_Tree()` work ...";
console.log(description);
let test_Data = [[3, 2, 4, 5, 6]];
var values_Arr = Array.from({length: 5}, (v, i) => i);
//
//values_Arr = [1, 4, 3, 5, 2];
//values_Arr = [3, 4, 1, 5, 2];
//values_Arr = [3, 2, 4, 5, 6];
values_Arr = [14, 25, 21, 10, 23, 7, 26, 12, 30, 16, 19];
test_Data.push(values_Arr);
/* unbalance cases|"dangling"
conditions:
when 2 nodes inner + leaf occurs (at the 1-st time)
where inner|parent node|sub tree has only one child
and, in turn, it's parent (grandparent) has only this inner node as child
so => child:left|right or children count:1 and grandchildren count:1
or
sub_Tree.size:3 and the only child.size:2
/// ### Note: condition holds for|when ? tree created with proper insert method ? ### ///
insert(14) -> 14:h+1:BF:0
insert(25) -> 14:h+1:BF:-1, 25:h+1:BF:0
insert(21) -> 14:h+1:BF:-2, 21:h+1:BF:0, 25:h+1:BF:-1
14 21
25 14 25
21 <- rebalance|rotation needed =>
[https://en.wikipedia.org/wiki/AVL_tree#Rebalancing]:
the keys(comparing values) moved only "vertically",
so that
the ("horizontal") in-order sequence of the keys is fully preserved
(which is essential for a binary-search tree).
Rebalancing() -> 14:h1:BF:0, 21:h2:BF:0, 25:h1:BF:0
insert(10) -> 10:h+1:BF:0, 14:h+1:BF:+1, 21:h+1:BF:+1, 25:h1:BF:0
insert(23) -> 10:h1:BF:0, 14:h2:BF:+1, 21:h3:BF:0, 23:h+1:BF:0, 25:h+1:BF:+1
insert(7) -> 7:h+1:BF:0, 10:h+1:BF:+1, 14:h+1:BF:+2, 21:h+1:BF:+1, 23:h1:BF:0, 25:h2:BF:+1
21 21
14 25 10 25
10 23 7 14 23
7 <- rebalance|rotation needed =>
Rebalancing() -> 7:h1:BF:0, 10:h2:BF:0, 14:h1:BF:0, 21:h3:BF:0, 23:h1:BF:0, 25:h2:BF:+1
insert(26) -> 7:h1:BF:0, 10:h2:BF:0, 14:h1:BF:0, 21:h3:BF:0, 23:h1:BF:0, 25:h+1:BF:0, 26:h+1:BF:0
insert(12) -> 7:h1:BF:0, 10:h+1:BF:-1, 12:h+1:BF:0, 14:h+1:BF:+1, 21:h+1:BF:+1, 23:h1:BF:0, 25:h2:BF:0, 26:h1:BF:0
insert(30) -> 7:h1:BF:0, 10:h3:BF:-1, 12:h1:BF:0, 14:h2:BF:+1, 21:h+1:BF:0, 23:h1:BF:0, 25:h+1:BF:-1, 26:h+1:BF:-1, 30:h+1:BF:0
insert(16) -> 7:h1:BF:0, 10:h3:BF:-1, 12:h1:BF:0, 14:h+1:BF:0, 16:h+1:BF:0, 21:h4:BF:0, 23:h1:BF:0, 25:h3:BF:-1, 26:h2:BF:-1, 30:h1:BF:0
21:4=0
10:3=-1 25:3=-1
7:1=0 14:2=0 23:1=0 26:2=-1
12:1=0 16:1=0 30:1=0
insert(19) -> 7:h1:BF:0, 10:h+1:BF:-2, 12:h1:BF:0, 14:h+1:BF:-1, 16:h+1:BF:-1, 19:h+1:BF:0, 21:h+1:BF:+1, 23:h1:BF:0, 25:h3:BF:-1, 26:h2:BF:-1, 30:h1:BF:0
21:5=+1
10:4=-2 25:3=-1
7:1= 0 14:3=-1 23:1= 0 26:2=-1
12:1= 0 16:2=-1 30:1= 0
19:1= 0
Rebalancing() -> 7:h1:BF:0, 10:h2:BF:+1, 12:h3:BF:0, 14:h1:BF:0, 16:h2:BF:0, 19:h1:BF:0, 21:h4:BF:0, 23:h1:BF:0, 25:h3:BF:-1, 26:h2:BF:-1, 30:h1:BF:0
21:5=+1
12:3= 0 25:3=-1
10:2=+1 16:2= 0 23:1= 0 26:2=-1
7:1= 0 14:1= 0 19:1= 0 30:1= 0
toDo: So|also ? parent BF == sum of children's BF ? <- not the case ?
Properties[https://en.wikipedia.org/wiki/AVL_tree#Properties]:
`Balance factors` can be kept up-to-date by
knowing the _previous_ `balance factors`
and the change in `height` –
it is not necessary to know the _absolute_ `height`.
For holding the AVL `balance` information,
two bits per `node` are sufficient.
The height (h) of an 'AVL tree' with (n) nodes
lies in the interval:
log2(n + 1) ≤ h < c log2(n + 2) + b,
where:
b = (c / 2) * log2(5) – 2 ≈ –0.328,
c = 1 / log2(φ) ≈ 1.44,
the golden ratio φ = (1 + √5) ⁄ 2 ≈ 1.618
*/
test_Data.forEach(function(test_item, index, array) {
console.log("for insert order(", test_item.length, "):", test_item);
let b_T = null;
test_item
.forEach(
function(item, index, array) {
// mutated|updated state
b_T = insert_Sub_Tree(
b_T, // where to insert
item, // what has to be inserted
//false
1 == 0
);
}
);
//
console.log(ANSI_REVERSED +
"root.show_Tree():" +
ANSI_RESET + ANSI_MAGENTA + ANSI_YELLOW_B +
b_T.show_Tree() + ANSI_RESET
);
// or just values_Arr.sort();
var in_Order_Labels_Arr = in_Order_Traversal(b_T);
var level_Order_Labels_Map = level_Order_Traversal(b_T);
// ANSI escape codes ruins output, part of info is missing
var padding = //ANSI_RESET + ANSI_REVERSED +
//ANSI_UNDERLINED +
//ANSI_CYAN +
//ANSI_BOLD +
"#";// + ANSI_RESET + ANSI_CYAN;
var drop_Down_Str = hierarchical_Drop_Down(
in_Order_Labels_Arr,
level_Order_Labels_Map,
padding,
//true
1 == 1
);
//
console.log(drop_Down_Str);
/* hierarchical drop down:
###30 [s:1, h:1, BF:0]
##26 [s:2, h:2, BF:-1]
#25 [s:4, h:3, BF:-1]
##23 [s:1, h:1, BF:0]
21 [s:11, h:4, BF:0]
###19 [s:1, h:1, BF:0]
##16 [s:2, h:2, BF:-1]
#14 [s:6, h:3, BF:0]
###12 [s:1, h:1, BF:0]
##10 [s:3, h:2, BF:0]
###7 [s:1, h:1, BF:0]
Expected Output:
7(BF=0) 10(BF=0) 12(BF=0) 14(BF=0) 16(BF=-1) 19(BF=0) 21(BF=0) 23(BF=0) 25(BF=-1) 26(BF=-1) 30(BF=0)
// why unsorted ? or strangely ordered <- it is not a Level|BFS traversal order . ? root -> left -> right ?
21(BF=0') 14(BF=0') 10(BF=0') 7(BF=0') 12(BF=0') 16(BF=-1') 19(BF=0') 25(BF=-1') 23(BF=0') 26(BF=-1') 30(BF=0')
*/
//
if (b_T != null) {
console.log("typeof b_T.show_Tree_Heigh:", typeof(b_T.show_Tree_Height));
//typeof b_T.show_Tree_Heigh: string
//TypeError: b_T.show_Tree_Height is not a function
console.log("root show_Tree:" + b_T.show_Tree_Height());
//root show_Tree:/.<-1:0>.\
if (b_T.left_S_T != null) {
console.log("left_S_T show_Tree:" + b_T.left_S_T.show_Tree());
}
if (b_T.right_S_T != null) {
console.log("right_S_T show_Tree:" + b_T.right_S_T.show_Tree());
}
}
});
}
function test_7() {
var description = "Checking a " + ANSI_BOLD + ANSI_BLUE +
"`get_Sub_Tree_Size`" + ANSI_RESET +
" method work ...";
console.log(description);
var b_T = Inner_Node(1, Inner_Node(2, Leaf(4), Leaf(5)), Leaf(3));
// ANSI_WHITE | ANSI_CYAN
console.log(ANSI_REVERSED + ANSI_GREEN +
"for Inner_Node(1, Inner_Node(2, Leaf(4), Leaf(5)), Leaf(3))" + ANSI_RESET);
console.log(ANSI_REVERSED +
"root.show_Tree():" +
ANSI_RESET + ANSI_MAGENTA + ANSI_YELLOW_B +
b_T.show_Tree() + ANSI_RESET);
console.log(ANSI_REVERSED +
"root.get_Sub_Tree_Size():" +
ANSI_RESET + ANSI_RED + ANSI_GREEN_B +
b_T.get_Sub_Tree_Size() + ANSI_RESET);
console.log(ANSI_REVERSED +
"left_S_T.get_Sub_Tree_Size():" +
ANSI_RESET + ANSI_BLACK + ANSI_GREEN_B +
b_T.left_S_T.get_Sub_Tree_Size() + ANSI_RESET);
console.log(ANSI_REVERSED +
"right_S_T.get_Sub_Tree_Size():" +
ANSI_RESET + ANSI_BLACK + ANSI_GREEN_B +
b_T.right_S_T.get_Sub_Tree_Size() + ANSI_RESET);
}
function test_8() {
const description = "Checking a `swap_Relink()` function work ...";
console.log(description);
const STATE_INFO = /*ANSI_CYAN*/ANSI_BLUE + ANSI_WHITE_B;//ANSI_YELLOW_B;
const RESULT_INFO = ANSI_BOLD + ANSI_GREEN;
// Inner_Node( node_Val, left_S_T, right_S_T )
var b_T_L_L = Inner_Node(3, Inner_Node(2, Leaf(1), null), null);
console.log("for b_T_L_L:" + STATE_INFO + b_T_L_L.show_Tree() + ANSI_RESET);
b_T_L_L = swap_Relink( b_T_L_L, +2 );
console.log("show_Tree() after swap_Relink():" + RESULT_INFO + b_T_L_L.show_Tree() + ANSI_RESET);
var b_T_L_R = Inner_Node(3, Inner_Node(1, null, Leaf(2)), null);
console.log("for b_T_L_R:" + STATE_INFO + b_T_L_R.show_Tree() + ANSI_RESET);
b_T_L_R = swap_Relink( b_T_L_R, +2 );
console.log("show_Tree() after swap_Relink():" + RESULT_INFO + b_T_L_R.show_Tree() + ANSI_RESET);
var b_T_R_R = Inner_Node(1, null, Inner_Node(2, null, Leaf(3)));
console.log("for b_T_R_R:" + STATE_INFO + b_T_R_R.show_Tree() + ANSI_RESET);
b_T_R_R = swap_Relink( b_T_R_R, -2 );
console.log("show_Tree() after swap_Relink():" + RESULT_INFO + b_T_R_R.show_Tree() + ANSI_RESET);
var b_T_R_L = Inner_Node(1, null, Inner_Node(3, Leaf(2), null));
console.log("for b_T_R_L:" + STATE_INFO + b_T_R_L.show_Tree() + ANSI_RESET);
b_T_R_L = swap_Relink( b_T_R_L, -2 );
console.log("show_Tree() after swap_Relink():" + RESULT_INFO + b_T_R_L.show_Tree() + ANSI_RESET);
}
//
function test_9() {
const description = "Checking a `get_UnBalanced_Sub_Tree()` function work ...";
console.log(description);
const STATE_INFO = /*ANSI_CYAN*/ANSI_BLUE + ANSI_WHITE_B;//ANSI_YELLOW_B;
const RESULT_INFO = ANSI_BOLD + ANSI_GREEN;
// Inner_Node( node_Val, left_S_T, right_S_T )
var b_T_L_L = Inner_Node(3, Inner_Node(2, Leaf(1), null), null);
console.log("for b_T_L_L:" + STATE_INFO + b_T_L_L.show_Tree() + ANSI_RESET);
//b_T_L_L = swap_Relink( b_T_L_L, +2 );
console.log(
"get_UnBalanced_Sub_Tree(b_T_L_L)" + RESULT_INFO + get_UnBalanced_Sub_Tree(b_T_L_L) + ANSI_RESET + " ?= " + [{}, +2]
);
var b_T_L_R = Inner_Node(3, Inner_Node(1, null, Leaf(2)), null);
console.log("for b_T_L_R:" + STATE_INFO + b_T_L_R.show_Tree() + ANSI_RESET);
//b_T_L_R = swap_Relink( b_T_L_R, +2 );
console.log(
"get_UnBalanced_Sub_Tree(b_T_L_R)" + RESULT_INFO + get_UnBalanced_Sub_Tree(b_T_L_R) + ANSI_RESET + " ?= " + [{}, +2]
);
var b_T_R_R = Inner_Node(1, null, Inner_Node(2, null, Leaf(3)));
console.log("for b_T_R_R:" + STATE_INFO + b_T_R_R.show_Tree() + ANSI_RESET);
//b_T_R_R = swap_Relink( b_T_R_R, -2 );
console.log(
"get_UnBalanced_Sub_Tree(b_T_R_R)" + RESULT_INFO + get_UnBalanced_Sub_Tree(b_T_R_R) + ANSI_RESET + " ?= " + [{}, -2]
);
var b_T_R_L = Inner_Node(1, null, Inner_Node(3, Leaf(2), null));
console.log("for b_T_R_L:" + STATE_INFO + b_T_R_L.show_Tree() + ANSI_RESET);
//b_T_R_L = swap_Relink( b_T_R_L, -2 );
console.log(
"get_UnBalanced_Sub_Tree(b_T_R_L)" + RESULT_INFO + get_UnBalanced_Sub_Tree(b_T_R_L) + ANSI_RESET + " ?= " + [{}, -2]
);
// "////.<7>.\<10>.\<14>.\<21>//.<23>.\<25>.\\" -> to tree =>
var b_T = Inner_Node(
21,
Inner_Node(
14,
Inner_Node(
10,
Leaf(
7),
null)),
Inner_Node(
25,
Leaf(
23),
null));
// unapply, unpack
var [unBalanced_S_T, unBalanced_S_T_BF] = get_UnBalanced_Sub_Tree(b_T);
console.log("for b_T:" + STATE_INFO + b_T.show_Tree() + ANSI_RESET);
console.log("unBalanced_S_T:" + STATE_INFO + unBalanced_S_T.show_Tree() + ANSI_RESET, "BF:", unBalanced_S_T_BF);
unBalanced_S_T = swap_Relink( unBalanced_S_T, unBalanced_S_T_BF );
console.log("'unBalanced_S_T' after swap_Relink():" + RESULT_INFO + unBalanced_S_T.show_Tree() + ANSI_RESET);
console.log("'b_T' after swap_Relink():" + RESULT_INFO + b_T.show_Tree() + ANSI_RESET);
}
/**/
//test_0();
//test_1();
//test_2();
//test_3();
//test_4();
//test_5();
test_6();
//test_7();
//test_8();
//test_9();
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment