Skip to content
Golang radix tree implementation
Go
Branch: master
Clone or download
Gabriel Sanches
Gabriel Sanches Update CHANGELOG.md
Latest commit 505b96d Mar 11, 2019
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
.editorconfig
.gitignore
.travis.yml
CHANGELOG.md
Gopkg.lock
Gopkg.toml
LICENSE
README.md
benchmark_test.go
bit.go
builder.go
colors.go
doc.go
edge.go
example_test.go
go.mod
go.sum
node.go
sorter.go
tree.go
tree_test.go

README.md

radix (Radix tree implementation in Go)

Build Status Sourcegraph GoDoc Minimal Version

About

This package is an implementation of a radix tree in Go (or Golang).

Searching for static values in the tree doesn't allocate memory on the heap, what makes it pretty fast.
It can also sort nodes by priority, therefore traversing nodes that hold more non-nil values first.

Usage

Full documentation here.

Installing

Go 1.10

vgo get -u github.com/gbrlsnchs/radix

Go 1.11

go get -u github.com/gbrlsnchs/radix

Importing

import (
	// ...

	"github.com/gbrlsnchs/radix"
)

Building this example from Wikipedia

tr := radix.New(radix.Tdebug)
tr.Add("romane", 1)
tr.Add("romanus", 2)
tr.Add("romulus", 3)
tr.Add("rubens", 4)
tr.Add("ruber", 5)
tr.Add("rubicon", 6)
tr.Add("rubicundus", 7)
tr.Sort(radix.PrioritySort) // optional step
fmt.Println(tr)

The code above will print this

. (14 nodes)
└── 7↑ r → <nil>
    ├── 4↑ ub → <nil>
    │   ├── 2↑ ic → <nil>
    │   │   ├── 1↑ undus 🍂 → 7
    │   │   └── 1↑ on 🍂 → 6
    │   └── 2↑ e → <nil>
    │       ├── 1↑ r 🍂 → 5
    │       └── 1↑ ns 🍂 → 4
    └── 3↑ om → <nil>
        ├── 2↑ an → <nil>
        │   ├── 1↑ us 🍂 → 2
        │   └── 1↑ e 🍂 → 1
        └── 1↑ ulus 🍂 → 3

Retrieving a value from the tree

n, _ := tr.Get("rubicon") // zero-allocation search
fmt.Println(n.Value)      // prints "6"

Building a dynamic tree

A dynamic tree is a tree that can match labels based on a placeholder and a demiliter (e.g. an HTTP router that accepts dynamic routes).
Note that this only works with prefix trees, not binary ones.

tr := radix.New(0) // passing 0 means passing no flags
tr.Add("/dynamic/path/@id", 1)
tr.Add("/dynamic/path/@id/subpath/@name", 2)
tr.Add("/static/path", 3)
tr.SetBoundaries('@', '/')

var (
	n *radix.Node
	p map[string]string
)
n, p = tr.Get("/dynamic/path/123")
fmt.Println(n.Value) // prints "1"
fmt.Println(p["id"]) // prints "123"

n, p = tr.Get("/dynamic/path/456/subpath/foobar")
fmt.Println(n.Value)   // prints "2"
fmt.Println(p["id"])   // prints "456"
fmt.Println(p["name"]) // prints "foobar"

n, _ = tr.Get("/static/path") // p would be nil
fmt.Println(n.Value)          // prints "3"

Building a binary tree

tr := radix.New(radix.Tdebug | radix.Tbinary)
tr.Add("deck", 1)
tr.Add("did", 2)
tr.Add("doe", 3)
tr.Add("dog", 4)
tr.Add("doge", 5)
tr.Add("dogs", 6)

The code above will print this

. (71 nodes)
01100100011001010110001101101011 🍂 → 1
011001000110100101100100 🍂 → 2
011001000110111101100101 🍂 → 3
011001000110111101100111 → 4
01100100011011110110011101100101 🍂 → 5
01100100011011110110011101110011 🍂 → 6

Contributing

How to help

You can’t perform that action at this time.