25:["$","title",null,{"children":"SkipList with order statistics (incomplete) | Bárbara Cerqueira | Observable"}] 49:T6d4,# SkipList with order statistics (incomplete) Skip lists are a probabilistic data structure designed to support the basic operations of _searching_, _insertion_ and _deletion_ with asymptotic time complexity of a general balanced tree implementation, while being more efficient in terms of memory [1]. Other miscellaneous operations (such as _merging_) happen asymptotically faster in skip lists than in its tree counterparts. For a brief insight in the internal structure of this object, this list is built in many levels, as depicted below.

When searching for a list node to interact with, it's not necessary to walk through each item. Instead, the algorithm walks in leaps. This is done by setting random heights for each node in such a way that is less likely that the nodes get very tall (the procedure is shown in the code). Then, we begin at the topmost level, going ahead until a node whose key is greater than ours is found. At this moment, either we found the desired node or we must continue our raid in the level below. Once we've reached the lowest level without any success, the search fails. Adding **order statistics** to the Skip list requires adding a new field to the nodes. In this implementation, we add a field called **`extra`**. The `extra` field for a node _N_ contains the total number of nodes between _N_ and the tallest node that points to _N_. In the example above, the `extra` fields of the various nodes would be given by the following table: | key | extra | |-----|---| | 3 | 0 | | 6 | 1 | | 7 | 0 | | 9 | 1 | | 12 | 0 | | 17 | 1| | 19 | 0 | | 21 | 0 | | 25 | 6 | | 26 | 0 | | NIL | 8 | 4a:T453,md` Finally, the \`SkipList\` itself. - \`Search(key)\`
Searching starts at the topmost level in the list. At every step, a pointer goes forward until a node with key greater than or equal to \`key\` is found. It returns the \`value\` stored in the target node. If the \`key\` is absent, returns \`undefined\`, as expected for JS objects. - \`Insert(key, value)\`
Insertion is preceded by searching for the appropriate place to insert a new node. If the \`key\` is already there, we simply exchange the \`value\` attribute of that node. If we've got a fresh \`key\` to insert, we create a new node and relink the previous and next nodes to fit the new one. Keeping track of these links is done with the aid of the \`update\` vector. - \`Delete(key)\`
Deletion follows pretty much like insertion does. When the key is found, relinking is carried between the node's neighbours. If the search fails, an error is thrown. - \`Order(key)\`
Searches \`key\` in the list and returns the number of elements smaller than \`key\` in the list. Note that \`key\` may not be in the list. `4b:T13d4,class SkipList { constructor(max_level = 6, p = 0.5) { this.level = 1; this.maxLevel = max_level; this.p = p; // Growth probability this.NIL = new Node(Infinity, null, max_level, 0, null); this.header = new Node(-Infinity, null, max_level, 0, this.NIL); // Node(key, val, level, extra) } Insert(key, val) { /* Insertion */ let update = newArray(this.maxLevel, this.NIL); let update_extra = newArray(this.maxLevel, 0); // Stores 'extra' per level during Search let x = this.header; // Search for (let i = this.level - 1; i >= 0; i--) { while (x.forward[i].key < key) { x = x.forward[i]; update_extra[i] += x.extra + 1; } update[i] = x; } x = x.forward[0]; let extra = 0; if (x.key == key) { x.val = val; } else { let new_level = this.randomLevel(); if (new_level >= this.level) { for (let i = this.level; i <= new_level+1; i++) { update[i] = this.header; update_extra[i] = 0; } this.level = new_level + 1; } // Finding 'extra' of new node -> Adds values of 'extra per level' for every level smaller than new node's height for (let i = 0; i < new_level-1; i++) { extra += update_extra[i]; } // Create node to insert x = new Node(key, val, new_level, extra, this.NIL); /* Stores nodes that have already had their 'extra' field adjusted. Since the only nodes that will need adjustment are the ones positioned behind the new node, but which don't have taller/equal nodes between itself and the new node, the total number of nodes needing adjustment is at most 'this.level', one per level. The nodes will be added to the position equivalent to their height (starting at 0) */ let adjusted = newArray(this.level, null); // Updating pointers and 'extra' fields level by level for (let i = this.level - 1; i >= 0; i--) { if (!adjusted.includes(update[i].forward[i])) { // Ensures 'extra' is not adjusted more than once if (update[i].forward[i].level > x.level) { // Nodes taller than new node update[i].forward[i].extra += 1; adjusted[i] = update[i].forward[i]; }else{ // Nodes shorter than new node for (let j = 0; j < update[i].forward[i].level-1; j++){ update[i].forward[i].extra -= update_extra[j]; } adjusted[i] = update[i].forward[i]; } } if (i < new_level){ x.forward[i] = update[i].forward[i]; update[i].forward[i] = x; } } } } /* Search ** The search is done by going forward on the topmost level possible. */ Search(key) { let x = this.header; for (let i = this.level - 1; i >= 0; i--) { while (x.forward[i].key < key) { x = x.forward[i]; } } x = x.forward[0]; if (x.key == key) { return x.val; } else { return undefined; } } Delete(key) { /* Deletion */ let update = newArray(this.maxLevel, this.NIL); let update_extra = newArray(this.maxLevel, 0); // Stores 'extra' per level during Search let x = this.header; // Search for (let i = this.level - 1; i >= 0; i--) { while (x.forward[i].key < key) { x = x.forward[i]; update_extra[i] += x.extra + 1; } update[i] = x; } x = x.forward[0]; if (x.key === key) { let adjusted = newArray(this.level, null); // Fixing pointers and 'extra' fields for (let i = this.level - 1; i >= 0; i--) { if (update[i].forward[i] === x) { update[i].forward[i] = x.forward[i]; } if (!adjusted.includes(update[i].forward[i])) { if (update[i].forward[i].level > x.level) { update[i].forward[i].extra -= 1; adjusted[i] = update[i].forward[i]; }else{ for (let j = 0; j < update[i].forward[i].level-1; j++){ update[i].forward[i].extra += update_extra[j]; } adjusted[i] = update[i].forward[i]; } } } while ( this.level > 1 && this.header.forward[this.level - 2] === this.NIL ) { this.level--; } } else { throw `Key Error: key '${key}' not found.`; } } Order(key) { let total = 0; let x = this.header; for (let i = this.level - 1; i >= 0; i--) { while (x.forward[i].key < key) { x = x.forward[i]; total += x.extra + 1; } } return total; } toString() { let s = "header"; let x = this.header; while (x.forward[0] != this.NIL) { x = x.forward[0]; s = s + ` -> [${x.key}|${x.val}]`; } return s + " -> NIL"; } randomLevel() { let level = 1; while (Math.random() < this.p && level < this.maxLevel - 1) { // biased coin toss level++; } return level; } }4c:T653,graphViz = function (sl) { let header = { key: "H", forward: [...sl.header.forward], extra: sl.header.extra }; let top = sl.level; let keys = []; for (let i = 0; i < top; i++) keys[i] = header.key; header.forward.length = top; let node; let next = function () { node = header.forward[0]; header.key = node.key; if (node == sl.NIL || !node.forward) return; for (let i = 0; i < node.forward.length; i++) { if (node.forward[i] == null) throw "ERROR"; header.forward[i] = node.forward[i]; keys[i] = node.key; } }; let result = ""; let emitNode = function (node) { let box = [ node.key == "H" ? "-∞" : node.key == Infinity ? "∞" : node.key ]; let n = top; if (node.forward) n = node.forward.length; box.push(`x:${node.extra}`); for (let i = 0; i < n; i++) box.push(`<${i}>`); result += `struct${node.key}[ label = "${box.join("|")}" ];\n`; }; let emitLinks = function (node) { let n = top; if (node.forward) n = node.forward.length; for (let i = 0; i < n; i++) { result += `struct${keys[i]}:<${i}>->struct${node.key}:<${i}>;\n`; } }; node = header; for (;;) { emitNode(node); if (node == sl.NIL || !node.forward) break; next(); } header = { key: "H", forward: [...sl.header.forward] }; for (let i = 0; i < top; i++) keys[i] = header.key; for (;;) { emitLinks(header.forward[0]); next(); if (node == sl.NIL || !node.forward) break; } return `digraph{ rankdir=LR; node [ shape=record margin=0 width=0.3 fontsize=12 ]; ${result}}`; }4d:[{"id":"3ad09c579d8fe31c055a04d6236a54aac101f6d5bdabcedb27e41062b74ddc2dde0375972ba241742b3d89c7b1e86eb5a284d716a2aeb40c1857986e55530ee5","href":"https://static.observableusercontent.com/files/3ad09c579d8fe31c055a04d6236a54aac101f6d5bdabcedb27e41062b74ddc2dde0375972ba241742b3d89c7b1e86eb5a284d716a2aeb40c1857986e55530ee5","name":"image.png","type":"image/png","lastModified":1685056697709.049,"size":14891}] 29:{"id":"c3c0d82584064082","slug":null,"title":"SkipList with order statistics (incomplete)","thumbnail":"f627e0a84f4d2821854edbacfbe25880f403184c3be5320ef2510d49f0082733","access_level":"public","create_time":"$D2023-05-25T23:18:17.709Z","update_time":"$D2023-05-30T04:53:14.620Z","view_time":null,"first_public_time":"$D2023-05-25T23:18:17.709Z","has_unpublished_edits":null,"fork":{"id":"d49dfc5cb52d6298","slug":"skiplist-with-order-statistics-incomplete","title":"SkipList with order statistics (incomplete)","owner":{"id":"e9fcee55f21948e0","login":"esperanc","name":"Claudio Esperança"}},"stars":0,"starred":false,"owner":{"type":"team","id":"79f01554c6271d00","login":"ufrj2023","name":"Bárbara Cerqueira","avatar_url":"https://avatars-next.observableusercontent.com/32729dcadc15cd8d6b4094c9eea3c41d5d2d85a7f76417ee226258c5f3957b10","tier":"starter_2024","bio":"","followed_by_you":false,"follows_you":false},"version":737,"publish_version":null,"role":null,"authored":false,"authors":[{"type":"individual","id":"51632a79d6986a1e","login":"1barbararodrigues","name":"Bárbara Cerqueira","avatar_url":"https://avatars-next.observableusercontent.com/ddc9ee30c8e58d5b14b0faa15c943ee986392a93c1fc8cb7af60babb7d731ed7","tier":null,"bio":"","followed_by_you":false,"follows_you":false}],"members":[{"type":"individual","id":"51632a79d6986a1e","login":"1barbararodrigues","name":"Bárbara Cerqueira","avatar_url":"https://avatars-next.observableusercontent.com/ddc9ee30c8e58d5b14b0faa15c943ee986392a93c1fc8cb7af60babb7d731ed7","tier":null,"role":"editor"},{"type":"team","id":"79f01554c6271d00","login":"ufrj2023","name":"Bárbara Cerqueira","avatar_url":"https://avatars-next.observableusercontent.com/32729dcadc15cd8d6b4094c9eea3c41d5d2d85a7f76417ee226258c5f3957b10","tier":"starter_2024","role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":0,"collection":null,"type":"notebook","body":{"titling":"auto","title":"SkipList with order statistics (incomplete)","cells":[{"id":0,"value":"$49","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":398,"value":"md`### Details\nBefore diving into the code, let's see an overview on some of the elements that appear below.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":303,"value":"md`The function \\`newArray(size, value=null)\\` initializes an Array filled with \\`size\\` copies of \\`value\\`. Equivalent to the Python statement
\\`>>> L = [value] * size\\`.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":161,"value":"function newArray(size, value=null) {\n return new Array(size).fill(value)\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":335,"value":"Each `Node` contains a `key`, a `val` and a `forward` attribute. The `key` is what indexes each `Node` and is exactly what the `Insert`, `Search` and `Delete` operations will run against. `val` contains the value stored in each `Node` and may be any kind of object. \n\nThe `forward` field contains links to the next element in the list for the various \"skip\" levels. The constructor of `Node` creates this with `level` entries, all pointing to a `NIL` object, which signals the end of each chain of links.\n\nIn this version, an additional **`extra`** field is used to encode the total number of elements between the previous node of the same `level` and this one. ","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":319,"value":"md`The \\`NIL\\` object is present at the end of each level in the SkipList. Its \\`key\\`, represented here by \\`Infinity\\`, is higher than any other found in the list. Its \\`val\\` and \\`forward\\` attributes aren't necessary, but intend to resemble \\`Node\\` behaviour.\n\nIn this version, each Skiplist has its own \\`NIL\\` object at the end, since it is also contains an **\\`extra\\`** field used to implement order statistics.\n \n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":5,"value":"class Node {\n constructor(key, val, level, extra, NIL) {\n this.key = key;\n this.val = val;\n this.extra = extra;\n this.level = level;\n this.forward = NIL ? newArray(level, NIL) : null; // null array\n }\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":346,"value":"$4a","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":141,"value":"$4b","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":436,"value":"md`## Examples`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":522,"value":"viewof refresh = html``","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":452,"value":"viewof sl = {\n refresh;\n let div = htl.html`

`;\n let L = new SkipList();\n div.append(dot`${graphViz(L)}`, htl.html`

INSERTION`);\n let keys = d3.shuffle(d3.range(1, 100)).slice(0, 8);\n for (let key of keys) {\n div.append(htl.html`
Inserting ${key}
`);\n L.Insert(key, null);\n div.append(dot`${graphViz(L)}`);\n }\n div.append(htl.html`

ORDER STATISTICS
`);\n for (let key of d3.shuffle(d3.range(1, 100)).slice(0, 8)) {\n div.append(htl.html`
${L.Order(key)} keys smaller than ${key}.`);\n }\n div.append(htl.html`

DELETION
`);\n d3.shuffle(keys);\n for (let key of keys) {\n div.append(htl.html`
Deleting ${key}
`);\n L.Delete(key);\n div.append(dot`${graphViz(L)}`);\n }\n div.value = L;\n return div;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":148,"value":"md`## Bibliography\n1. William Pugh, _A Skip List Cookbook_, University of Maryland, 1990.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":514,"value":"md`## Drawing code`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":454,"value":"$4c","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":443,"value":"dot = require(\"@observablehq/graphviz\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W4d","stdlib":"1"}} 24:null

INSERTION`);\n let keys = d3.shuffle(d3.range(1, 100)).slice(0, 8);\n for (let key of keys) {\n div.append(htl.html`Inserting ${key}`);\n L.Insert(key, null);\n div.append(dot`${graphViz(L)}`);\n }\n div.append(htl.html`

ORDER STATISTICS`);\n for (let key of d3.shuffle(d3.range(1, 100)).slice(0, 8)) {\n div.append(htl.html`${L.Order(key)} keys smaller than ${key}.`);\n }\n div.append(htl.html`

INSERTION`);\n let keys = d3.shuffle(d3.range(1, 100)).slice(0, 8);\n for (let key of keys) {\n div.append(htl.html`
Inserting ${key}
`);\n L.Insert(key, null);\n div.append(dot`${graphViz(L)}`);\n }\n div.append(htl.html`

ORDER STATISTICS
`);\n for (let key of d3.shuffle(d3.range(1, 100)).slice(0, 8)) {\n div.append(htl.html`
${L.Order(key)} keys smaller than ${key}.`);\n }\n div.append(htl.html`