30:T10b4,// // Nil is an empty AA tree. A new tree can be created by calling nil.insert() // nil = { var nil; class AANode { constructor (key, level, left, right) { [this.key, this.left, this.right, this.level] = [key,left,right,level] } // Basic BST find algorithm. // Returns the node with the sought key or null if not found find (key) { if (this == nil) return null; if (this.key == key) return this; if (this.key < key) return this.right.find(key); return this.left.find(key) } // Returns a copy of this tree clone () { if (this == nil) return nil; return new AANode (this.key, this.level, this.left.clone(), this.right.clone()) } // Rotates if red node to the left of a black node // Returns the new root of this subtree skew () { if (this.left.level == this.level) { let q = this.left; this.left = q.right; q.right = this; return q; } else return this; } // Rearranges a black node with two red nodes in cascade to the right. // Returns the new root of this subtree split () { // Note: must not split the nil node if (this != nil && this.right.right.level == this.level) { let q = this.right; this.right = q.left; q.left = this; q.level += 1; return q; } else return this } // Inserts key into the tree rooted at this node. // Returns the inserted node insert (key) { let p = this; if (p == nil) p = new AANode(key, 1, nil, nil); else if (key < p.key) p.left = p.left.insert(key); else if (key > p.key) p.right = p.right.insert(key); else throw "Duplicate Key: "+key; return p.skew().split(); } // Makes sure the level of this node respects the AA level invariant, // i.e., that is, 1 plus the level of its black children updateLevel() { let idealLevel = 1 + Math.min(this.left.level, this.right.level); if (this.level > idealLevel) { this.level = idealLevel; if (this.right.level > idealLevel) this.right.level = idealLevel; } } // Fixes up the tree after a node is deleted making sure it still // obeys the AA tree invariant by performing appropriate skews and splits. // Returns the updated node fixupAfterDelete() { this.updateLevel(); let p = this.skew(); p.right = p.right.skew(); p.right.right = p.right.right.skew(); p = p.split(); p.right = p.right.split(); return p } // Returns the descendant node containing the immediately smaller key leftReplacement () { let p = this.left; while (p.right != nil) p = p.right; return p; } // Returns the descendant node containing the immediately bigger key rightReplacement () { let p = this.right; while (p.left != nil) p = p.left; return p; } // Returns this node after deleting key from the tree rooted at it delete (key) { if (this == nil) throw "not found: "+key; if (key < this.key) this.left = this.left.delete(key); else if (key > this.key) this.right = this.right.delete(key); else { if (this.left == nil && this.right == nil) // leaf node? return nil; // just unlink the node else if (this.left == nil) { // no left child? let r = this.rightReplacement(); // get replacement from right this.key = r.key; // copy replacement contents here this.right = this.right.delete(r.key);// delete replacement } else { // no right child? let r = this.leftReplacement(); // get replacement from left this.key = r.key; // copy replacement contents here this.left = this.left.delete(r.key); // delete replacement } } return this.fixupAfterDelete(); // fix structure after deletion } } nil = new AANode ('nil',0); nil.left = nil.right = nil; return nil }31:T468,function graphViz (node) { let count = 0; let nodeMap = new Map(); let result = ""; let getNodeId = (node, isred) => { if (nodeMap.has(node)) return nodeMap.get(node); let nodeId = "node"+(++count); let style = isred ? "color=red style=filled fillcolor=pink" : ""; let label = node.key//+`(${node.level})`; if (node == nil) { result += `${nodeId} [label="" shape=point width=0 style=invis];` return nodeId; } result += `${nodeId} [${style} label="${label}"];\n`; nodeMap.set (node,nodeId); return nodeId } let traverse = (node) => { if (node == nil) return; let nodeId = getNodeId (node); if (node.left == nil && node.right == nil) return; for (let child of [node.left, nil, node.right]) { let childId = getNodeId(child, child.level == node.level); let style = (child == nil) ? "[style=invis]" : ""; result += `${nodeId} -> ${childId} ${style};\n`; traverse(child); } } traverse(node) return `digraph {graph [ordering="out"]; node [shape=circle fixedsize=true width=0.5]; ${result}\n }`; }32:[] 2e:{"title":"AA Trees","cells":[{"id":0,"value":"md`# AA Trees\n\nJavaScript implementations of AA 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":8,"value":"$30","pinned":true,"hidden":false,"mode":"ojs"},{"id":110,"value":"md`** Helper function to create an AA tree by repeated insertions of keys **`","pinned":false,"hidden":false,"mode":"ojs"},{"id":14,"value":"function AA (...keys) {\n let t = nil;\n for (let k of keys) t = t.insert(k)\n return t\n}\n ","pinned":true,"hidden":false,"mode":"ojs"},{"id":131,"value":"md`## Insertion demo`","pinned":false,"hidden":false,"mode":"ojs"},{"id":134,"value":"{\n let div = html`

`;\n let aa = nil\n for (let key of [11,5,6,1,10,2,4,3,7,9,8]) {\n aa = aa.insert(key);\n div.append(html`

${key} inserted${dot`${graphViz(aa)}`}

`);\n }\n return div\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":127,"value":"md`## Deletion demo`","pinned":false,"hidden":false,"mode":"ojs"},{"id":65,"value":"{\n let div = html`

`;\n let aa = AA (5,6,1,10,11,2,4,3,7,9,8);\n for (let key of [2,3,4,5,6]) {\n aa = aa.delete(key);\n div.append(html`

${key} deleted${dot`${graphViz(aa)}`}

`);\n }\n return div\n}\n","pinned":true,"hidden":false,"mode":"ojs"},{"id":107,"value":"md`## Drawing code`","pinned":true,"hidden":false,"mode":"ojs"},{"id":28,"value":"$31","pinned":false,"hidden":false,"mode":"ojs"},{"id":26,"value":"dot = require(\"@observablehq/graphviz\")","pinned":true,"hidden":false,"mode":"ojs"}],"files":"$W32","stdlib":"1","titling":"auto"}