tree23

KO | EN

gitlite — search

#javascript #python #hacktoberfest #react #ai #typescript #llm #go #golang #android #machine-learning #rust #deep-learning #linux

★ 8 Open GitHub ↗

An implementation of a balanced 2,3-tree that allows accessing next/previous elements in O(1) at all times.

// repository documentation

Was this content helpful?

★ 0 (0 ratings)

[![Go Report Card](https://goreportcard.com/badge/github.com/mauricegit/tree23)](https://goreportcard.com/report/github.com/mauricegit/tree23)

# 2,3-Tree

A Go library that implements a completely balanced 2,3-Tree that allows generic data as values in the tree.
A 2,3-Tree self-balances itself when inserting or deleting elements and it is guaranteed, that all leaf nodes will
be at a level at all times. The balancing itself runs in O(1) while ascending the tree.
All nodes will be positioned at the leaf-level. Inserting/Deleting/Searching all take O(log n) time with the logarithm between base 2 and 3.

Additionally, all leaf nodes are linked to another in a sorted order (and circularly). This additionally allows accessing
previous or next items (when we already have a leaf node) in O(1) without the need to further traverse the tree.
An iterator is simply achieved by retrieving the smallest child (there is a function for that) and following the .Next() links.

Further, the tree allows accessing elements close to a given value (without knowing the exact leaf value!).

## Documentation:

For detailed functionality and API, please have a look at the generated Go Docs: [https://godoc.org/github.com/MauriceGit/tree23](https://godoc.org/github.com/MauriceGit/tree23).

A fully functional example of creating a tree, inserting/deleting/searching:

```go

import (
    "github.com/MauriceGit/tree23"
)

type Element struct {
    E int
}

func (e Element) Equal(e2 TreeElement) bool {
    return e.E == e2.(Element).E
}
func (e Element) ExtractValue() float64 {
    return float64(e.E)
}

func main() {
    tree := New()

for i := 0; i < 100000; i++ {
        tree.Insert(Element{i})
    }

// e1 will be the leaf node: 14
    e1, err := tree.FindFirstLargerLeaf(13.000001)
    // e2 will be the leaf node: 7
    e2, err := tree.Find(Element{7})
    // e3 will be the leaf node: 8
    e3, err := tree.Next(e2)
    // e4 will be the leaf node: 6
    e4, err := tree.Previous(e2)
    // smallest will be the leaf node: 0
    smallest, err := tree.GetSmallestLeaf()
    // largest will be the leaf node: 99999
    largest, err  := tree.GetLargestLeaf()

for i := 0; i < 100000; i++ {
        tree.Delete(Element{i})
    }

// tree is now empty.

...
}

```

tree23

Explore Similar Repositories

Was this content helpful?

Recent Feedback

Download README