preface
A tree is a non-sequential data structure used to store data that needs to be found quickly. There are many examples of trees in real life, such as family trees, organizational charts of companies, etc.
This article explores binary search trees implemented in TypeScript. Interested developers are welcome to read this article.
Implementation approach
A node in a binary tree can have at most two child nodes: one on the left and one on the right.
Binary search tree is a kind of binary tree, which is different from binary tree:
- The left child of each node must be smaller than itself
- The right child of each node must be larger than itself
This article mainly explains the concrete realization of the tree, do not understand the basic knowledge of the tree developers please move: data structure: binary search tree
The realization of binary search tree
According to the characteristics of binary search tree, each node has two child nodes. The left child node must be smaller than the parent node, and the right child node must be larger than the parent node.
Create a secondary class Node
First, we need a class that describes each node in the binary tree. Given the characteristics of binary trees, the class we create must contain the following attributes:
- The key node values
- Left A reference to the left child node
- Right A reference to the right child node
Like a linked list, we will represent the relationship between nodes by Pointers. In a bidirectional linked list, each node contains two Pointers, one to the next node and two to the previous node. The tree works the same way (using two Pointers), but the tree has one pointer to the left child and the other to the right child.
The following figure shows a binary tree where the links between nodes are Pointers.
Create the basic structure of a binary search tree
We control the first node of this data structure (root node), which in the tree is root, by declaring a variable in the same way as a linked list.
Next, let’s analyze the method to achieve a binary search tree:
- Insert (key): Inserts a node into the tree
- Search (key): Finds a key in the tree. Returns true if the node exists, false otherwise
- Min (): Returns the smallest value/key in the tree
- Max (): Returns the largest value/key in the book
- Remove (key): Removes a key from the tree
Inserts a new node into the tree
- Verify that the insert operation is a special case: the root Node is null. If the root Node is null, create an instance of the Node class and assign it to root, pointing root to the newly created Node
- If the root node is not null, we need to find a suitable place to insert the child node, so we need to implement a helper method, insertNode
- The insertNode method takes two arguments: where do you want to start, and the key of the node you want to insert
- The binary search tree has one characteristic: the left child node is smaller than the parent node, and the right byte point is larger than the parent node. So we need to create a comparison method, compareFn
- The compareFn method takes two arguments: the value to be compared, and the original value. Returns -1 if less, 1 if greater, and 0 if equal
- Call the compareFn method to determine whether the key to be inserted is smaller than the key of the current node
- If it is less than, determine whether the left child Node of the current Node is null. If it is null, create Node Node and point it to the left child Node; otherwise, recursively call insertNode method from the position of the left child Node of the current Node to find the appropriate position
- If it is, determine whether the right child Node of the current Node is null. If it is null, create Node Node and point it to the right child Node; otherwise, recursively call insertNode method from the position of the right child Node of the current Node to find the appropriate location
Let’s use an example to illustrate the above process.
We want to insert the following data into the binary tree: 30 21 25 18 17 35 33 31
- First, insert 30, at which point the root Node is null, and create a Node to point it to root
- Then, I insert 21, and I compare 21 to 30, 21 is less than 30. Insert at the left child node of 30. The left child node of 30 is null. So directly insert
- Then, 25 < 30 is inserted at the left child of 30, at which point the left child of 30 already has 21. Recursively, insertNode is called to compare the size of 25 and 21, 25 > 21, so it is inserted at the right child of 21
- And so on until all nodes are inserted.
Search for values in the tree
Within trees, there are three types of searches that are frequently performed:
- Search minimum
- In the last example, after we inserted all the nodes into the binary tree, we found that the leftmost node of the tree was the smallest key in the tree
- So all we have to do is go from the root node all the way down the left subtree to find the smallest node
- Search maximum
- The right-most node of the tree is the largest key in the tree
- So we just have to go from the root node all the way down the right subtree to find the largest node
- Search for a specific value
- We start by declaring a method search, which takes one parameter: the key to look for, and it needs a helper method searchNode
- The searchNode takes two parameters: the node to look up and the key to look up, which can be used to look up a particular value of a tree or any of its subtrees
- The first step is to verify that the node passed to the parameter is valid (not null or undefined). If the key is not found, return false
- The compareFn method is called to compare the size of the key of the node being searched with that of the current node
- If the node you are looking for is smaller than the key of the current node, the searchNode method is recursively called, passing the left child of the current node and the key you are looking for
- If the node you are looking for is larger than the key of the current node, the searchNode method is recursively called, passing in the right child of the current node and the key to copy
- Otherwise, the node is found and returns true
Next, let’s use an example to describe the process of searching for a specific value.
The following figure shows a binary search tree, and we need to determine whether 25 is in the tree:
- Call the search method to find the key 25, and call the searchNode method to find the key from the root node, so pass root and the key to find
- First, node is not empty, so continue to determine the size of the key and the root node key, 25 < 30, recurse its left subtree
- Then, compare the size of 25 and 21, 25 > 21, recurse its right subtree
- At this point, 25 === 21, the node is found, return true
Remove a node
Remove the node in the tree, which takes a key, requires a helper method called removeNode, which takes two parameters: the node, the key to remove.
RemoveNode implementation is as follows:
- First, it checks whether the node is null, and returns null if it is
- Call the compareFn method to compare the size of the key to be removed with the current node key
- If the key to be removed is smaller than the current node key, the removeNode method is recursively called to pass the left child and key of the current node
- If the key to be removed is larger than the current node key, the removeNode method is recursively called to pass the current node’s right child and key
- Otherwise, the node to be deleted is found, and there may be three cases of node deletion:
- Both the left and right children of the current node are null, so we simply point the node to NULL to remove it
- The current node contains either a left child or a right child. If the left child is null, point the current node to the right child of the current node. If the right child is null, point the current node to the left child of the current node.
- The current node has two child nodes. You need to perform four steps:
- We need to find the smallest node in the right subtree
- Update the key of the current node with the key of the smallest node in the right subtree
- After the update is complete, there are redundant keys in the tree, and you need to call removeNode to remove them
- Updates a reference to a node to its parent
- Both the left and right children of the current node are null, so we simply point the node to NULL to remove it
Traversal of binary search tree
Walking through a tree is the process of visiting each node of the tree and performing some kind of operation on them. There are three ways to access all nodes of the tree:
- In the sequence traversal
- The first sequence traversal
- After the sequence traversal
Tree traversal is accessed in the form of recursion. For developers who do not understand recursion, please go to: understanding and implementation of recursion
In the sequence traversal
Middle-order traversal is a traversal that accesses the nodes of a tree in ascending order, that is, all nodes are accessed in ascending order. One application scenario of middle-order traversal is to sort the tree. Next, we will analyze the implementation of middle-order traversal:
- Declare the inOrderTraverse method to take as an argument a callback function that defines what we do to each node we traverse. Intermediate traversal is recursive, so we need an auxiliary method, inOrderTraverseNode
- The inOrderTraverseNode method takes two arguments: a node and a callback function
- Recursive baseline condition node== NULL
- Recursively calls the inOrderTraverseNode method, passing the left child of the current node and the callback function
- Call the callback function
- Recursively calls the inOrderTraverseNode method, passing the right child of the current node and the callback function
Next, we use an example to describe the middle order traversal process
As shown above, the blue characters indicate the order in which the nodes are accessed, and the orange lines indicate recursive calls until the node is null and then the callback function is executed. The specific execution process is as follows:
11=>7=>5=>3 ode:3, left:undefined callback(node.key) 3 right:undefined allback(node.key) 5 node:5, right:6 left:undefined callback(node.key) 6 right: undefined callback(node.key) 7 node:7, right:9 left:8 left:undefined callback(node.key) 8 right:undefined callback(node.key) 9 right:10 left:undefined callback(node.key) 10 right:undefined allback(node.key) 11 node:11, right:15 left:13 left:12 left:undefined callback(node.key) 12 right:undefined callback(node.key) 13 right:14 left:undefined callback(node.key) 14 right:undefined ...... . right:25 left:undefined 25 callback(node.key)Copy the codeThe first sequence traversal
A sequential traversal accesses each node in order of precedence over descendant nodes. One application of the sequential traversal is to print a structured document. Next, we analyze the specific implementation of the sequential traversal:
- Declare the preOrderTraverse method, which receives the same parameters as the mid-order traversal, and which also requires a secondary method, preOrderTraverseNode
- The preOrderTraverseNode method takes the same parameters as the middle-order traversal
- Base condition for recursion: node == NULL
- Call the callback function
- Recursively calls the preOrderTraverseNode method, passing the left child of the current node and the callback function
- Recursively calls the preOrderTraverseNode method, passing the right child of the current node and the callback function
Next, we use an example to describe the process of sequential traversal:
The specific execution process is as follows:
node:11 callback(node.key) 11 node.left=7 ode:7 callback(node.key) 7 node.left=5 ode:5 callback(node.key) 5 ode.left=3 node:3 callback(node.key) 3 node.left=undefined,node.right=undefined => node:5 node:5 node.right = 6 callback(node.key) 6 node:6 node.left=undefined,node.right=undefined => node:7 node:7 node.right = 9 callback(node.key) 9 ...... . callback(node.key) 25Copy the codeAfter the sequence traversal
A back-order traversal visits the descendants of a node first and then the node itself. One application of post-order traversal is to calculate the space occupied by all files in a directory and its subdirectories. Next, we will analyze the implementation of post-order traversal:
- Declare the postOrderTraverse method, receiving the same parameters as the mid-order traverse
- Declare the postOrderTraverseNode method that receives the same parameters as the mid-order traversal
- The baseline condition for recursion is node == NULL
- Recursively calls the postOrderTraverseNode method, passing the left child of the current node and the callback function
- Recursively calls the postOrderTraverseNode method, passing the right child of the current node and the callback function
- Call the callback function
Next, we use an example to describe the execution process of post-order traversal.
As shown in the figure above, blue characters indicate the order in which the nodes are executed, and orange lines indicate recursive calls until the node is null and then the callback function is executed.
The specific execution process is as follows:
11=>7=>5=>3 node:3 left:undefined right:undefined callback(node.key) 3 node:5 right:6 ode:6 left:undefined right:undefined callback(node.key) 6 node:5 callback(node.key) 5 node:7 right: 9 node:9 left:8 node:8 left:undefined right:undefined callback(node.key) 8 node:9 right:10 node:10 left:undefined right:undefined callback(node.key) 10 node:9 callback(node.key) 9 node:7 callback(node.key) 7 ... . callback(node.key) 11Copy the codeThe implementation code
Before we analyzed the implementation of binary search tree ideas, we will talk about the above ideas into code.
Creating secondary nodes
- Create the node.ts file
- Create a Node class and add attributes to the class based on the Node attributes
export class Node<K> {
public left: Node<K> | undefined;
public right: Node<K> | undefined;
constructor(public key: K) {
this.left = undefined;
this.right = undefined;
}
toString() {
return `${this.key}`; }}Copy the codeFor the complete code, go to node.ts
Create the basic structure of a binary tree
- Create the binarySearchtree.ts file
- Declare the root node and the alignment function
protected root: Node<T> | undefined;
constructor(protected compareFn: ICompareFunction<T> = defaultCompare) {
this.root = undefined;
};
Copy the codeexport type ICompareFunction<T> = (a: T, b: T) = > number;
export function defaultCompare<T> (a:T, b:T) {
if (a === b){
return Compare.EQUALS;
}else if(a > b) {
return Compare.BIGGER_THAN;
}else {
returnCompare.LESS_THAN; }}Copy the code- Implement node insertion
insert(key: T){
if (this.root == null) {// If the root node does not exist, create a new node
this.root = new Node(key);
}else {
// Insert child nodes in the root node
this.insertNode(this.root,key); }}protected insertNode(node: Node<T>, key: T) {
// If the key of the new node is smaller than the key of the current node, the new node is inserted to the left of the current node
// If the key of the new node is greater than the key of the current node, insert the new node to the right of the current node
if (this.compareFn(key,node.key) === Compare.LESS_THAN){
if (node.left == null) {// The left subtree of the current node is null and inserted directly
node.left = new Node(key);
}else {
// Recurse down from the current node (left subtree) to find the null position and insert it
this.insertNode(node.left,key); }}else{
if (node.right == null) {// The right subtree of the current node is null and inserted directly
node.right = new Node(key);
}else {
// Recurse down from the current node (right subtree) to find the null position and insert it
this.insertNode(node.right,key); }}}Copy the code- Gets the maximum, minimum, and specific node values for a node
// Search for the value of a specific node
search(key: T){
return this.searchNode(<Node<T>>this.root, key);
}
private searchNode(node: Node<T>, key: T): boolean | Node<T>{
if (node == null) {return false;
}
if (this.compareFn(key, node.key) === Compare.LESS_THAN){
// The key to look for is on the left of the node
return this.searchNode(<Node<T>>node.left, key);
} else if(this.compareFn(key, node.key) === Compare.BIGGER_THAN){
// The key is on the right side of the node
return this.searchNode(<Node<T>>node.right, key);
} else{
// The node has been found
return true; }}// Get the smallest node of the tree
min(){
return this.minNode(<Node<T>>this.root);
}
protected minNode(node: Node<T>): Node<T>{
let current = node;
while(current ! =null&& current.left ! =null){
current = current.left;
}
return current;
}
// Get the maximum node of the tree
max(){
return this.maxNode(<Node<T>>this.root);
}
private maxNode(node: Node<T>){
let current = node;
while(current ! =null&& current.right ! =null){
current = current.right;
}
return current;
}
Copy the code- Implement node removal
remove(key: T){
this.removeNode(<Node<T>>this.root,key);
}
protected removeNode(node: Node<T> | null, key: T){
// The node being detected is null, i.e. the key does not exist in the tree
if (node == null) {return null;
}
// Not null, you need to find the key to remove in the tree
if (this.compareFn(key,node.key) === Compare.LESS_THAN){ // If the target key is less than the value of the current node, look along the left side of the tree
node.left = <Node<T>>this.removeNode(<Node<T>>node.left, key);
return node;
} else if (this.compareFn(key,node.key) === Compare.BIGGER_THAN){ // If the target key is greater than the value of the current node, look along the right side of the tree
node.right = <Node<T>>this.removeNode(<Node<T>>node.right, key);
return node;
} else{
// The key is equal to key, which needs to be handled in three cases
if (node.left == null && node.right == null) {// Remove a leaf node that has no left or right children
// Point the node to null to remove it
node = null;
return node;
}
if (node.left == null) {// Remove a node from the left child node
// Node has a right child node, so references to it need to be changed to references to its right child node
node = <Node<T>>node.right;
// Returns the updated node
return node;
} else if(node.right == null) {// Remove a node from the right child node
// Node has a left child node, so references to it need to be references to its left child node
node = node.left;
// Returns the updated node
return node;
}
// Remove a node with two children
const aux = this.minNode(node.right); // When you find the node to remove, you need to find the smallest node in the right subtree, which is its successor
node.key = aux.key; // Update the node key with the smallest node key in the right subtree
// After updating node's keys, there are two identical keys in the tree, so we need to remove the extra keys
node.right = <Node<T>>this.removeNode(node.right, aux.key) // Remove the smallest node in the right subtree
return node; // Returns the updated node}}Copy the codeTraversal of binary trees
Next we implement middle-order, pre-order, post-order traversal
- In order to achieve traversal
inOrderTraverse(callback: Function) {this.inOrderTraverseNode(<Node<T>>this.root,callback);
}
private inOrderTraverseNode(node: Node<T>,callback: Function) {if(node ! =null) {this.inOrderTraverseNode(<Node<T>>node.left,callback);
callback(node.key);
this.inOrderTraverseNode(<Node<T>>node.right,callback); }}Copy the code- Implement sequential traversal
preOrderTraverse(callback: Function) {this.preOrderTraverseNode(<Node<T>>this.root, callback);
}
private preOrderTraverseNode(node: Node<T>, callback: Function) {if(node ! =null){
callback(node.key);
this.preOrderTraverseNode(<Node<T>>node.left, callback);
this.preOrderTraverseNode(<Node<T>>node.right, callback); }}Copy the code- After the realization of the sequence traversal
postOrderTraverse(callback: Function) {this.postOrderTraverseNode(<Node<T>>this.root, callback);
}
private postOrderTraverseNode(node: Node<T>, callback: Function) {
if(node ! =null) {this.postOrderTraverseNode(<Node<T>>node.left, callback);
this.postOrderTraverseNode(<Node<T>>node.right, callback); callback(node.key); }}Copy the codeFor the complete code, go to BinarySearchtree.ts
Write test code
We have implemented the binary search tree and its basic methods, now let’s test whether the above code can be properly executed.
const binarySearchTree = new BinarySearchTree();
binarySearchTree.insert(11);
binarySearchTree.insert(7);
binarySearchTree.insert(15);
binarySearchTree.insert(5);
binarySearchTree.insert(3);
binarySearchTree.insert(9);
binarySearchTree.insert(8);
binarySearchTree.insert(10);
binarySearchTree.insert(13);
binarySearchTree.insert(12);
binarySearchTree.insert(14);
binarySearchTree.insert(20);
binarySearchTree.insert(18);
binarySearchTree.insert(25);
binarySearchTree.insert(6);
// Test the sequential traversal function
const printNode = (value) = > console.log(value);
console.log("Middle order traversal");
binarySearchTree.inOrderTraverse(printNode);
// Test sequential traversal
console.log("Sequential traversal");
binarySearchTree.preOrderTraverse(printNode);
// Test sequence traversal
console.log("Post-order traversal");
binarySearchTree.postOrderTraverse(printNode);
// Test get the minimum function
console.log("Minimum of a tree",binarySearchTree.min());
// Test to get the maximum function
console.log("Maximum of the tree",binarySearchTree.max());
// Test the search node function
console.log("Eight is in the binary tree.",binarySearchTree.search(8));
console.log("100 is in the binary tree.",binarySearchTree.search(100));
// Test node deletion
console.log("Delete node 3");
binarySearchTree.remove(3);
binarySearchTree.inOrderTraverse(printNode);
Copy the codeFor the complete code, go to BinarySearchTreeTest
The result is as follows:
Write in the last
- If there are any errors in this article, please correct them in the comments section. If this article helped you, please like it and follow 😊
- This article was first published in nuggets. Reprint is prohibited without permission 💌