31:T6b9,class BinarySearchTree extends BinaryTree { constructor (...args) { super(...args); } // Finds a subtree whose root node has the given key. // If not found, returns the tree where one such node would be inserted. find (key) { if (!this.node) return this; if (this.node.entry.key == key) return this; if (this.node.entry.key < key) return this.node.right.find(key); return this.node.left.find(key) } // Inserts the given entry. Raises an error on duplicate keys. insert (entry) { let t = this.find (entry.key); if (t.node) throw `This key already in tree: ${entry.key}`; t.node = new BinaryTreeNode (entry, new BinarySearchTree(), new BinarySearchTree()) return t } // Returns the lefmost leaf node of this tree, which must // be non-empty leftmost () { if (!this.node) throw "Tree has no nodes"; if (!this.node.left.node) return this; return this.node.left.leftmost(); } // Deletes the entry in the root of this tree delete() { if (!this.node) throw "Tree has no nodes"; if (!this.node.left.node) { this.node = this.node.right.node } else if (!this.node.right.node) { this.node = this.node.left.node } else { let l = this.node.right.leftmost(); this.node.entry = l.node.entry; l.delete() } } // Returns a shallow copy of this tree clone() { if (!this.node) return new BinarySearchTree(); return new BinarySearchTree (new BinaryTreeNode (this.node.entry, this.node.left.clone(), this.node.right.clone())) } }32:[] 2f:{"title":"Binary Search Trees","cells":[{"id":0,"value":"md`# Binary Search Trees\n\nJavaScript implementations of binary search trees as mentioned in Lecture 4 of [David Mount's course on Data Structures (CMSC420)](https://www.cs.umd.edu/class/fall2019/cmsc420-0201/lectures.html)\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":10,"value":"md`

\n## A generic Binary Tree`","pinned":false,"hidden":false,"mode":"ojs"},{"id":344,"value":"md`** Class modeling a binary tree object.**
\nIt can be a link to a null tree or point to a root node`","pinned":false,"hidden":false,"mode":"ojs"},{"id":12,"value":"class BinaryTree {\n constructor(node = null) {\n this.node = node;\n }\n *preorder() {\n if (this.node) {\n yield this;\n yield* this.node.left.preorder();\n yield* this.node.right.preorder();\n }\n }\n *inorder() {\n if (this.node) {\n yield* this.node.left.inorder();\n yield this;\n yield* this.node.right.inorder();\n }\n }\n *postorder() {\n if (this.node) {\n yield* this.node.left.postorder();\n yield* this.node.right.postorder();\n yield this;\n }\n }\n toString() {\n if (this.node) return this.node.toString();\n return \"-\";\n }\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":375,"value":"md`** Class modeling a binary tree _node_ object.**`","pinned":false,"hidden":false,"mode":"ojs"},{"id":378,"value":"class BinaryTreeNode {\n constructor (entry,left,right) {\n [this.entry,this.left,this.right] = [entry,left,right]\n }\n toString() {\n if (this.entry instanceof String) return this.entry;\n return this.entry.toString()\n }\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":380,"value":"md`** Helper function to create a binary tree.**
\nIf called with no arguments, creates a null tree, otherwise creates\na tree with a root node constructed from the args.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":384,"value":"function BT (...args) {\n if (args.length == 0) return new BinaryTree ()\n return new BinaryTree(new BinaryTreeNode(...args))\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":386,"value":"md`** A sample \\`BinaryTree\\` **`","pinned":false,"hidden":false,"mode":"ojs"},{"id":389,"value":"bt = BT(\"A\",BT(\"B\",BT(),BT()),BT(\"C\",BT(),BT()))","pinned":true,"hidden":false,"mode":"ojs"},{"id":401,"value":"draw(bt)","pinned":true,"hidden":false,"mode":"ojs"},{"id":194,"value":"md`** Arrays with inorder, preorder and postorder traversals of the tree **`","pinned":false,"hidden":false,"mode":"ojs"},{"id":199,"value":"[...bt.inorder()].map(tree => tree.node.entry)","pinned":true,"hidden":false,"mode":"ojs"},{"id":202,"value":"[...bt.preorder()].map(tree => tree.node.entry)","pinned":true,"hidden":false,"mode":"ojs"},{"id":204,"value":"[...bt.postorder()].map(tree => tree.node.entry)","pinned":true,"hidden":false,"mode":"ojs"},{"id":433,"value":"md`

\n## Binary Search Tree`","pinned":false,"hidden":false,"mode":"ojs"},{"id":434,"value":"md`** Class modeling a node entry**
\nAn entry is composed of a \\`key\\`, which is used in searches, and a \\`value\\`, a generic data item associated with that key.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":439,"value":"class Entry {\n constructor (key,value = null) {\n [this.key,this.value] = [key,value]\n }\n toString () {\n if (this.value) return `${this.key} (${this.value})`\n return `${this.key}`\n }\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":443,"value":"md`** Class modeling a Binary Search Tree **
\nAssumes that each key is unique (no duplicates).`","pinned":false,"hidden":false,"mode":"ojs"},{"id":442,"value":"$31","pinned":true,"hidden":false,"mode":"ojs"},{"id":454,"value":"md`** Helper function to create a BST from an array **`","pinned":false,"hidden":false,"mode":"ojs"},{"id":453,"value":"function BST(entries) {\n let t = new BinarySearchTree();\n for (let [k,v] of entries) t.insert(new Entry(k,v))\n return t\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":459,"value":"md`** A sample BST **`","pinned":false,"hidden":false,"mode":"ojs"},{"id":462,"value":"t = BST([[9,\"A\"],[7,\"B\"],[8,\"C\"],[1,\"D\"],[4,\"E\"],[5,\"F\"],[11,\"X\"]])","pinned":true,"hidden":false,"mode":"ojs"},{"id":465,"value":"draw(t)","pinned":true,"hidden":false,"mode":"ojs"},{"id":497,"value":"md`** Inorder traversal of \\`t\\`**`","pinned":false,"hidden":false,"mode":"ojs"},{"id":476,"value":"[...t.inorder()].map(tree => tree.node.entry.toString())","pinned":true,"hidden":false,"mode":"ojs"},{"id":500,"value":"md`** A clone of \\`t\\` with key 7 deleted **`","pinned":false,"hidden":false,"mode":"ojs"},{"id":479,"value":"q = {\n let q = t.clone();\n q.find(7).delete();\n return q;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":481,"value":"draw(q)","pinned":true,"hidden":false,"mode":"ojs"},{"id":206,"value":"md`

\n## GraphViz drawing code`","pinned":false,"hidden":false,"mode":"ojs"},{"id":107,"value":"graphViz = (tree) => {\n if (tree instanceof BinaryTree) {\n let result = `digraph{`;\n let count = 0;\n let traverse = (root) => {\n if (root.node) {\n if (root.node.left.node) {\n result += `< ${root.node.toString()} > -> < ${root.node.left.node.toString()} >;\\n`;\n traverse(root.node.left)\n }\n else {\n result += 'null'+(++count)+'[shape = none, label=\"\"];\\n';\n result += `< ${root.node.toString()} > -> ${'null'+count} [arrowhead=\"tee\"];\\n`;\n }\n if (root.node.right.node) {\n result += `< ${root.node.toString()} > -> < ${root.node.right.node.toString()} >;\\n`;\n traverse(root.node.right);\n }\n else {\n result += 'null'+(++count)+'[shape = none, label=\"\"];\\n';\n result += `< ${root.node.toString()} > -> ${'null'+count} [arrowhead=\"tee\"];\\n`;\n }\n }\n }\n traverse (tree)\n return result + \"}\"\n }\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":113,"value":"draw = (tree) => dot`${graphViz(tree)}`","pinned":false,"hidden":false,"mode":"ojs"},{"id":8,"value":"dot = require(\"@observablehq/graphviz@0.2\")","pinned":true,"hidden":false,"mode":"ojs"}],"files":"$W32","stdlib":"1","titling":"auto"}