JS Implements Binary Sort Tree
Preface
_Binary sorting tree was not intended to be written, there was no difficulty found, want to start directly from the rotation of the AVL tree, but because I saw an interview topic from others, I inserted Key's code in my handwriting, so I thought I would do it.
_There is still a big difference between theory and practice, so if you have time, you should take a look at it yourself. There may still be a lot of problems in defining and understanding. For example, in my mind, the value of a node is usually expressed as value, so when you just see a problem, you say insertKey, I did not react at once, which should be put in the interview, this question is basically gone. The problem of Lu Xun and Zhou Shuren is quite confusing. Of course, more than that, I debugged several times when writing. Many places were not very thoughtful at first, there were bugs and haha. If the interview made me work hard, the code would not run without the help of a compiler.
concept
Binary Sort Tree, also known as Binary Search Tree, or Binary Search Tree, is a type of data structure. In general, query efficiency is higher than chain table structure.
Definition 1:
An empty tree, or a binary tree of the following properties:
(1) If the left subtree is not empty, the values of all nodes in the left subtree are less than the values of its root nodes;
(2) If the right subtree is not empty, the values of all nodes in the right subtree are larger than the values of its root nodes.
(3) The left and right subtrees are also binary sort trees;
(4) There are no nodes with equal key values.
PS: There are three relationships between the root node of a binary sorted tree and the left and right leaf nodes. Three definitions have been derived. Here, only one example is given, as shown in detail. Binary Sort Tree-Baidu Encyclopedia
The restriction of a binary tree can be simply understood as ordering the data in a left-small-right-large rule
Three relationships:
Definition 1: Any left subtree node <root node <any right subtree node
Definition 2: Any left subtree node <=root node <any right subtree node
Definition three: any left subtree node < root node < = any right subtree node
Summary of the problem
_Although we debugged a lot of time in js grammar, initialization, recursive export, return, etc., there is no place where people get stuck, how much time to think, I don't want to remember, the ideas are all in the code, the only thing I want to say is where nodes are deleted. Here I read some blogs, including Baidu Encyclopedia,Some are not written correctly, others are too long, especially Baidu Encyclopedia I don't know how many times I have to read to get his semantics. I don't get his meaning.
_So delete this and I'll make a note of it.
_If we want to delete a node, assuming that it is 8, there are several cases:
1, left and right subtrees are empty.
In this case, simply delete the node
|-----------3-----------|
|-----2-----| |-----8-----|
1
↓
|-----------3-----------|
|-----2-----|
1
2, left subtree is empty, right subtree is not empty
_Delete the node directly, point the original parent node to the pointer to delete the node, point to the right subtree to delete the node
|-----------3-----------|
|-----2-----| |-----8-----|
1 |--10--|
9 11
↓
|-----------3-----------|
|-----2-----| |-----10-----|
1 9 11
3, the right subtree is empty, the left subtree is not empty
_Delete the node directly, point the original parent node to the pointer to delete the node, and point to the left subtree to delete the node
|-----------3-----------|
|-----2-----| |-----8-----|
1 |--6--|
5 7
↓
|-----------3-----------|
|-----2-----| |-----6-----|
1 5 7
4, neither left nor right subtree is empty
Mode 1: Query the maximum value of the left subtree of the deleted node, assign its key to the deleted node, and delete the maximum node of the left subtree
Mode 2: Query the minimum value of the right subtree of the deleted node, assign its key to the deleted node, and delete the minimum value of the right subtree node
_What is the idea? I think so, delete this node, then find a place to fill it. What is the relationship between this node and its subtree? The root node must be smaller than any node of the right subtree and larger than any node of the left subtree. Who can fill it? It's easy to come out, the largest one on the left, or the smallest one on the right, and then delete the original node when it's filled in(as above, 1, 2, 3).
|-----------3-----------|
|-----2-----| |-----8-----|
1 |--6--| |--10--|
5 7 9 11
Mode 1: ↓
|-----------3-----------|
|-----2-----| |-----7-----|
1 |--6--| |--10--|
5 9 11
Mode 2: ↓
|-----------3-----------|
|-----2-----| |-----9-----|
1 |--6--| |--10--|
5 7 11
What? I can't understand it at all. What's the difference between Baidu Encyclopedia and Baidu Encyclopedia? Well, it's really hard to understand this kind of thing in words, so I recommend one for you Data Structure Dynamic Demonstration Site This is not only a demonstration of inserting and deleting data structures, but also a demonstration of sorting algorithms.
Code
. /TreeUnit.js? See Command Line Print Binary Tree
import treeUnit from './TreeUnit.js'
function TreeCode() {
var tree = null
let BinarySearchTree = function (value) {
this.key = value;
this.left = null;
this.right = null;
}
this.createTree = function () {
this.insert(3)
this.insert(2)
this.insert(1)
this.insert(8)
this.insert(6)
this.insert(5)
this.insert(7)
this.insert(10)
this.insert(9)
this.insert(11)
return tree;
}
this.createTreeArray = () => {
//Pre-order traversal
function NLR(biTree, index) {
if (biTree === null) return;
treeArray[index] = biTree.key
NLR(biTree.left, 2 * index + 1);
NLR(biTree.right, 2 * index + 2);
}
let treeArray = []
NLR(tree, 0)
return treeArray
}
/**
* insert
* @param {number} key Key Values of Nodes
*/
this.insert = function (key) {
function insert(tree) {
if (key <= tree.key) {
if (tree.left) {
insert(tree.left)
} else {
tree.left = new BinarySearchTree(key);
}
} else {
if (tree.right) {
insert(tree.right)
} else {
tree.right = new BinarySearchTree(key);
}
}
}
if (tree === null) {
tree = new BinarySearchTree(key);
} else {
insert(tree)
}
}
/**
* query
* @param {number} tree Key Values of Nodes
* @returns Query results, if returned
*/
function search(key) {
function search(tree) {
if (tree) {
if (tree.key === key) {
return tree
} else if (key < tree.key) {
return search(tree.left)
} else {
return search(tree.right)
}
}
}
return search(tree)
}
/**
* delete
* @param {number} tree Key Values of Nodes
*/
function deleteNode(key) {
function deleteNode(tree, key) {
if (tree) {
if (tree.key === key) {
if (tree.left && tree.right) {
var minKey = minNode(tree.right).key
tree.key = minKey
tree.right = deleteNode(tree.right, minKey)
} else if (tree.left) {
return tree.left
} else if (tree.right) {
return tree.right
} else {
return null
}
} else if (key < tree.key) {
tree.left = deleteNode(tree.left, key)
} else {
tree.right = deleteNode(tree.right, key)
}
return tree
}
}
deleteNode(tree, key)
}
function minNode(tree) {
if (!tree) {
console.log("not find")
} else if (tree.left) {
return minNode(tree.left)
} else {
return tree
}
}
this.search = (key) => {
var result = search(key)
return result === undefined ? -1 : result.key
}
this.delete = (key) => {
deleteNode(key)
}
}
var tree = new TreeCode();
tree.createTree()
treeUnit.printTree(tree.createTreeArray())
console.log("Find results:" + tree.search(8))
tree.delete(8)
console.log("Delete Vertex: 8")
treeUnit.printTree(tree.createTreeArray())
console.log("Find results:" + tree.search(8))