31:T4ac,results = { const results = [ speed(() => [...tr], 'Dancing links generator'), speed(() => [...stack(tr.root)], "Stacked generator"), speed(() => [...traverse(tr.root)], "Tree traversal generator"), speed(() => { const traverseArr = []; traverseCallback(tr.root, v => { traverseArr.push(v); }); return traverseArr; }, "Tree traversal callback"), speed(() => { const stackArr = []; stackCallback(tr.root, v => { stackArr.push(v); }); return stackArr; }, "Stacked callback"), speed(() => { const dancingLinkArr = []; tr.forEach(v => { dancingLinkArr.push(v); }); return dancingLinkArr; }, "Dancing links callback"), speed(() => { const dancingLinkArr = []; dancingLinkCallback(tr.min, v => { dancingLinkArr.push(v); }); return dancingLinkArr; }, "Dancing links callback2"), speed(() => { const arrayStackArr = []; arrayStackCallback(tr.root, v => { arrayStackArr.push(v); }); return arrayStackArr; }, "Stacked Array callback") ].sort((a, b) => a.time - b.time); return results; }32:Td5b,class Tree { constructor(options = {}) { const { update, remove, compare, create } = { update: identity, remove: stubTrue, compare: comparator, create: node, ...options }; this[s.del] = remove.bind(this); this[s.up] = update.bind(this); this[s.create] = create.bind(this); this[s.comparator] = compare.bind(this); this.root = null; this.min = this.max = null; this.length = 0; this.insert = this.insert.bind(this); this[s.insert] = this[s.insert].bind(this); this.remove = this.remove.bind(this); this[s.remove] = this[s.remove].bind(this); this[s.new_left] = this[s.new_left].bind(this); this[s.new_right] = this[s.new_right].bind(this); this.forEach = this.forEach.bind(this); } [s.new_left](parent, value) { const n = this[s.create](value); this.length++; const prev = parent.prev; if (prev) { n.prev = prev; prev.next = n; } else { this.min = n; } parent.prev = n; n.next = parent; return n; } [s.new_right](parent, value) { const n = this[s.create](value); this.length++; const next = parent.next; if (next) { n.next = next; next.prev = n; } else { this.max = n; } parent.next = n; n.prev = parent; return n; } insert(value) { this.root = this[s.insert](value, this.root); } [s.insert](X, T) { if (nil(T)) { const n = this[s.create](X); this.length++; this.min = n; this.max = n; return n; } const compare = this[s.comparator](X, T.value); if (compare < 0) { T.left = nil(T.left) ? this[s.new_left](T, X) : this[s.insert](X, T.left); } else if (compare > 0) { T.right = nil(T.right) ? this[s.new_right](T, X) : this[s.insert](X, T.right); } else { this[s.up](X, T); return T; } T = skew(T); T = split(T); return T; } remove(value) { this.root = this[s.remove](value, this.root); } [s.remove](X, T) { if (nil(T)) return T; const compare = this[s.comparator](X, T.value); if (compare < 0) { T.left = this[s.remove](X, T.left); } else if (compare > 0) { T.right = this[s.remove](X, T.right); } else { // nothing has changed if (!this[s.del](X, T)) return T; if (leaf(T)) { if (T.next) T.next.prev = T.prev; else this.max = T.prev; if (T.prev) T.prev.next = T.next; else this.min = T.next; this.length--; return null; } if (nil(T.left)) { const L = T.next; console.assert(successor(T) === T.next, "big"); T.right = this[s.remove](L.value, T.right); T.value = L.value; } else { const L = T.prev; console.assert(predecessor(T) === T.prev, "smol"); T.left = this[s.remove](L.value, T.left); T.value = L.value; } } T = skew(decrease_level(T)); T.right = skew(T.right); if (!nil(T.right)) T.right.right = skew(T.right.right); T = split(T); T.right = split(T.right); return T; } [Symbol.iterator]() { return dancingLinks(this.min); } forEach(callback) { let tree = this.min; while (true) { if (nil(tree)) return; if (callback(tree.value) === false) return false; // early exit tree = tree.next; } } }33:[] 2f:{"title":"Dancing Linked AA Tree","cells":[{"id":0,"value":"md`# Dancing Linked AA Tree`","pinned":false,"hidden":false,"mode":"ojs"},{"id":492,"value":"viewof options","pinned":false,"hidden":false,"mode":"ojs"},{"id":1032,"value":"viewof values = slider({\n title: \"values\",\n value: 100,\n min: 1,\n max: 1000000,\n precision: -1\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":160,"value":"chart","pinned":false,"hidden":false,"mode":"ojs"},{"id":135,"value":"tr = {\n const tree = new Tree();\n randoms.forEach(tree.insert);\n // tree.remove(15);\n // tree.remove(1);\n // tree.remove(20);\n // tree.remove(3);\n // tree.remove(24);\n // tree.remove(5);\n // tree.remove(11);\n // tree.remove(180);\n // tree.remove(0);\n\n return tree;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":706,"value":"md`> **Note**: I want to add some figures for better explanation, but I don't have the time. _plz send help_.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":131,"value":"md`During my research (I'm a Ph.D Student), I needed an array-like data structure filling two conditions:\n\n1. The length can easily vary.\n2. Be ordered.\n\n**Why ?**\n\nBecause the algorithm I'm implementing is recursive and on each iteration: \n- iterates over the structure **AND**\n- either adds or deletes values from the structure.\n\nSo the naive choice was to use a classic array and apply \\`sort()\\` at the beginning of an iteration. Complexity wise we obtain something like:`","pinned":false,"hidden":false,"mode":"ojs"},{"id":547,"value":"tex`O(n\\log(n))`","pinned":false,"hidden":false,"mode":"ojs"},{"id":546,"value":"md`Assuming \\`append\\` is ${tex`O(1)`}, deletion: ${tex`O(1)`} and \\`sort\\`: ${tex`O(n\\log(n))`}. This is not totally true but hey, even if we use filter or map, we are stuck at ${tex`O(n\\log(n))`}`","pinned":false,"hidden":false,"mode":"ojs"},{"id":573,"value":"md`**Let's talk about trees**\n\nSo the question now is why trees. Mainly because they're not bound by length like an array. The downside is that each mutable operation (add/delete) is ${tex`O(\\log(n))`}.\n\nBut _in AA Tree_(this implementation) like most binary trees iterating over it is equal to something like:`","pinned":false,"hidden":false,"mode":"ojs"},{"id":598,"value":"md`${tex`O(n\\log(\\log(n)))`}^{[ref necessary]}`","pinned":false,"hidden":false,"mode":"ojs"},{"id":615,"value":"md`> The next value in a BST(binary search tree) is either the parent (${tex`O(1)`}) or the smallest value of the right child ${tex`O(\\log(n))`}).`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1090,"value":"md`_I know that you can traverse the tree in ${tex`O(n)`}. But it's ~~not~~ doable using an ~~iterator~~_ using \\`yield*\\`. See Iterators section`","pinned":false,"hidden":false,"mode":"ojs"},{"id":604,"value":"md`This is less than array and sort right !... yeah right 🤔`","pinned":false,"hidden":false,"mode":"ojs"},{"id":627,"value":"md`**Can we do better ?**`","pinned":false,"hidden":false,"mode":"ojs"},{"id":630,"value":"md`In my case, and the case of the majority of us, memory complexity (how much an algorithm uses memory) is not really a problem, as long as it is not _excessive_ (like quadratic or worse).`","pinned":false,"hidden":false,"mode":"ojs"},{"id":641,"value":"md`Before I explain the current implementation let's recap. \n- We need a higly flexible data structure, the final size is not known, we can't just pre-allocate space.\n- We iterate over it in ascending order. We don't do random access.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":652,"value":"md`The fact that we never use random access, one of the main advantage of an array ${tex`O(1)`} vs tree ${tex`O(\\log(n))`} seals the deal for trees.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":660,"value":"md`Iterating over an AATree has this weird complexity. We want something linear without impacting add or delete complexity.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":671,"value":"md`**What do you know about dancing?**`","pinned":false,"hidden":false,"mode":"ojs"},{"id":677,"value":"md`I mean about [dancing **links**](https://en.wikipedia.org/wiki/Dancing_Links) ? It's a simple doubly linked list. Each element knows the \\`next\\` and the \\`previous\\` element.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":688,"value":"md`Imagine now we include this fact inside a tree ! Each node of the tree knows the next (in order) element and the previous one. Great 🎉! We just need to store the first one and follow the links.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":714,"value":"md`**How do we integrate it inside an AATree ?**\n\nNow that we have the idea, implementing it is not _that_ hard. When we add a value, the parent node is **always** either the closest smaller/bigger value.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":728,"value":"md`Let's begin from this tree:`","pinned":false,"hidden":false,"mode":"ojs"},{"id":759,"value":"example1 = \"103\".split(\"\").map(v => +v)","pinned":false,"hidden":false,"mode":"ojs"},{"id":731,"value":"{\n const tree = new Tree();\n example1.forEach(tree.insert);\n\n return createTree(\n d3.hierarchy(convert(tree.root)),\n d => d.data.name,\n 70,\n 10,\n { top: 10, left: 0, right: 0, bottom: 5 }\n );\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":784,"value":"md`The links are linked : \\`0 <=> 1 <=> 3\\`. Now let's add 2`","pinned":false,"hidden":false,"mode":"ojs"},{"id":793,"value":"example2 = \"1032\".split(\"\").map(v => +v)","pinned":false,"hidden":false,"mode":"ojs"},{"id":799,"value":"{\n const tree = new Tree();\n example2.forEach(tree.insert);\n\n return createTree(\n d3.hierarchy(convert(tree.root)),\n d => d.data.name,\n 100,\n 10,\n { top: 10, left: 0, right: 0, bottom: 5 }\n );\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":809,"value":"md`As we can see, it was added under 1. Note: not really true but ignore the tree balancing part, it does not affect the chaining`","pinned":false,"hidden":false,"mode":"ojs"},{"id":818,"value":"md`1 is smaller that 2 ^DUH. but the next value of 1 is 3 (\\`1.next == 3\\`). When we add two:\n- set the next value of 1 as the next value of 2 (\\`2.next = 1.next\\`)\n- set 2 as the next value of 1 (\\`1.next = 2\\`).\n\nWe also do the reverse linking (\\`3.previous = 2\\`) and (\\`2.previous = 1\\`). And that's it. Now we have \\`0 <=> 1 <=> 2 <=> 3\\`\n\nWe still need to track the lowest value and the highest value of the tree. It is quiete easy :\n- When adding an element, if the parent has no previous element it means it's the smallest value. We replace \\`tree.min = parent\\` by \\`tree.min = newnode\\`\n- We do the same but for \\`tree.max\\` : if \\`parent.next == null\\`, then \\`tree.max = newnode\\`.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":852,"value":"md`**What happens when we delete elements ?**`","pinned":false,"hidden":false,"mode":"ojs"},{"id":856,"value":"md`We kind of do the rewind of what we did when we were adding elements. Once we found the node to delete (let's say 2).\nWe set 2's next value (3) as the next value of 2's previous value (1) and 2's previous value (1) as the previous value of 2's next value (3): \n\n~~~python\n2.previous.next = 2.next // where 2.next == 3\n2.next.previous = 2.previous // where 2.previous == 1\n~~~\n\n2 is now not in the chain.\n\nWhen the removed value is either min or max, instead of rechaining the neighbors we just remove it from the chain.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":878,"value":"md`And there you have it. ${tex`O(n)`} on iteration, ${tex`O(\\log(n))`} when adding/deleting elements. And adds ${tex`O(2n)`} memory (where 1 is the size of a pointer).`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1276,"value":"md`## Iterators strategies`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1260,"value":"dancingLinks = function*(tree) {\n while (true) {\n if (nil(tree)) return;\n yield tree.value;\n tree = tree.next;\n }\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":1199,"value":"function* stack(tree) {\n const stack = new Stack();\n\n while (!stack.empty() || !nil(tree)) {\n if (!nil(tree)) {\n stack.add(tree);\n tree = tree.left;\n } else {\n tree = stack.pop();\n yield tree.value;\n tree = tree.right;\n }\n }\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":1061,"value":"function* traverse(tree) {\n if (nil(tree)) return; // do nothing\n\n yield* traverse(tree.left);\n yield tree.value;\n yield* traverse(tree.right);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":1355,"value":"function traverseCallback(tree, callback) {\n if (nil(tree)) return; // do nothing\n\n traverseCallback(tree.left, callback);\n callback(tree.value);\n traverseCallback(tree.right, callback);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":1365,"value":"stackCallback = function(tree, callback) {\n const stack = new Stack();\n while (true) {\n if (nil(tree)) {\n if (stack.empty()) return;\n\n tree = stack.pop();\n callback(tree.value);\n tree = tree.right;\n } else {\n stack.add(tree);\n tree = tree.left;\n }\n }\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":1417,"value":"arrayStackCallback = function(tree, callback) {\n const stack = [];\n while (true) {\n if (nil(tree)) {\n if (stack.length === 0) return;\n\n tree = stack.pop();\n callback(tree.value);\n tree = tree.right;\n } else {\n stack.push(tree);\n tree = tree.left;\n }\n }\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":1382,"value":"dancingLinkCallback = function(tree, callback) {\n while (true) {\n if (nil(tree)) return;\n\n callback(tree.value);\n tree = tree.next;\n }\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":1343,"value":"viewof reroll","pinned":false,"hidden":false,"mode":"ojs"},{"id":1305,"value":"md`Speed:\n\n| Strategy | time |\n|----------|------|\n${results.map(\n ({ type, time }) => `| ${type} | ${time} ms |\n`\n)}`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1313,"value":"$31","pinned":false,"hidden":false,"mode":"ojs"},{"id":889,"value":"md`**Explore the code**`","pinned":false,"hidden":false,"mode":"ojs"},{"id":891,"value":"md`The chaining during insertion is done by \\`Tree.new_left\\` and \\`Tree.new_right\\`\n\n\\`Tree._insert\\` is an adapted version of the initial \\`insert\\`^{[[ref](https://observablehq.com/@stardisblue/aa-tree#operations)]} AATree algorithm\n\nUnchaining is done in \\`Tree._delete\\` which is an adapted version of the AATree \\`delete\\`^{[[ref](https://observablehq.com/@stardisblue/aa-tree#operations)]} algorithm.\n\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1447,"value":"comparator = (a, b) => a - b","pinned":true,"hidden":false,"mode":"ojs"},{"id":1460,"value":"stubTrue = () => true","pinned":true,"hidden":false,"mode":"ojs"},{"id":1468,"value":"identity = T => T","pinned":true,"hidden":false,"mode":"ojs"},{"id":1511,"value":"s = ({\n del: Symbol('delete'),\n up: Symbol('up'),\n create: Symbol('create'),\n comparator: Symbol('comparator'),\n insert: Symbol('insert'),\n remove: Symbol('remove'),\n new_left: Symbol('new_left'),\n new_right: Symbol('new_right')\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":231,"value":"$32","pinned":true,"hidden":false,"mode":"ojs"},{"id":127,"value":"md`## AA Tree Utils`","pinned":false,"hidden":false,"mode":"ojs"},{"id":38,"value":"function split(T) {\n // if (nil(T)) return NIL; if (nil(T.right) || nil(T.right.right)) return T;\n if (nil(T) || nil(T.right) || nil(T.right.right)) return T;\n\n if (T.level === T.right.right.level) {\n const R = T.right;\n T.right = R.left;\n R.left = T;\n R.level += 1;\n return R;\n }\n\n return T;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":8,"value":"function skew(T) {\n // if (nil(T)) return NIL; if (nil(T.left)) return T;\n if (nil(T) || nil(T.left)) return T;\n\n const L = T.left;\n if (L.level === T.level) {\n T.left = L.right;\n L.right = T;\n return L;\n }\n\n return T;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":81,"value":"function decrease_level(T) {\n const r_level = nil(T.right) ? 0 : T.right.level;\n const l_level = nil(T.left) ? 0 : T.left.level;\n const should_be = 1 + Math.min(l_level, r_level);\n if (should_be < T.level) {\n T.level = should_be;\n if (should_be < r_level) {\n T.right.level = should_be;\n }\n }\n return T;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":114,"value":"md`### Accessors`","pinned":false,"hidden":false,"mode":"ojs"},{"id":68,"value":"function successor(T) {\n let next = T.right;\n while (!nil(next.left)) next = next.left;\n return next;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":72,"value":"function predecessor(T) {\n let prev = T.left;\n while (!nil(prev.right)) prev = prev.right;\n return prev;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":99,"value":"md`### Checkers`","pinned":false,"hidden":false,"mode":"ojs"},{"id":62,"value":"function leaf(node) {\n return nil(node.left) && nil(node.right);\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":14,"value":"nil = function(node) {\n return node === null;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":122,"value":"md`## Node`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1496,"value":"node = value => new Node(value)","pinned":true,"hidden":false,"mode":"ojs"},{"id":2,"value":"class Node {\n constructor(value) {\n this.level = 1;\n this.value = value;\n this.left = this.right = null;\n this.prev = this.next = null;\n }\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":148,"value":"md`## View Utils`","pinned":false,"hidden":false,"mode":"ojs"},{"id":498,"value":"style","pinned":false,"hidden":false,"mode":"ojs"},{"id":157,"value":"import { chart, viewof options, viewof reroll, style, randoms } with {\n data,\n values\n} from \"@stardisblue/aa-tree\"","pinned":false,"hidden":false,"mode":"ojs"},{"id":1044,"value":"import { createTree } from \"@stardisblue/vertical-tree\"","pinned":true,"hidden":false,"mode":"ojs"},{"id":1037,"value":"d3 = require('d3@6')","pinned":false,"hidden":false,"mode":"ojs"},{"id":155,"value":"data = convert(\n randoms.length > 10000\n ? {\n value: \"tree view is disabled for +10000 values\",\n left: null,\n right: null\n }\n : tr.root\n)","pinned":true,"hidden":false,"mode":"ojs"},{"id":162,"value":"import { slider, button } from '@jashkenas/inputs'","pinned":false,"hidden":false,"mode":"ojs"},{"id":152,"value":"function convert(node) {\n const children = [];\n if (!nil(node.left)) children.push(convert(node.left));\n if (!nil(node.right)) children.push(convert(node.right));\n\n return {\n name: node.value,\n children\n };\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":1142,"value":"class Stack {\n constructor() {\n this.last = null;\n this.length = 0;\n }\n add(v) {\n const n = { value: v, prev: null };\n\n if (!this.last) {\n this.last = n;\n } else {\n n.prev = this.last;\n this.last = n;\n }\n this.length++;\n }\n\n pop() {\n const n = this.last;\n this.last = n.prev;\n this.length--;\n return n.value;\n }\n empty() {\n return this.last === null;\n }\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":1218,"value":"function speed(callback, title) {\n const t1 = performance.now();\n const result = callback();\n return { type: title, time: performance.now() - t1, result };\n}","pinned":false,"hidden":false,"mode":"ojs"}],"files":"$W33","stdlib":"1","titling":"auto"}