%20copy.gif)
This is a continuation of a series introducing data structures in javascript. A binary tree is a tree
based data structure in which each node has at most two child nodes. The child nodes are typically
referred to as the left and right nodes. Nodes with children are called parent nodes. The absolute
first node in the tree is referred to as the root node.
A binary search tree is a binary tree that is organized with the following properties:
– The left subtree of a node contains only nodes with keys that are less than the nodes key.
– The right subtree of a node contains only nodes with keys that are greater than the nodes key.
– Both the left and right subtrees must also be binary trees
With the data inserted into the tree in this manner, searching becomes more effecient than within an array
because traversal of the data structure can logically exclude elements for comparison. Traversing the structure
from the root node, a greater than or less than check will eliminate half of the data to be compared; assuming
that it is a perfectly balanced tree.
Each node in a binary search tree is similar to a doubly linked list in that they contain some data as well
as two pointers to other nodes. The key difference from a doubly linked list is that the nodes relate to
one another.
A javascript implementation of such a node would look like the following:
1var node = {
2 data: 17,
3 left: null,
4 right: null
5}
The first step in building a binary search tree implementation is to define a custom type with a single property
that represents the root node.
1function BinarySearchTree() {
2 this.root = null;
3}
To insert a value into the tree you must traverse the tree using the rules that are defined earlier in this document.
The one special case is when no root node exists; denoting that the node to be inserted is the root node.
1BinarySearchTree.prototype = {
2 insert: function(data){
3 var node = {
4 data: data,
5 left: null,
6 right: null
7 };
8
9 var currentNode;
10
11 if (this.root === null){
12 this.root = node;
13 } else {
14 currentNode = this.root;
15
16 while(true){
17 if (data < currentNode.data){
18 if (currentNode.left === null){
19 currentNode.left = node;
20 break;
21 } else {
22 currentNode = currentNode.left;
23 }
24 } else if (data > currentNode.data){
25 if (currentNode.right === null){
26 currentNode.right = node;
27 break;
28 } else {
29 currentNode = currentNode.right;
30 }
31 } else {
32 break;
33 }
34 }
35 }
36 },
37};
Removal of a node from a binary search tree is can be a complex operation because the
tree must remain balanced. This means that all values on the left must be less than
all of the values on the right. There are two special cases to consider when removing
a node as well; existence of the node must be checked as well as determination if the
node to be removed is the root node.
When removing a node, the number of children for that node must be taken into consideration
since the operations become slightly different depending on the number. Removing a node with
two children is the most complex.
1BinarySearchTree.prototype = {
2 remove: function(data){
3
4 var found = false;
5 var parentNode = null;
6 var currentNode = this.root;
7 var childCount;
8 var replacementNode;
9 var replacementParent;
10
11 while(!found && currentNode){
12 if (data < currentNode.data){
13 parentNode = currentNode;
14 currentNode = currentNode.left;
15 } else if (value > current.value){
16 parentNode = currentNode;
17 currentNode = currentNode.right;
18 } else {
19 found = true;
20 }
21 }
22
23 if (found){
24 childCount = (current.left !== null ? 1 : 0) +
25 (current.right !== null ? 1 : 0);
26
27 if (currentNode === this.root){
28 switch(childCount){
29 case 0:
30 this.root = null;
31 break;
32 case 1:
33 this.root = (currentNode.right === null ?
34 currentNode.left : currentNode.right);
35 break;
36 case 2:
37 replacementNode = this.root.left;
38
39 while (replacementNode.right !== null){
40 replacementParent = replacementNode;
41 replacementNode = replacementNode.right;
42 }
43
44 if (replacementParent !== null){
45 replacementParent.right = replacementNode.left;
46
47 replacementNode.right = this.root.right;
48 replacementNode.left = this.root.left;
49 } else {
50 replacementNode.right = this.root.right;
51 }
52
53 this.root = replacementNode;
54 }
55 } else {
56 switch (childCount){
57 case 0:
58 if (currentNode.data < parentNode.data){
59 parent.left = null;
60 } else {
61 parentNode.right = null;
62 }
63 break;
64 case 1:
65 if (currentNode.data < parentNode.data){
66 parentNode.left = (currentNode.left === null ?
67 currentNode.right : currentNode.left);
68 } else {
69 parentNode.right = (currentNode.left === null ?
70 currentNode.right : currentNode.left);
71 }
72 break;
73 case 2:
74 replacementNode = currentNode.left;
75 replacementParent = currentNode;
76
77 while(replacementNode.right !== null){
78 replacementParent = replacementNode;
79 replacementNode = replacementNode.right;
80 }
81
82 replacementParent.right = replacementNode.left;
83
84 replacementNode.right = currentNode.right;
85 replacementNode.left = currentNode.left;
86
87 if (currentNode.data < parentNode.data){
88 parentNode.left = replacementNode;
89 } else {
90 parentNode.right = replacementNode;
91 }
92 }
93 }
94 }
95 },
96};
A generic method to traverse the array is useful to have for cases where you may want
to convert the values in the tree to an array or a string.
1BinarySearchTree.prototype = {
2 traverse: function(evaluate){
3 function iterate(node){
4 if (node){
5 if (node.left !== null){
6 iterate(node.left);
7 }
8
9 evaluate.call(this, node);
10
11 if (node.right !== null){
12 iterate(node.right);
13 }
14 }
15 }
16 iterate(this.root);
17 },
18
19 toArray: function(){
20 var result = [];
21
22 this.traverse(function(node){
23 result.push(node.data);
24 });
25
26 return result;
27 },
28
29 toString: function(){
30 return this.toArray().toString();
31 },
32};
Below are some simple usage examples for this implementation of a binary
search tree in JavaScript.
1var bst = new BinarySearchTree();
2bst.add(17);
3bst.add(11);
4bst.add(43);
5bst.add(9);
6bst.add(65);
7bst.remove(43);
8
9document.writeln(bst.toString()); // prints 9 11 17 65
Copyright © Design & Developed by Yojimbo Corp.
