A Binary Search Tree can be an empty Tree or a Binary Tree with the following properties: if the left subtree is not empty, the value of all nodes in the left subtree is less than the value of the root node; If its right subtree is not empty, the value of all nodes in the right subtree is greater than the value of its root node. Its left and right subtrees are also binary sort trees respectively. As a classical data structure, binary search tree has the advantages of quick insertion and deletion of linked list and quick search of array. Therefore, it is widely used, for example, in file system and database system, this data structure is generally used for efficient sorting and retrieval operations
The definition of the tree
A tree consists of a set of nodes joined by edges. An example of a tree is the organization chart of a company, as shown below
An organization chart is used to describe the structure of an organization. In Figure 10-1, each box is a node, and the lines connecting the boxes are called edges. Nodes represent positions in the organization and describe the relationships between positions. For example, if the CIO reports directly to the CEO, the two are connected by a single edge. The development manager reports to the CIO, also connected by an edge. The vice Director of Sales and the development manager do not have a direct connection, so the two nodes are not connected by an edge.
The tree below shows more tree terminology, which will be covered in a subsequent discussion. The topmost node of a tree is called the root node. If more than one node is connected below it, the node is called the parent, and the nodes below it are called the children. A node can have zero, one, or more child nodes. A node without any children is called a leaf node.
A tree can be divided into several levels, with the root node at level 0, its children at level 1, its children at level 2, and so on. Nodes at any level of the tree can be regarded as the root of the subtree, which contains the children of the root node and the children of the children, etc. We define the number of layers of the tree as the depth of the tree.
This top-down tree is counter-intuitive. In the real world, the roots of the tree are at the bottom. Top-down trees are a long-standing habit in computer science. In fact, computer scientist Gartner tried to change this habit, but within a few months he realized that most computer scientists were unwilling to describe trees in a natural, bottom-up way, and the matter had to be dropped. Finally, each node has a value associated with it, which is sometimes called a key.
Binary trees and binary lookup trees
The search process of a binary sorting tree is similar to that of a suboptimal binary sorting tree. An ordered sequence of keywords can be obtained by traversing a binary sorting tree. An unordered sequence can be transformed into an ordered sequence by constructing a binary sorting tree. The process of constructing a binary sorting tree is the process of sorting unordered sequences. The new node inserted each time is the new leaf node in the binary sorting tree. During the insertion operation, there is no need to move other nodes, but only need to change the pointer of a node from null to non-null. Search, insert, delete is order log of n, tree height.
Each node in a binary tree cannot have more than two children. By limiting the number of child nodes to 2, you can write efficient programs that insert, find, and delete data in the tree. The following figure shows a binary tree
When considering a particular kind of binary tree, such as a binary search tree, it is important to determine the child nodes. A binary search tree is a special binary tree in which relatively small values are stored in the left node and large values in the right node. This feature makes lookups efficient, both for numeric and non-numeric data, such as words and strings.
Implement binary search tree
To realize the Node
Binary lookup trees are made up of nodes, so the first object we define is Node, which is similar to a linked list. The Node class is defined as follows:
class Node {
constructor(key) {
this.key = key;
this.left = null;
this.right = null; }}Copy the codeThe Node object holds both data and links (left and right) to other nodes.
Realization of BST
You can now create a class that represents a binary lookup tree (BST). We let the class contain only one data member: a Node object representing a binary lookup root Node. The constructor of this class initializes the root node to NULL to create an empty node. BST starts with an insert() method that adds new nodes to the tree. This method is a bit complicated and needs to be explained in detail. The first step is to create a Node object and pass data into it for storage. Second, check whether BST has a root node. If not, then this is a new tree and the node is the root node, and the method is done. Otherwise, go to the next step. If the node to be inserted is not the root node, you need to prepare to traverse the BST to find the appropriate place to insert. The process is similar to traversing a linked list. Layer by layer through the BST, storing the current node with a variable. After entering the BST, the next step is to decide where to put the nodes. When the correct insertion point is found, the loop is broken. The algorithm for finding the correct insertion point is as follows.
- Let the root node be the current node.
- If the data of the node to be added is smaller than that of the current node, set the new current node to the left node of the original node. the
- Perform Step 4.
- If the left node of the current node is null, the new node is inserted into the position and the loop exits. Instead, continue
- Execute the next loop.
- Set the new current node to be the right node of the original node.
- If the right node of the current node is null, the new node is inserted into this position and the loop exits. Instead, continue
- Execute the next loop.
With the algorithm above, you are ready to implement the BST class.
class BinarySearchTree {
constructor() {
this.root = null;
}
insert(key) {
/ / insert
const newNode = new Node(key);
if (this.root === null) {
this.root = newNode;
} else {
this.insertNode(this.root, newNode); }}insertNode(node, newNode) {
if (newNode.key < node.key) {
if (node.left === null) {
node.left = newNode;
} else {
this.insertNode(node.left, newNode); }}else {
if (node.right === null) {
node.right = newNode;
} else {
this.insertNode(node.right, newNode); }}}}Copy the codeThere are three ways to traverse the BST: middle-order, pre-order, and post-order. In order to access all nodes on the BST in ascending order based on the key value on the node. Sequential traversal first accesses the root node and then the left and right subtrees in the same manner. A back-order traversal visits the leaf node first, from the left to the right subtree, and then to the root node
Add middle-order, pre-order, and post-order traversal
class BinarySearchTree {...inOrderTraverse(callback) {
// Find in order
this.inOrderTraverseNode(this.root, callback);
}
preOrderTraverse(callback) {
// search first
this.preOrderTraverseNode(this.root, callback);
}
postOrderTraverse(callback) {
// after the search
this.postOrderTraverseNode(this.root, callback);
}
inOrderTraverseNode(node, callback) {
if(node ! = =null) {
this.inOrderTraverseNode(node.left, callback);
callback(node.key);
this.inOrderTraverseNode(node.right, callback); }}preOrderTraverseNode(node, callback) {
if(node ! = =null) {
callback(node.key);
this.preOrderTraverseNode(node.left, callback);
this.preOrderTraverseNode(node.right, callback); }}postOrderTraverseNode(node, callback) {
if(node ! = =null) {
this.postOrderTraverseNode(node.left, callback);
this.postOrderTraverseNode(node.right, callback); callback(node.key); }}}Copy the codeSearch in the binary search tree
There are usually three types of lookups for BST:
- Find the given value;
- Find the minimum value;
- Find the maximum.
class BinarySearchTree {...min() {
/ / the minimum
return this.minNode(this.root);
}
max() {
/ / Max
return this.maxNode(this.root);
}
search(key) {
/ / to find
this.searchNode(this.root, key);
}
minNode(node) {
if (node) {
while(node && node.left ! = =null) {
node = node.left;
}
return node.key;
}
return null;
}
maxNode(node) {
if (node) {
while(node && node.right ! = =null) {
node = node.right;
}
return node.key;
}
return null;
}
searchNode(node, key) {
if (node === null) return false;
if (key < node.key) {
return this.searchNode(node.left, key);
} else if (key > node.key) {
return this.searchNode(node.right, key);
} else {
return true; }}findMinNode(node) {
if (node) {
while(node && node.left ! = =null) {
node = node.left;
}
return node.key;
}
return null; }}Copy the codeRemoves a node from a binary lookup tree
class BinarySearchTree {...remove(key) {
// Remove the tree node
this.removeNode(this.root, key);
}
removeNode(node, key) {
if (node === null) return null;
if (key < node.key) {
node.left = this.removeNode(node.left, key);
return node;
} else if (key > node.key) {
node.right = this.removeNode(node.right, key);
return node;
} else {
if (node.left === null && node.right === null) {
node = null;
return node;
} else if (node.left === null) {
node = node.right;
return node;
} else if (node.right === null) {
node = node.left;
return node;
}
const aux = this.findMinNode(node.right);
node.key = aux.key;
node.right = this.removeNode(node.right, aux.key);
returnnode; }}}Copy the codeThe complete code
class Node {
constructor(key) {
this.key = key;
this.left = null;
this.right = null; }}class BinarySearchTree {
constructor() {
this.root = null;
}
insert(key) {
/ / insert
const newNode = new Node(key);
if (this.root === null) {
this.root = newNode;
} else {
this.insertNode(this.root, newNode);
}
console.log(this.root);
}
inOrderTraverse(callback) {
// Find in order
this.inOrderTraverseNode(this.root, callback);
}
preOrderTraverse(callback) {
// search first
this.preOrderTraverseNode(this.root, callback);
}
postOrderTraverse(callback) {
// after the search
this.postOrderTraverseNode(this.root, callback);
}
min() {
/ / the minimum
return this.minNode(this.root);
}
max() {
/ / Max
return this.maxNode(this.root);
}
search(key) {
/ / to find
this.searchNode(this.root, key);
}
remove(key) {
// Remove the tree node
this.removeNode(this.root, key);
}
insertNode(node, newNode) {
if (newNode.key < node.key) {
if (node.left === null) {
node.left = newNode;
} else {
this.insertNode(node.left, newNode); }}else {
if (node.right === null) {
node.right = newNode;
} else {
this.insertNode(node.right, newNode); }}}inOrderTraverseNode(node, callback) {
if(node ! = =null) {
this.inOrderTraverseNode(node.left, callback);
callback(node.key);
this.inOrderTraverseNode(node.right, callback); }}preOrderTraverseNode(node, callback) {
if(node ! = =null) {
callback(node.key);
this.preOrderTraverseNode(node.left, callback);
this.preOrderTraverseNode(node.right, callback); }}postOrderTraverseNode(node, callback) {
if(node ! = =null) {
this.postOrderTraverseNode(node.left, callback);
this.postOrderTraverseNode(node.right, callback); callback(node.key); }}minNode(node) {
if (node) {
while(node && node.left ! = =null) {
node = node.left;
}
return node.key;
}
return null;
}
maxNode(node) {
if (node) {
while(node && node.right ! = =null) {
node = node.right;
}
return node.key;
}
return null;
}
searchNode(node, key) {
if (node === null) return false;
if (key < node.key) {
return this.searchNode(node.left, key);
} else if (key > node.key) {
return this.searchNode(node.right, key);
} else {
return true; }}removeNode(node, key) {
if (node === null) return null;
if (key < node.key) {
node.left = this.removeNode(node.left, key);
return node;
} else if (key > node.key) {
node.right = this.removeNode(node.right, key);
return node;
} else {
if (node.left === null && node.right === null) {
node = null;
return node;
} else if (node.left === null) {
node = node.right;
return node;
} else if (node.right === null) {
node = node.left;
return node;
}
const aux = this.findMinNode(node.right);
node.key = aux.key;
node.right = this.removeNode(node.right, aux.key);
returnnode; }}findMinNode(node) {
if (node) {
while(node && node.left ! = =null) {
node = node.left;
}
return node.key;
}
return null; }}Copy the codeReference books
Data structures and algorithms described in JavaScript