29:null 2a:["$","title",null,{"children":"Search-oriented Tree Data Structures | Jo Wood | Observable"}] 2f:T11d0,

BinarySearchTree

A mutable binary search tree storing unique, comparable values. Maintains the invariant that all values in the left subtree are strictly less than the node, and all values in the right subtree are strictly greater. Provides efficient insertion, search, and removal, though performance depends on how balanced the tree is.

`constructor(rootValue?: any)`

Creates a new BinarySearchTree. If a rootValue is provided, it is inserted as the root of the tree.

`root: BinaryTreeNode | null`

The root node of the tree, or null if the tree is empty.

`insert(x: any): BinarySearchTree`

Inserts x into the binary search tree. If the tree is empty, x becomes the root. Values less than the current node go to the left; greater values go to the right. Duplicate values are ignored. Returns this tree to support method chaining.

`find(x: any): BinaryTreeNode | null`

Node containing x if it exists in the tree, or null if not found.

`remove(x: any): BinarySearchTree`

Removes x from the binary search tree if it exists. Returns this tree to support method chaining.

`clear(): BinarySearchTree`

Clears the tree. Returns this tree to support method chaining.

`*[Symbol.iterator](): Iterable<any>`

Returns an iterator over all items in the tree in depth-first in-order. This provides a conventient way of iterating over all items. For example,
for (const x of tree)
or
[...tree].

`*nodesPreOrder(): Iterable<BinaryTreeNode>`

Generator that yields tree nodes in depth-first pre-order (VLR), starting from the root.

`*dfsPreOrder(): Iterable<any>`

Generator that yields node values in depth-first pre-order (VLR), starting from the root.

`*dfsInOrder(): Iterable<any>`

Generator that yields node values in depth-first in-order (LVR), starting from the root. This yields the node values in ascending order according to the comparison used by the tree.

`*dfsPostOrder(): Iterable<any>`

Generator that yields node values in depth-first post-order (LRV), starting from the root.

`*bfs(): Iterable<any>`

Generator that yields node values in breadth-first order, starting from the root.

`toArray(traversal?: "in"|"pre"|"post"|"bfs"): Array<any>`

Array of the values in the tree using the specified traversal order, defaulting to breadth-first.
Throws: Error if an unsupported traversal type is given.

`toDot(options?: object): Element`

Generates a GraphViz dot visualization for the tree. Accepts the following options:

rankDir: Direction of layout (e.g. "TB", "LR"; default: "TB")
scale: Scale factor, useful for shrinking large tree displays (default: 1)
compact: Determines whether compact or spaced layout (default: true)
fillClr: Function mapping a node to its fill colour (default: (node) => "white")
labelClr: Function mapping a node to its text colour (default: (node) => "black")

30:T1161,

AVLTree

A self-balancing binary search tree that maintains logarithmic height through rotations. The AVL invariant ensures that the height difference between the left and right subtrees of any node is at most 1. Search, insertion and removal have ${tex`O(\log n)`} worst-case time complexity. Traversing all values takes ${tex`O(n)`}time.

`constructor(rootValue?: any)`

Creates a new AVLTree. If rootValue is provided, it is inserted as the root node.

`root: AVLTreeNode | null`

The root node of the tree, or null if the tree is empty.

`insert(x: any): AVLTree`

Inserts x into the AVL tree and rebalances the tree if necessary. Duplicate values are ignored.
Returns the tree to support method chaining.

`find(x: any): AVLTreeNode | null`

The node containing x if it exists in the tree, or null if not found.

`remove(x: any): AVLTree`

Removes x from the AVL tree and rebalances the tree to maintain height balance.
Returns the tree to support method chaining.

`clear(): AVLTree`

Clears the tree. Returns this tree to support method chaining.

`*[Symbol.iterator](): Iterable<any>`

Returns an iterator over all items in the tree in depth-first in-order. This provides a conventient way of iterating over all items. For example,
for (const x of tree)
or
[...tree].

`*nodesPreOrder(): Iterable<AVLTreeNode>`

Generator that yields tree nodes in depth-first pre-order (VLR), starting from the root.

`*dfsPreOrder(): Iterable<any>`

Generator that yields node values in depth-first pre-order (VLR), starting from the root.

`*dfsInOrder(): Iterable<any>`

Generator that yields node values in depth-first in-order (LVR), starting from the root. This yields the node values in ascending order according to the comparison used by the tree.

`*dfsPostOrder(): Iterable<any>`

Generator that yields node values in depth-first post-order (LRV), starting from the root.

`*bfs(): Iterable<any>`

Generator that yields node values in breadth-first order, starting from the root.

`toArray(traversal?: "in"|"pre"|"post"|"bfs"): Array<any>`

Array of the values in the tree using the specified traversal order, defaulting to breadth-first.
Throws: Error if an unsupported traversal type is given.

