Binary search tree (Recursive)

The binary search tree looked at me for three whole days, and was impressed by human wisdom every day, go!

1. What is binary search tree

Binary Search Tree (BST) : Binary Search Tree (BST) : Binary Search Tree (BST) : Binary Search Tree (BST) : Binary Search Tree

If the left subtree of any node is not empty, the values of all nodes in the left subtree are less than the values of its root node.
If the right subtree of any node is not empty, the values of all nodes in the right subtree are greater than the values of its root node.
The left and right subtrees of any node are binary search trees respectively.
No nodes with equal keys;

advantages

Compared with other data structures, it has the advantage of efficient insert, delete and search operations, with an average time complexity of O(logn).
You can easily answer questions about relationships between data: min, Max, floor, ceil, rank, select

	insert	delete	To find the
Regular array	O(n)	O(n)	O(n)
Sequential array	O(n)	O(n)	O(logn)
Binary search tree	O(logn)	O(logn)	O(logn)

Ordinary array insert O(n) : Here is the implementation of no duplicate elements of the data structure, so the ordinary array insert needs to find whether the element already exists, if there is an update, insert.

limitations

No random access
The binary search tree isUnbalanced treeIf the tree distribution is extremely unbalanced, the time performance will be greatly affected. The same data can correspond to different binary search trees. If the number of nodes and tree depth are the same (similar to linked list), all operations will degenerate to O(n).

It can be improved to balanced binary search tree, such as red black tree. It is not discussed in this paper

2. JavaScript implements BST

The following is to build a binary search tree (similar to a dictionary) with no duplicate elements, which can find the value by looking up the key

👇 Below is the main structure

// Construct the node
class Node {
	constructor(key, value) {
		this.key = key
		this.value = value
		this.left = null
		this.right = null}}// Construct binary search tree
class BST {
	constructor(root = null) {
		this.root = root
		this.count = 0
	}
  // The main method
  insert(key){} / / insert
  search(key){} / / to find
  preOrder(){} // preorder traversal
  inOrder(){}  // middle order traversal
  postOrder(){} // after the sequence traversal
  levelOrder(){} // width first traversal (sequence)
  searchMin(){} // Find minimum
  searchMax(){} // Find maximum
	deleteMin(){} // Delete minimum
  deleteMax(){} // Delete maximum
  delete(key){} / / delete
}
Copy the code

2.1 insert

// Insert a node (key, value) into the binary search tree.
// return the root node

// Recursive implementation
insert(key, value) {
  return this.root = this._insert(this.root, key, value)
}
_insert(node, key, value) {
  if (node === null) {
    return node = new Node(key, value)
  }
  if (key === node.key) {
    node.value = value
  } else if (key < node.key) {
    node.left = this._insert(node.left, key, value)
  } else {
    node.right = this._insert(node.right, key, value)
  }
  return node
	}
}
Copy the code

2.2 find

// Search the root of the binary search tree for nodes that contain keys.
// Returns node if contains, null if not
search(key) {
  let node = this.root
  while(node ! = =null) {
    if (key === node.key) {
      return node
    } else if (key > node.key) {
      node = node.right
    } else {
      node = node.left
    }
  }
  return null
}
Copy the code

2.3 traversal

Binary search tree traversal is divided into two categories, depth-first traversal and breadth-first traversal.

Depth-first traversal can be divided into three types: sequential traversal, middle-sequential traversal and post-sequential traversal. (Divided by root position) Sequential traversal: left-right middle-order traversal: left-right back-order traversal: left-right root

// first traversal (recursion)
preOrder(node = this.root, arr = []) {
  if(node ! = =null) {
    arr.push(node.key)
    this.preOrder(node.left, arr)
    this.preOrder(node.right, arr)
  }
  return arr
}

// Middle order traversal (recursive)
inOrder(node = this.root, arr = []) {
  if(node ! = =null) {
    this.inOrder(node.left, arr)
    arr.push(node.key)
    this.inOrder(node.right, arr)
  }
  return arr
}

// after the sequence traversal (recursive)
postOrder(node = this.root, arr = []) {
  if(node ! = =null) {
    this.postOrder(node.left, arr)
    this.postOrder(node.right, arr)
    arr.push(node.key)
  }
  return arr
}

// breadth-first traversal (hierarchy)
levelOrder() { 
  const stack = []
  const arr = []
  stack.push(this.root)
  while (stack.length > 0) {
    let node = stack.shift() // First in, first out
    arr.push(node.key)
    node.left && stack.push(node.left)
    node.right && stack.push(node.right)
  }
  return arr
}
Copy the code

2.4 delete

Find the node to delete (1) Return NULL if the node does not exist (2) Continue if the node does exist
judge

(1) If a node has no children, then only the link pointing from the parent node to it needs to be null

(2) When the node has only the left subtree, the parent node points to the child node of the node

(2) When the node has only the right subtree, the parent node points to the child node of the node

(3) [Key point] When a node contains left and right subtrees, the node is replaced with the largest node in the left subtree or the smallest node in the right subtree (Hubbard deletion, 1962).

delete(key) {
  return this.root = this._deleteNode(this.root, key)
}
_deleteNode(node, key) {
  if (node === null) {
    return null
  }
  if (key > node.key) {
    node.right = this._deleteNode(node.right, key)
    return node
  } else if (key < node.key) {
    node.left = this._deleteNode(node.left, key)
    return node
  } else { // key === node.key
    if (node.left === null) {
      return node.right
    } else if (node.right === null) {
      return node.left
    } else {
      // The left and right nodes are not empty
      let rightMinNode = this.searchMin(node.right)
      let successor = new Node(rightMinNode.key, rightMinNode.value)
      successor.left = node.left
      successor.right = this.deleteMin(node.right)
      return successor
    }
  }
}

SearchMin (), deleteMin() (both recursive)
searchMin(node = this.root) {
  if (node.left === null) {
    return node
  }
  node = node.left
  return this.searchMin(node)
}

deleteMin(){
  // Delete the smallest node whose root node is node
  // Returns the deleted root node
  if(this.root === null) {return null
  }
  return this.root = this._deleteMin(this.root)
}
_deleteMin(node){
  if(node.left === null) {
    return node.right
  } 
  node.left = this._deleteMin(node.left)
  return node
}
Copy the code

More and more

In addition to adding, deleting, or changing data, binary search trees can also answer sequential questions between data. (Specific implementation omitted)

Minimum, maximum,
Succeeded, predecessor
Floor, ceil
Rank (58), select (10)

3. BST of different designs

4. Reference

Mooc Liu Yubo [algorithm and data structure] : big love bo teacher ❤️ rookie tutorial – data structure: the specific implementation process diagram, nice!