Binary search tree is the most common type of binary tree, also called binary search tree. As the name suggests, binary lookup trees are designed for fast lookup. However, it can not only quickly find a data, but also quickly insert and delete a data. How does it do this? These all depend on the special structure of binary search trees. A binary search tree requires that at any node in the tree, the value of each node in the left subtree is less than the value of this node, and the value of each node in the right subtree is greater than the value of this node.
Code:
class Node { constructor(num = 0){ this.value = num; this.left = null; this.right = null; } } class SearchTree{ constructor(){ this.root = null; } print(){ let point = this.root; if (point){ printAll(this.root.left); console.log(this.root.value); printAll(this.root.right); } function printAll(p){ if (p === null){ return; } printAll(p.left); console.log(p.value); printAll(p.right); } } insert(num){ let node = new Node(num); let p = this.getPrev(num); if (! p){ this.root = node; } else if(num < p.value){ p.left = node; } else { p.right = node; } } getPrev(num, find = false) { let point = this.root; let res = []; while (true) { if (point && point.left && num < point.value) { point = point.left; continue } if (point && point.right && num >= point.value) { if (find && num === point.value) { res.push(point.value); } point = point.right; Continue} if (find) {if (point.value === num) {res.push(point.value); } if (res.length === 0) { return null } if (res.length === 1) { return res[0]; } return res; } return point; } } find(num) { if (this.root === null) { return } return this.getPrev(num, true); } remove(num) { let point = this.root; let prent = null; let tree = this; let res = null; while (true) { if (point.left) { if (num < point.left.value || num < point.value) { prent = point; point = point.left; continue } } if (point.right) { if (num >= point.right.value || num >= point.value) { if (num === point.value) { delMethod(point, prent); if (prent === null) { point = this.root; } else { prent = prent; point = prent.right; } res = true; continue } prent = point; point = point.right; continue } } if (point.value === num) { res = true; delMethod(point, prent); } break; } return res; function delMethod(delNode, parent) { let p = delNode; // let pp = parent; // the node to be deleted has two children if (p.eft! = null && p.right ! = null) {// let minP = p. light; let minPP = p; While (minP. Left! = null) { minPP = minP; minP = minP.left; } p.value = minP.value; P = minP; Pp = minPP; } // Delete node is leaf node or has only one child node let child; // the child node of p if (p.left! = null) child = p.left; else if (p.right ! = null) child = p.right; else child = null; if (pp == null) { tree.root = child } else if (pp.left == p) { pp.left = child; } else { pp.right = child; }}}}Copy the code