Binary search method

Let’s start by introducing a search method that will be used in the following binary search tree processing. Note:

  • Binary search must be used in an ordered sequence.

Goal:

If target is found, return idnex:

  • In an array, [left…right] looks for target.
  • Binary lookup is as simple as finding the middle index value and determining whether target is larger or smaller than the middle value.
  • If it is equal to the middle value, return index.
  • If the value is less than the middle value, the next step is to look in [left…index-1] and discard the index.
  • If the value is greater than the intermediate value, search for [index+1…right] and discard the index.
  • If no, return -1.
function binarySrerch(arr, int, Let left = 0 let right = n-1 while (left <= right) { // let index = (left + right) / 2 Let index = left + (right-left) / 2 if (arr[index] === target) {return index; } if (target < arr[index]) {// Find target right = index-1 in arr[left... index-1] else {// Find target right = index-1 in arr[index -1]... Target left = index + 1}} return -1; }Copy the code

Binary search tree

The data structure

Binary search tree data structure is dictionary data structure (lookup table/table structure) as shown below:

Binary search tree

It’s essentially a binary tree. See below:Properties of binary search trees:

The left and right children of each node are small on the left and large on the right.

We know that the data structure of the heap is a complete binary tree, and a binary search tree is not necessarily a complete binary tree. So instead of using array data structures, it makes more sense to use table structures.

Insert a node

If we want to insert a 60 into the binary search tree below, how do we insert it?

Ideas:

  • The inserted data should first be compared with the node.
  • Larger than the root node, it will be inserted to the right of this node
  • If there is a right-hand node, the comparison continues with the right-hand node.
  • If not, it will be inserted.
  • If equal data is found during the search, overwrite it directly.

Below:

  • 61 is bigger than 41. It’s to the right of 41.
  • 61 is bigger than 58, and then to the right of 58.
  • It is found that there is only one left node under 58, which is inserted directly into the right child node of 58.
  • If equal data is found during the search, overwrite it directly.

This completes an insert. Now that we’re clear, let’s look at our code

// Insert a node (key, Class Node {key value left right root = null count = 0 constructor(key, constructor) value) { this.key = key this.value = value this.left = this.right = null } size() { return this.count; } isEmpty() { return this.count === 0; } insert(key, value) { this.root = this._insert(this.root, key, value) } contain(key) { return this._contain(this.root, } // Binary search tree with node as root, Insert node (key, value) // Return the root of the binary search tree after inserting a new node. _insert(node, key, value) { if (node === null) { this.count++ return new Node(key, value) } if (value === node.key) { node.key = value } else if (value < node.key) { node.left = this._insert(node.left, key, value) } else { node.right = this._insert(node.right, key, _contain(node, _contain(node, _contain(node, _contain())); key) { if (node === null) { return false } if (key in node) { return true } else { return this._contain(node.left, Key) | | this. _contain (node. Right, key)}}} / / / * data structure is so may need to insert/a key corresponding to find the position * / let the node = {a: 1, left: {b: 2, left: null, right: null }, right: { c: 3, left: null, right: null } }Copy the code

The above may not understand, look at the code below.

  • The following code is just an example
function _contain(node, key) {
    if (node === null) {
        return false
    }
    if (key in node) {
        return true
    } else {
        return this._contain(node.left, key) || this._contain(node.right, key)
    }
}
let node = {
    a: 1,
    left: { b: 2, left: null, right: null },
    right: { c: 3, left: null, right: null }
}
console.log(_contain(node, "b")) // true
console.log(_contain(node, "d")) // false
Copy the code

We know how to pass in node to see if there is a key. Can passing in value find the corresponding value?

In fact, passing in value for search is the same as inserting. You can find where the value is inserted, but can’t find the corresponding value?

Let’s look at the code (including the previous insert code, so we don’t need to look up) :

// Insert a node (key, Class Node {key value left right root = null count = 0 constructor(key, constructor) value) { this.key = key this.value = value this.left = this.right = null } size() { return this.count; } isEmpty() { return this.count === 0; } insert(key, value) { this.root = this._insert(this.root, key, value) } contain(key) { return this._contain(this.root, Key)} search(value) {return this._search(this.root, value)} Insert node (key, value) // Return the root of the binary search tree after inserting a new node. _insert(node, key, value) { if (node === null) { this.count++ return new Node(key, value) } if (value === node.key) { node.key = value } else if (value < node.key) { node.left = this._insert(node.left, key, value) } else { node.right = this._insert(node.right, key, _contain(node, _contain(node, _contain(node, _contain())); key) { if (node === null) { return false } if (key in node) { return true } else { return this._contain(node.left, Key) | | this. _contain (node. Right, key)}} / / in the node as the root of the binary search tree to find whether there is a value value _search (node, value) { if (node === null) { return null } if (value === node.key) { return node.key } else if (value < node.key) { return this._search(node.left, value) } else { return this._search(node.right, Let node = {a: 1, left: {b: 2, left: null, right: {a: 1, left: {b: 2, left: null, right: null }, right: { c: 3, left: null, right: null } }Copy the code

conclusion

We now understand binary search tree insertion and search operations.

Next, we will continue to study binary search trees, with respect to their front, middle and back traversal.