wbtree

Weight Balanced Tree

A simple module to keep a binary tree "weight balanced".

Can be used to implement a self-balancing binary search tree.

Installation

yarn add wbtree

Usage

To implement a basic sorted set insertion you could implement something like this:

import { WBTNode, balanceLeft, balanceRight } from "wbtree"

const insert = (value, root) => {
  if (root === undefined) {
    return { data: { value, size: 1 } }
  }

  if (value < root.data.value) {
    root.data.size += 1
    root.left = insert(value, root.left)
    return balanceRight(root)
  } else if (root.data.value < value) {
    root.data.size += 1
    root.right = insert(value, root.right)
    return balanceLeft(root)
  }
  return root
}