百科.dev
全部条目在线工具AI 编程趋势榜开源项目技术资讯提交条目
登录
< 返回工具列表
F

functional-red-black-tree

> 编程语言
开源

一个纯粹的功能性红黑树数据结构

388 stars0 点赞2 次浏览
访问官网GitHub

工具介绍

一个纯粹的功能性红黑树数据结构

functional-red-black-tree

A fully persistent red-black tree written 100% in JavaScript. Works both in node.js and in the browser via browserify.

Functional (or fully persistent) data structures allow for non-destructive updates. So if you insert an element into the tree, it returns a new tree with the inserted element rather than destructively updating the existing tree in place. Doing this requires using extra memory, and if one were naive it could cost as much as reallocating the entire tree. Instead, this data structure saves some memory by recycling references to previously allocated subtrees. This requires using only O(log(n)) additional memory per update instead of a full O(n) copy.

Some advantages of this is that it is possible to apply insertions and removals to the tree while still iterating over previous versions of the tree. Functional and persistent data structures can also be useful in many geometric algorithms like point location within triangulations or ray queries, and can be used to analyze the history of executing various algorithms. This added power though comes at a cost, since it is generally a bit slower to use a functional data structure than an imperative version. However, if your application needs this behavior then you may consider using this module.

Install

bash
npm install functional-red-black-tree

Example

Here is an example of some basic usage:

javascript
//Load the library
var createTree = require("functional-red-black-tree")

//Create a tree
var t1 = createTree()

//Insert some items into the tree
var t2 = t1.insert(1, "foo")
var t3 = t2.insert(2, "bar")

//Remove something
var t4 = t3.remove(1)

API

javascript
var createTree = require("functional-red-black-tree")

Overview

  • Tree methods
    • var tree = createTree([compare])
    • tree.keys
    • tree.values
    • tree.length
    • tree.get(key)
    • tree.insert(key, value)
    • tree.remove(key)
    • tree.find(key)
    • tree.ge(key)
    • tree.gt(key)
    • tree.lt(key)
    • tree.le(key)
    • tree.at(position)
    • tree.begin
    • tree.end
    • tree.forEach(visitor(key,value)[, lo[, hi]])
    • tree.root
  • Node properties
    • node.key
    • node.value
    • node.left
    • node.right
  • Iterator methods
    • iter.key
    • iter.value
    • iter.node
    • iter.tree
    • iter.index
    • iter.valid
    • iter.clone()
    • iter.remove()
    • iter.update(value)
    • iter.next()
    • iter.prev()
    • iter.hasNext
    • iter.hasPrev

Tree methods

var tree = createTree([compare])

Creates an empty functional tree

  • compare is an optional comparison function, same semantics as array.sort()

Returns An empty tree ordered by compare

tree.keys

A sorted array of all the keys in the tree

tree.values

An array array of all the values in the tree

tree.length

The number of items in the tree

tree.get(key)

Retrieves the value associated to the given key

  • key is the key of the item to look up

Returns The value of the first node associated to key

tree.insert(key, value)

Creates a new tree with the new pair inserted.

  • key is the key of the item to insert
  • value is the value of the item to insert

Returns A new tree with key and value inserted

tree.remove(key)

Removes the first item with key in the tree

  • key is the key of the item to remove

Returns A new tree with the given item removed if it exists

tree.find(key)

Returns an iterator pointing to the first item in the tree with key, otherwise null.

tree.ge(key)

Find the first item in the tree whose key is >= key

  • key is the key to search for

Returns An iterator at the given element.

tree.gt(key)

Finds the first item in the tree whose key is > key

  • key is the key to search for

Returns An iterator at the given element

tree.lt(key)

Finds the last item in the tree whose key is < key

  • key is the key to search for

Returns An iterator at the given element

tree.le(key)

Finds the last item in the tree whose key is <= key

  • key is the key to search for

Returns An iterator at the given element

tree.at(position)

Finds an iterator starting at the given element

  • position is the index at which the iterator gets created

Returns An iterator starting at position

tree.begin

An iterator pointing to the first element in the tree

tree.end

An iterator pointing to the last element in the tree

tree.forEach(visitor(key,value)[, lo[, hi]])

Walks a visitor function over the nodes of the tree in order.

  • visitor(key,value) is a callback that gets executed on each node. If a truthy value is returned from the visitor, then iteration is stopped.
  • lo is an optional start of the range to visit (inclusive)
  • hi is an optional end of the range to visit (non-inclusive)

Returns The last value returned by the callback

tree.root

Returns the root node of the tree

Node properties

Each node of the tree has the following properties:

node.key

The key associated to the node

node.value

The value associated to the node

node.left

The left subtree of the node

node.right

The right subtree of the node

Iterator methods

iter.key

The key of the item referenced by the iterator

iter.value

The value of the item referenced by the iterator

iter.node

The value of the node at the iterator's current position. null is iterator is node valid.

iter.tree

The tree associated to the iterator

iter.index

Returns the position of this iterator in the sequence.

iter.valid

Checks if the iterator is valid

iter.clone()

Makes a copy of the iterator

iter.remove()

Removes the item at the position of the iterator

Returns A new binary search tree with iter's item removed

iter.update(value)

Updates the value of the node in the tree at this iterator

Returns A new binary search tree with the corresponding node updated

iter.next()

Advances the iterator to the next position

iter.prev()

Moves the iterator backward one element

iter.hasNext

If true, then the iterator is not at the end of the sequence

iter.hasPrev

If true, then the iterator is not at the beginning of the sequence

Credits

(c) 2013 Mikola Lysenko. MIT License

Issues· 0 开放

查看全部 Issues在 GitHub 打开

暂无开放 Issues,或尚未同步最近议题。

> 标签

JavaScript

暂无评论,来聊聊你的看法吧

> 工具信息

发布日期2026年8月1日
最后更新2026年9月17日
分类编程语言
定价开源

> 相关工具

T
TypeScript
JavaScript 的超集,为前端与全栈提供静态类型
P
Python
通用编程语言,广泛用于 Web、数据与 AI
G
Go
Google 推出的简洁高效系统语言