30:T1c43,// // Class representing a 2-3 tree // class Node23 { constructor (parent=null) { [this.parent,this.links,this.keys] = [parent,[],[]] } // Return number of keys keyCount () { return this.keys.length } // Returns true iff node is leaf isLeaf () { return this.links.length == 0 } // Returns true iff node is root isRoot () { return this.parent == null } // Returns the index i where key == keys[i] or // where key should be inserted locateKey (key) { let i = 0; while (i < this.keys.length && this.keys[i] < key) i++; return i; } // Finds the node where key is or the leaf node where it should be inserted find (key) { if (this.isLeaf()) return this; let i = this.locateKey(key); if (i < this.keyCount() && this.keys[i] == key) return this; let son = this.links[i]; if (son.parent != this) { // Debug! console.log(son, " parent link is not ", this); } return son.find(key) } // Splits this node split() { if (this.isRoot()) { // Split root node let [bNode,dKey,fNode] = [new Node23(this),this.keys[1],new Node23(this)]; [bNode.keys,fNode.keys] = [this.keys.slice(0,1),this.keys.slice(2,3)]; if (!this.isLeaf()) { let [A,C,E,G] = this.links; [bNode.links, fNode.links] = [[A,C],[E,G]]; for (let child of bNode.links) child.parent = bNode; for (let child of fNode.links) child.parent = fNode; } this.keys = [dKey]; this.links = [bNode,fNode] } else { // Split non-root node let [bNode,dKey,fNode] = [this,this.keys[1],new Node23(this.parent)]; [bNode.keys,fNode.keys] = [bNode.keys.slice(0,1),bNode.keys.slice(2,3)]; if (!this.isLeaf()) { let [A,C,E,G] = this.links; [bNode.links, fNode.links] = [[A,C],[E,G]]; for (let child of bNode.links) child.parent = bNode; for (let child of fNode.links) child.parent = fNode; } this.parent.insert (dKey,fNode) } } // Inserts a new key into this node. insert (key,rightLink = null) { let i = this.locateKey(key); if (i < this.keyCount() && this.keys[i] == key) throw key+": key already in tree"; if (this.isLeaf() || rightLink) { this.keys = this.keys.slice (0,i).concat([key]).concat(this.keys.slice(i)); if (rightLink) { // inserting in a non-leaf node this.links = this.links.slice (0,i+1) .concat([rightLink]) .concat(this.links.slice(i+1)) } if (this.keyCount() > 2) this.split() } else { this.links[i].insert(key,rightLink) } } // Returns a copy of the tree rooted at this node clone() { let copy = new Node23(); copy.keys = this.keys.slice(0); if (!this.isLeaf()) { copy.links = this.links.map (l => { let c = l.clone(); c.parent = copy; return c }); } return copy; } // Returns the smallest key to the right of key i in the current node. // Assumes this node is internal. rightReplacement (i) { let p = this.links[i+1]; while (!p.isLeaf()) p = p.links[0]; return p.keys[0] } // Returns the next sibling node to the right of this one if it exists. Otherwise returns null rightSibling() { if (this.isRoot()) return null; let i = this.parent.links.indexOf (this); if (i < 0 || i == this.parent.links.length-1) return null; return this.parent.links[i+1] } // Returns the next sibling node to the left this one if it exists. Otherwise returns null leftSibling() { if (this.isRoot()) return null; let i = this.parent.links.indexOf (this); if (i < 0 || i == 0) return null; return this.parent.links[i-1] } // Tries to fix an empty node by adopting from the left or right sibling // Returns true iff adoption is successful adopt () { let sibling = this.leftSibling(); if (sibling && sibling.keyCount() > 1) { let i = this.parent.links.indexOf (this); let lkey = sibling.keys.pop(); this.keys.push (this.parent.keys[i-1]); this.parent.keys[i-1] = lkey; if (!this.isLeaf()) { let llink = sibling.links.pop(); this.links.unshift (llink) llink.parent = this } return true } sibling = this.rightSibling(); if (sibling && sibling.keyCount() > 1) { let i = this.parent.links.indexOf (this); let rkey = sibling.keys.shift(); this.keys.push (this.parent.keys[i]); this.parent.keys[i] = rkey; if (!this.isLeaf()) { let rlink = sibling.links.shift(); this.links.push(rlink) rlink.parent = this } return true; } return false } // Deletes the ikey'th key of this node and its two neighboring links, replacing // them with the given link. Returns the key value that was removed delKey (ikey, link) { let key = this.keys.splice(ikey,1); this.links.splice (ikey,2,link) return key[0] } // Tries to merge with sibling from left or from right // Returns true if successful merge() { let sibling = this.leftSibling() if (sibling) { // Merge with sibling to the left console.assert (sibling.keys.length == 1); // Sibling must be a 2-node let i = this.parent.links.indexOf(this); // Index of the link that points to this node let pkey = this.parent.delKey(i-1,sibling) sibling.keys.push (pkey) if (!this.isLeaf()) { sibling.links.push (this.links[0]) this.links[0].parent = sibling } return true } sibling = this.rightSibling(); if (sibling) { // Merge with sibling to the right console.assert (sibling.keys.length == 1); // Sibling must be a 2-node let i = this.parent.links.indexOf(this); // Index of the link that points to this node let pkey = this.parent.delKey(i,sibling) sibling.keys.unshift(pkey) if (!this.isLeaf()) { sibling.links.unshift(this.links[0]) this.links[0].parent = sibling } return true } return false } // Called whenever a node has 0 keys underflow() { if (this.isRoot()) { if (!this.isLeaf()) { let son = this.links[0]; this.keys = son.keys this.links = son.links; for (let grandson of son.links) { grandson.parent = this } } } else { if (!this.adopt()) { if (this.merge()) { if (this.parent.keys.length == 0) { this.parent.underflow() } } else throw "Neither merge or adopt worked!" } } } // Deletes the key from the tree delete (key) { let i = this.locateKey(key); if (i >= this.keyCount() || this.keys[i] != key) { if (this.isLeaf()) throw key+": key not in tree"; else this.links[i].delete(key) } else { // found key if (!this.isLeaf()) { let r = this.rightReplacement(i); this.keys[i] = r; this.links[i+1].delete(r) } else { this.keys.splice(i,1); if (this.keys.length == 0) { // underflow this.underflow() } } } } } 31:[] 2e:{"title":"2-3-Trees","cells":[{"id":0,"value":"md`# 2-3-Trees\n\nJavaScript implementations of 2-3 trees as mentioned in Lecture 6 of [Prof. 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":5,"value":"$30","pinned":true,"hidden":false,"mode":"ojs"},{"id":11,"value":"{\n let div = html`

