This article mainly introduces the binary search tree sequence traversal.

First, the important concepts behind sequence traversal are introduced:

  • Depth first
  • breadth-first

What is depth-first traversal?

Depth-first traversal: simply speaking, it is depth-first. Our binary search tree, whether preordered, middle ordered or post ordered, traversal is carried out in depth first. Look at this binary search tree:

We looked for 28, then 16, 13, then 16, then 22, then back to 28, then 30, 29, 42, and so on.

We’re going to go from one node to the bottom, and then we’re going to go to the other node, and that’s called depth-first traversal.

What is breadth first traversal?

Breadth-first traversal: simply called breadth-first, breadth-first traversal is also called sequencing traversal.

Breadth-first traversal is breadth-first. Look at this binary search tree:

Our breadth-first lookup order is:

  • Look for the root node 28, then look for the left subtree 16 of 28.
  • End Go back to 28 and find the right subtree 30.
  • I’m going to look for the left subtree of 16, 13, and then I’m going to look for the right subtree, 22.
  • And then you go to 30, and then you go to 29, and then you go to 42.

We’ll find that breadth-first is looking at a layer by layer, rather than finding the deepest part of a node like depth-first.

How to implement breadth-first traversal?

Usually we implement a breadth-first traversal that requires a queue data structure. Queue data structures have a feature of first-in, first-out, last-in, last-out.

Again, the binary search tree example above:

  • Our queue data structure is an array. We will first store the root node 28 in the array and search for it.
  • After searching and finding that 28 is not desirable, we will eject 28 from the queue, that is, remove it from the array.
  • The left and right subtrees are then stored in an array and searched.
  • Search for left subtree 16 does not correspond to left subtree 16, pop left subtree 16, and store the left and right subtrees of 16 into the array.
  • So we have a right subtree of 30, left subtree of 13, and right subtree of 22 in our array, so we’re going to keep searching, 30 is not the right subtree, we’re going to pop 30 off the queue, we’re going to store 30 or so subtrees in our array.
  • At this point, the array has 13, 22, 29, 42, and search until the search is complete.

Here are the elements in the front queue when the queue is ejected in 16:Here’s what’s left in front of the queue at 30:

Code:

// Insert node (key, root) into binary search tree 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; /* node: search tree value: front: search tree value: front: search tree Queue * / levelOrder (node, Value) {let front = [] front. Push (node) while (front. Length > 0) {let front = [] front (currentNode.key === value) {console.log(currentNode) return true} else {// If currentNode.left! == null) { front.push(currentNode.left) } if (currentNode.right ! == null) {front. Push (currentNode.right)}} return false}}} key: 28, left: { key: 16, left: { key: 13, left: null, right: null }, right: { key: 22, left: null, right: null } }, right: { key: 30, left: { key: 29, left: null, right: null }, right: { key: 42, left: null, right: null } } }Copy the code

Binary search tree removes nodes

It is easy to search for a node, and it is easy to delete a node. After deleting a node, how to operate the left subtree and right subtree under a node?

Let’s think about what the minimum and maximum values of the binary search tree look like if the node I want to delete is a binary search tree?

  • Starting with the root node 28, the lowest left subtree is the minimum
  • Starting from the root node 28, the lowest right subtree is the maximum

Search for the smallest node:

// In a binary search tree rooted in node, return the node with the smallest key. function _minimum(node) { if (node.left === null) { return node } return this._minimum(node.left) } let node = { key: 28, left: { key: 16, left: { key: 13, left: null, right: null }, right: { key: 22, left: null, right: null } }, right: { key: 30, left: { key: 29, left: null, right: null }, right: { key: 42, left: null, right: null } } } _minimum(node) // {key: 13, left:null, right:null}Copy the code

Search for the maximum node:

function _maximum(node) {
    if (node.right === null) {
        return node
    }
    return this._maximum(node.right)
}
let node = {
    key: 28,
    left: {
        key: 16,
        left: { key: 13, left: null, right: null },
        right: { key: 22, left: null, right: null }
    },
    right: {
        key: 30,
        left: { key: 29, left: null, right: null },
        right: { key: 42, left: null, right: null }
    }
}
_maximum(node)
// {key: 42, left: null, right: null}
Copy the code

Searching for the maximum and minimum values of the binary search tree we already know, how to remove the minimum value of the binary search tree?

Consider the following figure: If you remove the minimum value of 22, how do you deal with nodes 33 and beyond?

If you delete 22, you need to move 33 to 22.

Using a similar thread, consider how to remove the maximum value of the binary search tree in the following image:As you can see, just delete 58 and put 50 where 58 is.Code implementation:

// Delete the smallest node in the binary search tree. Function _removeMin(node) {if (node.left === null) {const nodeRight = node.right; delete node; return nodeRight; } node.left = this._removemin (node.left) return node; } let node = { key: 28, left: { key: 16, left: { key: 13, left: null, right: null }, right: { key: 22, left: null, right: null } }, right: { key: 30, left: { key: 29, left: null, right: null }, right: { key: 42, left: null, right: null } } }Copy the code

Delete the maximum node in the binary search tree and go directly to the code:

