TypeScript data structures and algorithms: binary search trees

The previous article “TypeScript Data Structures and Algorithms: Hash Tables” implemented the data structures and algorithms in TypeScript hash tables. This article continues with the implementation of binary search trees.

Binary Search Tree (Binary Search Tree), can be to understand the word is divided into three parts: Binary Search | | Tree. First, it is a tree. Second, each node has at most two child nodes. Third, the left child node < this node < the right child node is arranged in order to facilitate search. The overall structure is shown in the figure below:

The following is the method that will be implemented in a binary search tree.

• insert(key): Inserts a new node into the tree.
• search(key): Finds a key in the tree. There is returnedtrue; Return false if not present.
• inOrderTraverse(): Traverses all nodes in middle order.
• preOrderTraverse(): Traverses all nodes in sequence first.
• postOrderTraverse(): Traverses all nodes in sequence.
• min(): Returns the node with the smallest key in the tree.
• max(): Returns the node with the largest key in the tree.
• remove(key): Removes a node from the tree.

The data structure

The Node Node

Using data structures means that each node has three parts: left, key, and right.

As shown in the figure above, key is the key of the local node. Left points to the left child node smaller than key, and right points to the right child node larger than key. Write a separate data structure Node for each Node:

export class Node<K> {
  left: Node<K>;
  right: Node<K>;

  constructor(public key: K) {}

  toString() {
    return `The ${this.key}`; }}Copy the code

Helper method

Since binary search trees are ordered trees, there needs to be a way to compare sizes:

// Enumeration values for comparing results
export enum Compare {
  LESS_THAN = -1,
  BIGGER_THAN = 1,
  EQUALS = 0,}// specify the type of custom Compare
export type ICompareFunction<T> = (a: T, b: T) = > number;

/ * * *@description: Default size comparison function *@param {T} a
 * @param {T} b
 * @return {Compare} Returns -1, 0, 1, which is less than or equal to greater than */
export function defaultCompare<T> (a: T, b: T) :Compare {
  if (a === b) {
    return Compare.EQUALS;
  }
  return a < b ? Compare.LESS_THAN : Compare.BIGGER_THAN;
}
Copy the code

BinarySearchTree class

Next, create the skeleton of the BinarySearchTree class, using root to represent the root node.

import { Compare, defaultCompare, ICompareFunction } from '.. /util';
import { Node } from './models/node';

export default class BinarySearchTree<T> {
  protected root: Node<T>;

  constructor(protected compareFn: ICompareFunction<T> = defaultCompare){}}Copy the code

Specific methods are divided into three categories: getRoot, min and Max non-recursive methods, inOrderTraverse, preOrderTraverse and postOrderTraverse recursive ordered traversal methods. And search, insert and remove three recursive tree operation methods.

Non-recursive methods

The implementation of the three non-recursive methods is very simple and can be explained using a graph:

The root node can be returned directly to root, while the extremum is searched iteratively left and right respectively. The extremum is found until the parent node of undefined is found.

/ * * *@description: Returns the root node */
getRoot(): Node<T> {
  return this.root;
}

/ * * *@description: returns the smallest element in the tree */
min(): Node<T> {
  // Call the iteration method
  return this.minNode(this.root);
}

/ * * *@description: returns the smallest element */ under the specified subtree
protected minNode(node: Node<T>): Node<T> {
  let current = node;
  // Keep looking left
  while(current ! =null&& current.left ! =null) {
    current = current.left;
  }
  return current;
}

/ * * *@description: Returns the largest element in the tree */
max(): Node<T> {
  // Call the iteration method
  return this.maxNode(this.root);
}

/ * * *@description: returns the largest element */ under the specified subtree
protected maxNode(node: Node<T>): Node<T> {
  let current = node;
  // Keep checking to the right
  while(current ! =null&& current.right ! =null) {
    current = current.right;
  }
  return current;
}

Copy the code

Orderly traversal

The purpose of the three ordered traversals is to walk through the tree one by one in a specific way, visiting each node and executing the callback function. In a binary tree, there are only two directions of recursion (left and right), and the difference between middle and then sequential traversal is that the steps of looking at the key and executing the callback function are placed opposite each other in the middle of the two recursive steps.

The first sequence traversal

The order of the first traversal is to execute the callback -> left -> right, so the order of access is parent first, suitable for printing structured documents:

/ * * *@description: Sequential traversal */
preOrderTraverse(callback: Function) {
  // Call the sequential traversal iteration method
  this.preOrderTraverseNode(this.root, callback);
}

private preOrderTraverseNode(node: Node<T>, callback: Function) {
  // Baseline conditions
  if(node ! =null) {
    // The sequential traversal is executed in the order of callbacks -> left -> right
    callback(node.key);
    this.preOrderTraverseNode(node.left, callback);
    this.preOrderTraverseNode(node.right, callback); }}Copy the code

In the sequence traversal

The middle order traversal order is left -> execute the callback -> right, so it follows the order from smallest to largest, can be used to print the sorted result:

/ * * *@description: middle order traversal */
inOrderTraverse(callback: Function) {
  // Call the sequential traversal iteration method
  this.inOrderTraverseNode(this.root, callback);
}

private inOrderTraverseNode(node: Node<T>, callback: Function) {
  // Baseline conditions
  if(node ! =null) {
    // The middle order traversal is left -> execute the callback -> right
    this.inOrderTraverseNode(node.left, callback);
    callback(node.key);
    this.inOrderTraverseNode(node.right, callback); }}Copy the code