`toDot(options?: object): Element`

Generates a GraphViz dot visualization for the tree. Accepts the following options:

rankDir: Direction of layout (e.g. "TB", "LR"; default: "TB")
scale: Scale factor, useful for shrinking large tree displays (default: 1)
compact: Determines whether compact or spaced layout (default: true)
fillClr: Function mapping a node to its fill colour (default: (node) => "white")
labelClr: Function mapping a node to its text colour (default: (node) => "black")

31:T1204,

RedBlackTree

A self-balancing binary search tree using the left-leaning red-black invariants. The tree maintains its structure through rotations and colour flips. Search, insertion and removal take ${tex`O(\log n)`} time in the worst case, while complete traversals take ${tex`O(n)`}. Each node is a RedBlackTreeNode; the tree, rather than the node itself, maintains the structural invariants. The tree’s height is at most ${tex`2\log_2(n+1)`}.

`constructor(rootValue?: any)`

Creates a new RedBlackTree. If rootValue is provided, it is inserted as the root node.

`root: RedBlackTreeNode | null`

The root node of the tree, or null if the tree is empty.

`insert(x: any): RedBlackTree`

Inserts x into the red-black tree and rebalances as needed using rotations and colour flips. Duplicate values are ignored. Returns the tree to support method chaining.

`find(x: any): RedBlackTreeNode | null`

The node containing x if it exists in the tree, or null if not found.

`remove(x: any): RedBlackTree`

Removes x from the red-black tree and rebalances as needed. The root is always recoloured to black. Returns the tree to support method chaining.

`clear(): RedBlackTree`

Clears the tree. Returns this tree to support method chaining.

`*[Symbol.iterator](): Iterable<any>`

Returns an iterator over all items in the tree in depth-first in-order. This provides a conventient way of iterating over all items. For example,
for (const x of tree)
or
[...tree].

`*nodesPreOrder(): Iterable<RedBlackTreeNode>`

Generator that yields tree nodes in depth-first pre-order (VLR), starting from the root.

`*dfsPreOrder(): Iterable<any>`

Generator that yields node values in depth-first pre-order (VLR), starting from the root.

`*dfsInOrder(): Iterable<any>`

Generator that yields node values in depth-first in-order (LVR), starting from the root. This yields the node values in ascending order according to the comparison used by the tree.

`*dfsPostOrder(): Iterable<any>`

Generator that yields node values in depth-first post-order (LRV), starting from the root.

`*bfs(): Iterable<any>`

Generator that yields node values in breadth-first order, starting from the root.

`toArray(traversal?: "in"|"pre"|"post"|"bfs"): Array<any>`

Array of the values in the tree using the specified traversal order, defaulting to breadth-first.
Throws: Error if an unsupported traversal type is given.

`toDot(options?: object): Element`

Generates a GraphViz dot visualization for the tree. Accepts the following options:

rankDir: Direction of layout (e.g. "TB", "LR"; default: "TB")
scale: Scale factor, useful for shrinking large tree displays (default: 1)
compact: Determines whether compact or spaced layout (default: true)
fillClr: Function to set the node fill colour (default: (node) => "white")
labelClr: Function to set the node label text colour (default: (node) => "black")