function _removeMax(node) {
    if (node.right === null) {
        const nodeRight = node.right
        delete node
        return nodeRight
    }
    node.right = this._removeMax(node.right)
    return node;
}
let node = {
    key: 28,
    left: {
        key: 16,
        left: { key: 13, left: null, right: null },
        right: { key: 22, left: null, right: null }
    },
    right: {
        key: 30,
        left: { key: 29, left: null, right: null },
        right: { key: 42, left: null, right: null }
    }
}
Copy the code

By deleting the minimum and maximum values, you don’t need to consider whether they still exist below, or if there are two nodes.

So, what if we want to delete any node, that node has two subtrees, left and right, and there are subtrees under the subtree?

If we want to delete the 58 node, what should we do?

And then we need another algorithm: Hubbard Deletion

If we delete 58, who will replace 58?

  • It should be the minimum in the right subtree of 58, so that it’s bigger than the left subtree of the deleted node, and smaller than the right subtree of the deleted node.
  • All nodes in the right subtree of 58 will be greater than 50, and only the left subtree of 60 will be less than 60.

If s is node 59 and d is node 58:

  • First, find node 59, the successor of node 60, delete this node and save it.
  • Set the right of 59 to: 60 Delete the node after 59 (the current right of 58).
  • Set the left of 59 to the left of 58.
  • Finally, replace the whole node of 59 with the node of 58.

Code implementation:

// Delete the node whose root value is value from the binary search tree. // Return the root of the new binary search tree after deletion. function _remove(node, value) { if (node === null) { return null } if (value < node.key) { node.left = this._remove(node.left, value) return node } if (value > node.key) { node.right = this._remove(node.right, If (value === node.key) {if (node.left === null) {const nodeRight = this._remove(node.right) delete node return nodeRight } if (node.right === null) { const nodeLeft = Succeeded = this._remove(node.left) delete node return nodeLeft} // Find the successor of node const succeeded = this._minimum(node.right) // For the next node, Right = this._removemin (node.right) forerunner. Left = node.left delete node return succeeded}} // Returns the node with the smallest key in a binary search tree rooted in node. function _minimum(node) { if (node.left === null) { return node } return this._minimum(node.left) } // Delete the smallest node in the binary search tree with root node. Function _removeMin(node) {if (node.left === null) {const nodeRight = node.right; delete node; return nodeRight; } node.left = this._removemin (node.left) return node; } let node = { key: 41, left: { key: 22, left: { key: 15, left: { key: 13, left: null, right: null }, right: null }, right: { key: 33, left: null, right: { key: 37, left: null, right: null } } }, right: { key: 58, left: { key: 50, left: { key: 42, left: null, right: null }, right: { key: 53, left: null, right: null } }, right: { key: 60, left: { key: 59, left: null, right: null }, right: {key: 63, left: null, right: null} } } }Copy the code

More complete code:

// Insert node (key, root) into binary search tree 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; {if (this.count === 0) {throw new Error("node is null")} const minNode = If (this.count === 0) {throw new Error("node is "); if (this.count === 0) } const minNode = this._maximum(this.root) return minnode.key} removeMin() {if (this.root! == null) { this.root = this._removeMin(this.root) } } remove(key) { this.root = this._remove(this.root, RemoveMax () {if (this.root! == null) {this.root = this._removemax (this.root)}} // Return the least key node in the binary search tree with node as root. _minimum(node) {if (node.left === null) {return node} return this._minimum(node.left)} // In a binary search tree rooted by node, the node with the largest key value is returned. _maximum(node) {if (node.right === null) {return node} return this._maximum(node.right)} // Delete the smallest node in the binary search tree. _removeMin(node) {if (node.left === null) {// Check if there is const nodeRight = node.right; delete node; return nodeRight; } node.left = this._removemin (node.left) return node; } // Delete the largest node in the binary search tree. _removeMax(node) {if (node.right === null) {const nodeRight = node.right delete node return nodeRight } node.right = this._removeMax(node.right) return node; } // Delete the node whose root is node from the binary search tree. // Return the root of the new binary search tree after deletion. _remove(node, value) { if (node === null) { return null } if (value < node.key) { node.left = this._remove(node.left, value) return node } if (value > node.key) { node.right = this._remove(node.right, If (value === node.key) {if (node.left === null) {const nodeRight = this._remove(node.right) delete node return nodeRight } if (node.right === null) { const nodeLeft = Succeeded = this._remove(node.left) delete node return nodeLeft} // Find the successor of node const succeeded = this._minimum(node.right) // For the next node, Right = this._removemin (node.right) forerunner. Left = node.left delete node return succeeded}}} // /* Let node = {key: 41, left: {key: 22, left: {key: 15, left: {key: 13, left: {key: 13, left: null, right: null }, right: null }, right: { key: 33, left: null, right: { key: 37, left: null, right: null } } }, right: { key: 58, left: { key: 50, left: { key: 42, left: null, right: null }, right: { key: 53, left: null, right: null } }, right: { key: 60, left: { key: 59, left: null, right: null }, right: {key: 63, left: null, right: null} } } }Copy the code

Think about how to do the following? This is the precursor.

conclusion

It mainly solves the operation of binary search tree deletion, given any value, how to delete a node, how to deal with the latter node?

The suggestion is to hit the debugger to see, it is easy to understand.