After the sequence traversal

The order of back-order traversal is left -> right -> execute the callback, so the access order is child first, which can be applied to calculate the size of a directory and all files in its subdirectories.

/ * * *@description: sequential traversal */
postOrderTraverse(callback: Function) {
  // Call the sequential iteration method
  this.postOrderTraverseNode(this.root, callback);
}

private postOrderTraverseNode(node: Node<T>, callback: Function) {
  // Baseline conditions
  if(node ! =null) {
    // Backorder traversal is executed left -> right -> execute callback
    this.postOrderTraverseNode(node.left, callback);
    this.postOrderTraverseNode(node.right, callback); callback(node.key); }}Copy the code

Recursive tree operations

Search, insert and remove, the three conventional methods of adding and deleting, all require recursion of the tree.

check

If key is smaller than node.key, search to the left and vice versa until a value or null is found:

/ * * *@description: Search for the element */
search(key: T): boolean {
  // Call recursive methods
  return this.searchNode(this.root, key);
}

/ * * *@description: recursive search */
private searchNode(node: Node<T>, key: T): boolean {
  // Baseline condition: return false at end
  if (node == null) {
    return false;
  }

  if (this.compareFn(key, node.key) === Compare.LESS_THAN) {
    // key is smaller than node.key
    return this.searchNode(node.left, key);
  } else if (this.compareFn(key, node.key) === Compare.BIGGER_THAN) {
    // key is larger than node.key
    return this.searchNode(node.right, key);
  } else {
    // Baseline condition: neither large nor small, indicating that the element is found, return true
    return true; }}Copy the code

increase

If the tree is empty, the tree is inserted to the root node. When the tree is not empty, it must be inserted into an appropriate position of the leaf node, so the appropriate insertion position can be determined recursively by the size:

/ * * *@description: Inserts the element */
insert(key: T) {
  if (this.root == null) {
    // Boundary case: insert to root node
    this.root = new Node(key);
  } else {
    // find the insertion position recursively
    this.insertNode(this.root, key); }}/ * * *@descriptionRecursive insertion method */
protected insertNode(node: Node<T>, key: T) {
  if (this.compareFn(key, node.key) === Compare.LESS_THAN) {
    // If key is smaller than node.key, look left
    if (node.left == null) {
      // Baseline condition: the left side is empty and the value is directly assigned
      node.left = new Node(key);
    } else {
      // If not, continue to recurse
      this.insertNode(node.left, key); }}else {
    // Key is larger than node.key
    if (node.right == null) {
      // Baseline condition: the right side is empty and the value is directly assigned
      node.right = new Node(key);
    } else {
      // If not, continue to recurse
      this.insertNode(node.right, key); }}}Copy the code

delete

Deleting a node comes last because deleting a node is the most complex. Because binary search trees are ordered, inserts are inserted in the right place, not in the middle of the tree. However, during deletion, any node in the tree (including nodes in the middle of the tree) can be deleted, so that the structure of the tree must be reconstructed. It can be divided into the following three situations:

1. deleteA leaf node

Removing the leaf node is the simplest operation, because the removal of the leaf node does not involve tree restructuring:

2. deleteThere is only one child nodeThe nodes of the

After deleting a node that has only one left or right child, the subtree is isolated and needs to be reintegrated into the tree. However, the situation is not complicated, just need to entrain the child node subtree to replace the deleted node:

3. deleteThere are two child nodesThe nodes of the

The situation becomes more complicated if the deleted node has two children. It is necessary to find the smallest node in the right subtree of the deleted node first, then replace the position of the deleted node, and then re-point to the right subtree to establish the structure:

The code is as follows:

/ * * *@description: Removes the specified element */
remove(key: T) {
  // Call the recursion method, which is special enough to return the deleted tree
  this.root = this.removeNode(this.root, key);
}

/ * * *@description: a recursive method that removes a specified element from a specified subtree and returns the processed node to the node */ each time
protected removeNode(node: Node<T>, key: T): Node<T> {
  // Baseline conditions
  if (node == null) {
    return null;
  }

  if (this.compareFn(key, node.key) === Compare.LESS_THAN) {
    // When key is smaller than Node. key, go left
    node.left = this.removeNode(node.left, key);
    return node;
  } else if (this.compareFn(key, node.key) === Compare.BIGGER_THAN) {
    // When the key is greater than node.key, go to the right
    node.right = this.removeNode(node.right, key);
    return node;
  } else {
    // The node to be deleted has been found
    if (node.left == null && node.right == null) {
      // When the node to be deleted is a leaf node
      node = null;
      return node;
    } else if (node.left == null) {
      // When the node to be deleted has only one child node
      node = node.right;
      return node;
    } else if (node.right == null) {
      // The deleted node has only one child node
      node = node.left;
      return node;
    } else {
      // When the node to be deleted has two children
      const aux = this.minNode(node.right);
      node.key = aux.key;
      node.right = this.removeNode(node.right, aux.key);
      returnnode; }}}Copy the code

The next article will examine AVL trees.

---

Front-end notepad, not regularly updated, welcome to pay attention to!

• Wechat official account: Lin Jingyi’s notepad
• Blog: Lin Jingyi’s notebook
• Nuggets column: Lin Jingyi’s notebook
• Zhihu column: Lin Jingyi’s notebook
• Github: MageeLin

---