ref

package
v0.0.0-...-c1449ee Latest Latest
Warning

This package is not in the latest version of its module.

Go to latest
Published: Jul 25, 2024 License: MIT Imports: 0 Imported by: 0

Documentation

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

This section is empty.

Types

type Finder

type Finder interface {

	// Find returns the lowest common ancestor between a and b.
	// If a or b is root, the lowest common ancestor is root.
	// If one of a or b is an ancestor of another, the lowest common ancestor is the next their ancestor.
	// So, only root might be an ancestor of itself.
	Find(a, b Key) *Key
}

Finder calculates the lowest common ancestor.

type Key

type Key string

Key is a key to identify nodes.

type Node

type Node struct {
	Key      Key    `json:"name"`
	Subnodes []Node `json:"employees"`
}

Node represents a node of a tree. Key of node must be unique for identification.

type Tarjan

type Tarjan struct {
	// contains filtered or unexported fields
}

Tarjan represents Tarjan algorithm.

func NewTarjan

func NewTarjan(d *Node) *Tarjan

NewTarjan release Tarjan's LCA algorithm.

func (*Tarjan) Find

func (tar *Tarjan) Find(a, b Key) *Key

Find realises Finder interface using Tarjan algorithm with path compression and union by rank heuristics. The algorithm uses preprocessing during NewTarjan method, so at this moment its complexity is ~O(1).

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL