Skip to content

Commit 6b5f1a8

Browse files
authored
Merge pull request algorithm-visualizer#221 from rajraku/master
Tracer to depict addition of nodes in binary search tree
2 parents 47010c4 + 0546562 commit 6b5f1a8

File tree

4 files changed

+500
-48
lines changed

4 files changed

+500
-48
lines changed
Original file line numberDiff line numberDiff line change
@@ -1,34 +1,32 @@
1-
function bst_insert ( root, element, parent ) { // node = current node , parent = previous node
1+
function bst_insert ( root, element, parent ) { // root = current node , parent = previous node
22
tracer._visit ( root, parent )._wait ();
3+
var treeNode = T[root];
4+
var propName = '';
35
if ( element < root ) {
4-
if ( T[root][0] === -1 ) { // insert as left child of root
5-
T[root][0] = element;
6-
G[root][element] = 1; // update in graph
7-
tracer._visit ( element, root )._wait ();
6+
propName = 'left';
7+
} else if ( element > root) {
8+
propName = 'right';
9+
}
10+
if(propName !== '') {
11+
if ( !treeNode.hasOwnProperty(propName) ) { // insert as left child of root
12+
treeNode[propName] = element;
13+
T[element] = {};
14+
tracer._addNode(element, root)._wait();
815
logger._print( element + ' Inserted ');
916
} else {
10-
//tracer._clear ();
11-
bst_insert ( T[root][0], element, root );
12-
}
13-
} else if ( element > root ) { // insert as right child of root
14-
if( T[root][1] === -1 ) {
15-
T[root][1] = element;
16-
G[root][element] = 1; // update in graph
17-
tracer._visit ( element, root )._wait ();
18-
logger._print ( element + ' Inserted ');
19-
} else {
20-
//tracer._clear ();
21-
bst_insert ( T[root][1], element, root );
17+
bst_insert ( treeNode[propName], element, root );
2218
}
2319
}
2420
}
2521

2622
var Root = elements[0]; // take first element as root
23+
T[Root] = {};
24+
tracer._addRoot(Root);
2725
logger._print ( Root + ' Inserted as root of tree ');
28-
tracer._setTreeData ( G, Root );
2926

3027
for (var i = 1; i < elements.length; i++) {
3128
tracer2._select ( i )._wait();
3229
bst_insert ( Root, elements[i] ); // insert ith element
33-
tracer2._deselect( i );
30+
tracer2._deselect( i )._wait();
31+
tracer._clearTraversal();
3432
}
Original file line numberDiff line numberDiff line change
@@ -1,34 +1,7 @@
1-
var G = [ // G[i][j] indicates whether the path from the i-th node to the j-th node exists or not
2-
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
3-
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
4-
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
5-
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
6-
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
7-
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
8-
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
9-
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
10-
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
11-
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
12-
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
13-
];
14-
15-
16-
var T = [ // mapping to G as a binary tree , [i][0] indicates left child, [i][1] indicates right child
17-
[-1,-1],
18-
[-1,-1],
19-
[-1,-1],
20-
[-1,-1],
21-
[-1,-1],
22-
[-1,-1],
23-
[-1,-1],
24-
[-1,-1],
25-
[-1,-1],
26-
[-1,-1],
27-
[-1,-1]
28-
];
1+
var T = {};
292

303
var elements = [5,8,10,3,1,6,9,7,2,0,4]; // item to be searched
31-
var tracer = new DirectedGraphTracer( " BST - Elements marked red indicates the current status of tree ");
4+
var tracer = new DirectedGraphConstructTracer( " BST - Elements marked red indicates the current status of tree ", 0);
325
var tracer2 = new Array1DTracer ( " Elements ")._setData ( elements );
336
var logger = new LogTracer ( " Log ");
347
tracer.attach ( logger );

0 commit comments

Comments
 (0)