Detailed explanation of using JS binary search tree
This time I will bring you a detailed explanation of the use of JS binary search trees. What are the precautions when using JS binary search trees? The following is a practical case. Get up and take a look.
What is a binary tree
A binary tree means that each node of the tree can only have at most two child nodes
What is a binary search tree
On the basis of the binary tree, the binary search tree has an additional condition, that is, when inserting a value in the binary tree, if the inserted value is smaller than the current node, it will be inserted into the left node, otherwise it will be inserted into the right node; if during the insertion process, the left node or If the right node already exists, then continue to compare according to the above rules until a new node is encountered.
Characteristics of binary search trees
Due to its unique data structure, the binary search tree has a time complexity of O(h) whether it is adding, deleting or searching. h is the height of the binary tree. Therefore, the binary tree should be as short as possible, that is, the left and right nodes should be as balanced as possible.
Construction of binary search tree
To construct a binary search tree, you must first construct the node class of the binary tree. It can be seen from the characteristics of binary trees that each node class has a left node, a right node and the value itself, so the node class is as follows:
class Node {
constructor(key) {
this.key = key;
this.left = null;
this.right = null;
}
}Then construct a binary search tree
class Tree{
constructor(param = null) {
if (param) {
this.root = new Node(param);
} else {
this.root = null;
}
}
}Here this.root is the tree of the current object.
Binary search treeNew addition
Due to the characteristics of the binary search tree that the left subtree is smaller than the node and the right subtree is larger than the node, the new algorithm for the binary search tree can be easily written, as follows:
insert(key) {
if (this.root === null) {
this.root = new Node(key);
} else {
this._insertNode(this.root, key);
}
}
_insertNode(node, key) {
if (key < node.key) {
if (node.left === null) {
node.left = new Node(key);{1}
} else {
this._insertNode(node.left, key);{2}
}
} else if (key > node.key) {
if (node.right === null) {
node.right = new Node(key);{3}
} else {
this._insertNode(node.right, key);{4}
}
}
}The above code first determines the key size of the newly added key and the current node. If it is smaller, it recursively traverses the left child node until it finds a null left child node; if it is larger than the current node, the same principle applies. The reason why the above code {1}{2}{3}{4} can change the value of this.root is because the JavaScript function is passed by value, and when the parameter is a non-basic type, such as here Object, the value of its object is memory, so the content of this.root will be directly changed every time.
Traversal of binary search tree
Binary search trees are divided into three traversal methods: preorder, inorder, and postorder.
inOrderTraverse(callback) {
this._inOrderTraverse(this.root, callback);
}
_inOrderTraverse(node, callback) {
if (node) {
this._inOrderTraverse(node.left, callback);
callback(node.key);
this._inOrderTraverse(node.right, callback);
}
}The above is an in-order traversal.
The thing to understand here is recursion. You know, the execution of a function can be abstracted into a data structure - a stack. For the execution of the function, a stack is maintained to store the execution of the function. Each time the function recurses, it will push the current execution environment onto the stack and record the execution location. Taking the above code as an example, there is the following data
It will start from 11, execute {1} to the stack, then go to 7, then execute {1} to the stack, then go to 5, execute {1} to the stack, and then go to 3, execute {1} to the stack. At this time, it is found that The left child node of node 3 is null, so it starts to pop off the stack. At this time, the execution environment of node 3 pops up, execute {2}, {3}, and find that the right child node of 3 is also null, and the recursive execution of {3} is completed. , then pop up node 5, execute {2}{3}, then pop up node 7, execute {2}{3} onto the stack, when executing {3}, it is found that node 7 has a right node, so continue executing {1}, to the node 8, execute {1} again, 8 has no left child node, {1} is executed, {2}{3} is executed, and so on.
The difference between preorder and midorder is that the node itself is visited first, that is, the execution order of the code is 2 1 3.
The same applies to the post-order, the execution order is 1 3 2
It is not difficult to find that no matter the order is before, during or after, the left node is always recursed first. When the left node is traversed, the stack is popped and all nodes are traversed. The only difference between them is the timing of accessing the node itself.
Binary search tree search
The search is very simple, just make a loop judgment based on the principle that the left child node is smaller than the node and the right child node is larger than the node.
search(value) {
if (this.root) {
if (value === this.root.key) {
return true;
} else {
return this._searchNode(value, this.root);
}
}
throw new Error('this.root 不存在');
}
_searchNode(value, node) {
if (!node) {
return false;
}
if (value === node.key) {
return true;
}
if (value > node.key) {
return this._searchNode(value, node.right);
} else if (value < node.key) {
return this._searchNode(value, node.left);
}
}Binary search treeDelete
Deletion is more complicated and needs to be judged according to different situations
First determine whether the node has a left subtree. If there is no left subtree, directly replace the deleted node with the root node of the right subtree;
If there is, replace the deleted node with the smallest node of the right subtree;
remove(key) {
this._removeNode(this.root, key);
}
_removeNode(node, value) {
if (!node) {
return null;
}
if (value > node.key) {
node.right = this._removeNode(node.right, value);
} else if (value < node.key) {
node.left = this._removeNode(node.left, value);
} else {
// 如果没有左子树，那么将右子树根节点作为替换节点
if (!node.left) {
return node.right;
// 如果存在左子树，那么取右子树最小节点作为替换节点
} else if (node.left) {
return this._minNode(node.right);
}
}
}总结
总的来说，通过这次简单的二叉搜索树的学习，让我重新认识了递归，以前对于递归的理解只是一些简单的理论概念，这次深入实践让我对递归的理解又加深了许多。
这让我想到了数学的学习，数学的理论公式是很容易记住掌握的，如果说对一个知识点的掌握满分是十分，那么直到真正去实践它之前，只看公式的掌握只能是2分，因为公式很简单，就几句话几个原则，但是遇到的问题是千变万化的，只有真正将理论付诸实践，经过各种实践的打磨蹂躏，才能真正理解它其中的奥秘。
相信看了本文案例你已经掌握了方法，更多精彩请关注php中文网其它相关文章！
推荐阅读：
The above is the detailed content of Detailed explanation of using JS binary search tree. For more information, please follow other related articles on the PHP Chinese website!
Hot AI Tools
Undresser.AI Undress
AI-powered app for creating realistic nude photos
AI Clothes Remover
Online AI tool for removing clothes from photos.
Undress AI Tool
Undress images for free
Clothoff.io
AI clothes remover
Video Face Swap
Swap faces in any video effortlessly with our completely free AI face swap tool!
Hot Article
Hot Tools
Notepad++7.3.1
Easy-to-use and free code editor
SublimeText3 Chinese version
Chinese version, very easy to use
Zend Studio 13.0.1
Powerful PHP integrated development environment
Dreamweaver CS6
Visual web development tools
SublimeText3 Mac version
God-level code editing software (SublimeText3)
Hot Topics
What software is crystaldiskmark? -How to use crystaldiskmark?
Mar 18, 2024 pm 02:58 PM
CrystalDiskMark is a small HDD benchmark tool for hard drives that quickly measures sequential and random read/write speeds. Next, let the editor introduce CrystalDiskMark to you and how to use crystaldiskmark~ 1. Introduction to CrystalDiskMark CrystalDiskMark is a widely used disk performance testing tool used to evaluate the read and write speed and performance of mechanical hard drives and solid-state drives (SSD). Random I/O performance. It is a free Windows application and provides a user-friendly interface and various test modes to evaluate different aspects of hard drive performance and is widely used in hardware reviews
How to download foobar2000? -How to use foobar2000
Mar 18, 2024 am 10:58 AM
foobar2000 is a software that can listen to music resources at any time. It brings you all kinds of music with lossless sound quality. The enhanced version of the music player allows you to get a more comprehensive and comfortable music experience. Its design concept is to play the advanced audio on the computer The device is transplanted to mobile phones to provide a more convenient and efficient music playback experience. The interface design is simple, clear and easy to use. It adopts a minimalist design style without too many decorations and cumbersome operations to get started quickly. It also supports a variety of skins and Theme, personalize settings according to your own preferences, and create an exclusive music player that supports the playback of multiple audio formats. It also supports the audio gain function to adjust the volume according to your own hearing conditions to avoid hearing damage caused by excessive volume. Next, let me help you
How to use Baidu Netdisk app
Mar 27, 2024 pm 06:46 PM
Cloud storage has become an indispensable part of our daily life and work nowadays. As one of the leading cloud storage services in China, Baidu Netdisk has won the favor of a large number of users with its powerful storage functions, efficient transmission speed and convenient operation experience. And whether you want to back up important files, share information, watch videos online, or listen to music, Baidu Cloud Disk can meet your needs. However, many users may not understand the specific use method of Baidu Netdisk app, so this tutorial will introduce in detail how to use Baidu Netdisk app. Users who are still confused can follow this article to learn more. ! How to use Baidu Cloud Network Disk: 1. Installation First, when downloading and installing Baidu Cloud software, please select the custom installation option.
How to use NetEase Mailbox Master
Mar 27, 2024 pm 05:32 PM
NetEase Mailbox, as an email address widely used by Chinese netizens, has always won the trust of users with its stable and efficient services. NetEase Mailbox Master is an email software specially created for mobile phone users. It greatly simplifies the process of sending and receiving emails and makes our email processing more convenient. So how to use NetEase Mailbox Master, and what specific functions it has. Below, the editor of this site will give you a detailed introduction, hoping to help you! First, you can search and download the NetEase Mailbox Master app in the mobile app store. Search for "NetEase Mailbox Master" in App Store or Baidu Mobile Assistant, and then follow the prompts to install it. After the download and installation is completed, we open the NetEase email account and log in. The login interface is as shown below
BTCC tutorial: How to bind and use MetaMask wallet on BTCC exchange?
Apr 26, 2024 am 09:40 AM
MetaMask (also called Little Fox Wallet in Chinese) is a free and well-received encryption wallet software. Currently, BTCC supports binding to the MetaMask wallet. After binding, you can use the MetaMask wallet to quickly log in, store value, buy coins, etc., and you can also get 20 USDT trial bonus for the first time binding. In the BTCCMetaMask wallet tutorial, we will introduce in detail how to register and use MetaMask, and how to bind and use the Little Fox wallet in BTCC. What is MetaMask wallet? With over 30 million users, MetaMask Little Fox Wallet is one of the most popular cryptocurrency wallets today. It is free to use and can be installed on the network as an extension
Detailed explanation of obtaining administrator rights in Win11
Mar 08, 2024 pm 03:06 PM
Windows operating system is one of the most popular operating systems in the world, and its new version Win11 has attracted much attention. In the Win11 system, obtaining administrator rights is an important operation. Administrator rights allow users to perform more operations and settings on the system. This article will introduce in detail how to obtain administrator permissions in Win11 system and how to effectively manage permissions. In the Win11 system, administrator rights are divided into two types: local administrator and domain administrator. A local administrator has full administrative rights to the local computer
Detailed explanation of division operation in Oracle SQL
Mar 10, 2024 am 09:51 AM
Detailed explanation of division operation in OracleSQL In OracleSQL, division operation is a common and important mathematical operation, used to calculate the result of dividing two numbers. Division is often used in database queries, so understanding the division operation and its usage in OracleSQL is one of the essential skills for database developers. This article will discuss the relevant knowledge of division operations in OracleSQL in detail and provide specific code examples for readers' reference. 1. Division operation in OracleSQL
Teach you how to use the new advanced features of iOS 17.4 'Stolen Device Protection'
Mar 10, 2024 pm 04:34 PM
Apple rolled out the iOS 17.4 update on Tuesday, bringing a slew of new features and fixes to iPhones. The update includes new emojis, and EU users will also be able to download them from other app stores. In addition, the update also strengthens the control of iPhone security and introduces more "Stolen Device Protection" setting options to provide users with more choices and protection. "iOS17.3 introduces the "Stolen Device Protection" function for the first time, adding extra security to users' sensitive information. When the user is away from home and other familiar places, this function requires the user to enter biometric information for the first time, and after one hour You must enter information again to access and change certain data, such as changing your Apple ID password or turning off stolen device protection.
