GeezerVison is showing github.com — Algorithm for insertion in BST · Wilsonlsc/AlgorithmVisualizer@c6a22c0
File treeExpand file treeCollapse file tree Open diff view settings algorithm/tree/binary_search_tree
Expand file treeCollapse file tree Open diff view settings Collapse file Copy file name to clipboard +34Lines changed: 34 additions & 0 deletions | Original file line number | Diff line number | Diff line change |
|---|
| | 1 | +function bst_insert ( root, element, parent ) { // node = current node , parent = previous node | | 2 | + tracer._visit ( root, parent )._wait (); | | 3 | + 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 (); | | 8 | + logger._print( element + ' Inserted '); | | 9 | + } 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 ); | | 22 | + } | | 23 | + } | | 24 | +} | | 25 | + | | 26 | +var Root = elements[0]; // take first element as root | | 27 | +logger._print ( Root + ' Inserted as root of tree '); | | 28 | +tracer._setTreeData ( G, Root ); | | 29 | + | | 30 | +for (var i = 1; i < elements.length; i++) { | | 31 | + tracer2._select ( i )._wait(); | | 32 | + bst_insert ( Root, elements[i] ); // insert ith element | | 33 | + tracer2._deselect( i ); | | 34 | +} |
Collapse file Copy file name to clipboard +34Lines changed: 34 additions & 0 deletions | Original file line number | Diff line number | Diff line change |
|---|
| | 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 | +]; | | 29 | + | | 30 | +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 "); | | 32 | +var tracer2 = new Array1DTracer ( " Elements ")._setData ( elements ); | | 33 | +var logger = new LogTracer ( " Log "); | | 34 | +tracer.attach ( logger ); |
Collapse file Copy file name to clipboardExpand all lines: algorithm/tree/binary_search_tree/desc.json +3-2Lines changed: 3 additions & 2 deletions | Original file line number | Diff line number | Diff line change |
|---|
| 4 | 4 | "Search applications where data is constantly entering/leaving such as map and set objects in many languages' library." | 5 | 5 | ], | 6 | 6 | "Complexity": { | 7 | | - "time": "Best : O(1) Average : O(logN) Worst : O(N)", | | 7 | + "time": " Best : O(1) Average : O(logN) Worst : O(N) ", | 8 | 8 | "space": "O(n)" | 9 | 9 | }, | 10 | 10 | "References": [ | 11 | 11 | "<a href='https://en.wikipedia.org/wiki/Binary_search_tree'>Wikipedia</a>" | 12 | 12 | ], | 13 | 13 | "files": { | 14 | | - "bst_search": "Search in Binary Search Tree" | | 14 | + "bst_search": "Search in Binary Search Tree", | | 15 | + "bst_insert": "Insert in Binary Search Tree" | 15 | 16 | } | 16 | 17 | } |
|