[Algorithm] Delete a node from Binary Search Tree
Node from Tree search Binary delete ALGORITHM
2023-09-14 08:59:14 时间
The solution for the problem can be divided into three cases:
case 1: if the delete node is leaf node, then we can simply remove it
case 2: if the delete node is has single side or substree
case 3: it has two children, then to keep it as a valid binary search tree, we can copy the min value from right subtree to delete node, to convert the problem into case 2
function Node(val) { return { val, left: null, right: null }; } function Tree() { return { root: null, addLeft(val, root) { const node = Node(val); root.left = node; return root.left; }, addRight(val, root) { const node = Node(val); root.right = node; return root.right; } }; } const tree = new Tree(); const root = Node(12); tree.root = root; const n1 = tree.addLeft(5, root); const n2 = tree.addRight(15, root); const n3 = tree.addLeft(3, n1); const n4 = tree.addRight(7, n1); tree.addLeft(1, n3); tree.addRight(9, n4); const n5 = tree.addLeft(13, n2); tree.addRight(14, n5); const n6 = tree.addRight(17, n2); const n7 = tree.addRight(20, n6); tree.addLeft(18, n7); /** * 12 / \ 5 15 / \ / \ 3 7 13 17 / \ \ \ 1 9 14 20 / 18 Delete 15 First copy 17 to 15 12 / \ 5 17 / \ / \ 3 7 13 17 / \ \ \ 1 9 14 20 / 18 Then remove original 17 12 / \ 5 17 / \ / \ 3 7 13 20 / \ \ / 1 9 14 18 */ function deleteNode(root, val) { // base case, if leaf node, return if (root === null) { return root; } else if (val > root.val) { // if delete value is larger than root, search on right side of tree root.right = deleteNode(root.right, val); } else if (val < root.val) { // if delete value is smaller than root, search on left side of tree root.left = deleteNode(root.left, val); } else { // if found the delete value and it is leaf node if (root.left === null && root.right === null) { // set leaf node to null root = null; } // if found the delete node and its right side has children // set root to null and link to its right node else if (root.left === null && root.right !== null) { let temp = root.right; root = null; root = temp; } // if found the delete node and its left side and children // set root to null and link to its left node else if (root.left !== null && root.right === null) { let temp = root.left; root = null; root = temp; } // the found node has children on both sides // then pick the min value from rgiht side (or max value from left side) // copy to current node // reset it right side (or left side) else { const temp = root.right; // get the min on the right side or max on the left side root.val = temp.val; root.right = deleteNode(root.right, temp.val); } return root; } } deleteNode(tree.root, 15); console.log(JSON.stringify(tree.root.left, null, 2));
相关文章
- 9 —— node —— 读取文件及文件夹的名字
- Remove Nth Node From End of List
- 9.Node.js 包管理器npm
- [Custom CLI] Develop and Publish a Node.js CLI from Scratch
- [Node.js] Take Screenshots of Multiple Dimensions for Responsive Sites using Nightmare
- [Node.js] node-persist: localStorage on the server
- [Node.js] Level 3 new. Steam
- node require 运行步骤
- node-canvas遇到NODE_MODULE_VERSION不一致的问题
- [Custom CLI] Develop and Publish a Node.js CLI from Scratch
- [Unit Testing] Mock a Node module's dependencies using Proxyquire
- [WASM] Run WebAssembly in Node.js using the node-loader
- [Node.js]23. Level 4: Semantic versioning
- 【GO】 K8s 管理系统项目5[API部分--Node]
- SAP WebClient UI component context node class单元测试方法
- how is value displayed in BSP UI from model node data binding
- 日志库 winston 的学习笔记 - 创建一个使用 winston 的 Node.js 应用
- node-schedule.js实现crontab定时任务
- Node.js stream模块(二)可写流