32:[] 2d:{"id":"eaea325974f14571","slug":"data-structures-search-tree","title":"Search-oriented Tree Data Structures","thumbnail":"4fb33a148d854d2220d7f0290c0ce2d616facf1ec652fbf39b7aad6fc5fb241d","access_level":"public","create_time":"$D2025-08-10T06:18:46.612Z","update_time":"$D2026-09-22T11:11:33.836Z","view_time":null,"first_public_time":"$D2026-09-22T14:23:51.315Z","has_unpublished_edits":null,"fork":{"id":"5bf5df2d35e53b34","slug":"data-structures-tree","title":"General Tree Data Structures","owner":{"id":"9461f58b209074d5","login":"jwolondon","name":"Jo Wood"}},"stars":1,"starred":false,"owner":{"type":"team","id":"9461f58b209074d5","login":"jwolondon","name":"Jo Wood","avatar_url":"https://avatars-next.observableusercontent.com/27f72cecd1ac20853a533421fab228ce5f611cbc0986c1e420f7d3b1eb49ef50","tier":"starter_2024"},"version":509,"publish_version":509,"role":null,"authored":false,"authors":[{"type":"individual","id":"e2432cc13dc447d3","login":"jwolondon","name":"Jo Wood","avatar_url":"https://avatars-next.observableusercontent.com/27f72cecd1ac20853a533421fab228ce5f611cbc0986c1e420f7d3b1eb49ef50","tier":null}],"members":[{"type":"team","id":"9461f58b209074d5","login":"jwolondon","name":"Jo Wood","avatar_url":"https://avatars-next.observableusercontent.com/27f72cecd1ac20853a533421fab228ce5f611cbc0986c1e420f7d3b1eb49ef50","tier":"starter_2024","role":"editor"},{"type":"individual","id":"e2432cc13dc447d3","login":"jwolondon","name":"Jo Wood","avatar_url":"https://avatars-next.observableusercontent.com/27f72cecd1ac20853a533421fab228ce5f611cbc0986c1e420f7d3b1eb49ef50","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":true,"trashed":false,"lapsed":null,"subscribed":null,"forks":1,"collection":{"id":"cf3a41cde0560514","slug":"data-structures","title":"data structures","owner":{"id":"9461f58b209074d5","login":"jwolondon","name":"Jo Wood"}},"type":"notebook","body":{"title":"Search-oriented Tree Data Structures","cells":[{"id":0,"value":"# Search-oriented Tree Data Structures","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":411,"value":"These structures impose an ordering on their values so that a search can follow one path through the tree rather than examine every node. Their search, insertion and removal operations take ${tex`O(h)`} time, where${tex`h`} is the tree's height. For a suitably balanced tree this is ${tex`O(\\log n)`}, but an unbalanced binary search tree can have ${tex`h = n`}. Therefore, using trees that balance themselves, such as AVL and red-black trees can guarantee logarithmic height.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":31,"value":"## 1. Binary Search Trees\n\nOne of the more common specialised variants of binary trees is the [binary search tree](https://en.wikipedia.org/wiki/Binary_search_tree) (BST). It stores unique, orderable values and maintains the property that every value in a node’s left subtree is smaller than the node’s value, while every value in its right subtree is larger. Maintaining this property allows efficient retrieval of values from the tree with a time complexity of ${tex`O(h)`} where ${tex`h`} is the height of the tree.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":165,"value":"In the examples that follow, consider the storage of the following randomly ordered list of numbers:","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":167,"value":"const xs = [\n 19, 5, 17, 14, 1, 10, 13, 12, 3, 11, 15, 20, 8, 6, 18, 9, 16, 7, 4, 2\n];","pinned":true,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":163,"value":"The simplest implementation is the non-balancing BST.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":29,"value":"import {BinarySearchTree} from \"observable:@jwolondon/adts-and-data-structures\";","pinned":true,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":173,"value":"const bst = xs.reduce((bst, x) => bst.insert(x), new BinarySearchTree())\n\ndisplay(bst.toDot({ scale: 0.7 }))","pinned":true,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":184,"value":"Finding a value involves comparing it with the root. If it does not match, the search follows the left child when the sought value is smaller and the right child when it is larger. This process continues until either a matching node is found or the required child link is null indicating that the value is absent.\n\nWhile inserting and removing values from the tree is relatively efficient, it suffers from the problem of being unbalanced (more nodes down one branch than the other) if values are inserted with any kind of order. The worst case of inserting values entirely in order leads to a linear sequence, offering no advantage over a linear data structure.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":186,"value":"const linearBst = [1, 2, 3, 4, 5].reduce(\n (bst, x) => bst.insert(x),\n new BinarySearchTree()\n);\n\ndisplay(linearBst.toDot({scale: 0.7}));","pinned":true,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":193,"value":"A non-balancing BST can be appropriate when implementation simplicity and low constant overhead are important, provided the insertion order is unlikely to produce a highly unbalanced tree. Unlike AVL and red-black trees, it provides no worst-case logarithmic guarantee.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":40,"value":"$2f","pinned":false,"hidden":false,"mode":"html","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":42,"value":"## 2. AVL Tree","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":284,"value":"An [AVL Tree](https://en.wikipedia.org/wiki/AVL_tree), named after Adelson-Velsky and Landis, is a self-balancing binary search tree. For every node, the heights of its left and right subtrees differ by at most 1. This guarantees ${tex`O(\\log n)`} worst-case search, insertion and removal. Maintaining the invariant requires height updates and, when necessary, rotations after insertions and removals. AVL trees are therefore often well suited to lookup-heavy workloads.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":290,"value":"Like the unbalanced BST, AVL trees store unique orderable values and have the property that a parent node's value will always be greater than its left child's value and less than its right child's value. Here's the same sequence of randomly ordered numbers from 1-20 as above, represented in an AVL tree:","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":204,"value":"import {AVLTree} from \"observable:@jwolondon/adts-and-data-structures\";","pinned":true,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":200,"value":"const avl = xs.reduce((avl, x) => avl.insert(x), new AVLTree());\n\ndisplay(avl.toDot({scale: 0.7}));","pinned":true,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":292,"value":"The advantage of an AVL tree over an unbalanced BST is most apparent for queries when values have been inserted in sorted order. Below is the AVL tree after inserting integers 1–31 in ascending order. In the unbalanced BST, 31 would be 30 edges from the root; in this AVL tree it is only 4 edges from the root, equal to ${tex`\\left\\lfloor \\log_2(31) \\right\\rfloor`}.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":257,"value":"d3.range(1, 32)\n .reduce((avl, x) => avl.insert(x), new AVLTree())\n .toDot({scale: 0.7})","pinned":false,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":45,"value":"$30","pinned":false,"hidden":false,"mode":"html","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":47,"value":"

AVLTreeNode

\n A node used by an AVLTree. Inherits from BinaryTreeNode.\n The height is managed internally by the AVL tree and exposed via a read-only accessor.\n

\n\n

`height: number`

\n The height of the subtree rooted at this node. A leaf has height 1;\n a missing subtree has height 0. This read-only value is maintained by the AVL tree.\n

","pinned":false,"hidden":false,"mode":"html","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":52,"value":"## 3. Red-Black Tree","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":313,"value":"A [red-black tree](https://en.wikipedia.org/wiki/Red–black_tree) is a self-balancing binary search tree that uses a 'colour' associated with each node to constrain the tree’s shape. This implementation uses the left-leaning red-black variant. Its balance is less strict than that of an AVL tree, but it still guarantees ${tex`O(\\log n)`} search, insertion and removal. Red-black trees are often used for update-heavy workloads because maintaining their looser balance may require less restructuring.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":317,"value":"Here's the same list of 20 numbers as shown for the other binary search trees, in the red-black tree. For the curious, node colours are normally an internal implementation detail, but are shown here to illustrate how the balancing rules are maintained.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":213,"value":"import { RedBlackTree } from \"observable:@jwolondon/adts-and-data-structures\"","pinned":true,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":211,"value":"const rbTree = xs.reduce((rbt, x) => rbt.insert(x), new RedBlackTree());\n\ndisplay(\n rbTree.toDot({\n scale: 0.7,\n fillClr: (node) => (node.clr === \"R\" ? \"pink\" : \"lightgrey\")\n })\n);","pinned":true,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":56,"value":"$31","pinned":false,"hidden":false,"mode":"html","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":58,"value":"

RedBlackTreeNode

\n A tree node used within a RedBlackTree. Inherits from BinaryTreeNode and includes\n a clr property that can be either \"R\" (red) or \"B\" (black).\n Colour is used internally to maintain red-black tree balance properties.\n

\n\n

`clr: \"R\" | \"B\"`

\n Indicates the node's colour. \n This is mutable by the RedBlackTree class but should be treated as internal.\n

\n\n

`isRed: boolean`

\n A read-only property that returns true if the node is red.\n Used internally to determine structural transformations during insertion and deletion.\n

","pinned":false,"hidden":false,"mode":"html","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":223,"value":"## 4. A comparison of BSTs","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":322,"value":"To see all three binary search tree variants, here they are applied to a sequence of integers from 1 to 20, shuffled in random order. Press the button to reshuffle.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":227,"value":"shuffle; // Regenerate random insert sequence when button is pressed\nconst shuffledXs = d3.shuffle(d3.range(1, 21));","pinned":true,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":229,"value":"const shuffle = view(Inputs.button(\"Shuffle insert order\"));","pinned":false,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":232,"value":"

Unbalanced BST

\n ${shuffledXs.reduce((bst, x) => bst.insert(x), new BinarySearchTree()).toDot({scale:0.7})}\n

AVL Tree

\n ${shuffledXs.reduce((bst, x) => bst.insert(x), new AVLTree()).toDot({scale:0.7})}\n

Red-Black Tree

\n ${shuffledXs.reduce((bst, x) => bst.insert(x), new RedBlackTree()).toDot({scale:0.7,\n fillClr: (node) => (node.clr === \"R\" ? \"pink\" : \"lightgrey\"),\n })}\n

","pinned":false,"hidden":false,"mode":"html","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":414,"value":"| Tree type | Balancing | Typical use | Notes |\n|---|---|---|---|\n| BST | None | Small datasets or unordered insertions | Lowest balancing overhead, but ${tex`O(n)`} worst-case operations |\n| AVL | Strict height balance | Lookup-heavy workloads | Shorter worst-case search paths, with additional height maintenance |\n| Red-black | Red-black invariants | Update-heavy workloads | Guaranteed ${tex`O(\\log n)`} operations with less rigid balance than AVL |","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":13,"value":"---\n\n## Appendices","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":15,"value":"_For API doc and page styling:_","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":412,"value":"import {defaultStyle} from \"observable:@jwolondon/utilities-cdt-2026\";","pinned":false,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":17,"value":"import { apiStyle } from \"observable:@jwolondon/data-structure-docs\"","pinned":false,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":413,"value":"defaultStyle()","pinned":false,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":20,"value":"apiStyle()","pinned":false,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W32","stdlib":"2","titling":"auto"}} 2e:"$2d:body"