`;\n let t = new Node23();\n div.append(dot`${graphViz(t)}`);\n for (let key of [10, 8, 7, 11, 6, 2, 12, 14, 15]) {\n div.append(htl.html`
After inserting ${key}
`);\n t.insert(key);\n div.append(dot`${graphViz(t)}`);\n }\n return div;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":103,"value":"{\n let div = html`

`;\n let t = new Node23();\n for (let key of [1, 4, 6, 7, 10, 9, 11, 8, 2, 3, 5]) t.insert(key);\n div.append(dot`${graphViz(t)}`);\n for (let key of [1, 4, 6, 7, 10, 9, 11, 8, 2, 3, 5]) {\n t.delete(key);\n div.append(html`
After deleting ${key}
`);\n div.append(dot`${graphViz(t)}`);\n }\n return div;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":147,"value":"md`## Drawing code`","pinned":false,"hidden":false,"mode":"ojs"},{"id":20,"value":"function graphViz (node) {\n let count = 0;\n let nodeMap = new Map();\n let result = \"\";\n let getNodeId = (node) => {\n if (nodeMap.has(node)) return nodeMap.get(node);\n let nodeId = \"node\"+(++count);\n let label = node.keyCount() ? node.keys.join(\" | \") : \"-\" ;\n result += `${nodeId} [label=\"${label}\"];\\n`;\n nodeMap.set (node,nodeId);\n return nodeId\n }\n let traverse = (node) => {\n let nodeId = getNodeId (node);\n for (let child of node.links) {\n let childId = getNodeId(child);\n result += `${nodeId} -> ${childId};\\n`;\n traverse(child);\n }\n }\n traverse(node)\n return `digraph { node [shape=record style=rounded]\\n${result} }`;\n}\n ","pinned":true,"hidden":false,"mode":"ojs"},{"id":18,"value":"dot = require(\"@observablehq/graphviz\")","pinned":true,"hidden":false,"mode":"ojs"}],"files":"$W31","stdlib":"1","titling":"auto"}