tree

package
v1.1.0 Latest Latest
Warning

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

 Go to latest Published: Jan 2, 2025 License: MIT Imports: 4 Imported by: 0

Documentation

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

func MaxCombine 

func MaxCombine(a, b int) int

func MinCombine 

func MinCombine(a, b int) int

func SumCombine 

func SumCombine(a, b int) int

Common combine functions

Types

type AVLNode 

type AVLNode struct {
	Key    int
	Height int
	Left   *AVLNode
	Right  *AVLNode
}

AVLNode represents a node in AVL tree

type AVLTree 

type AVLTree struct {
	Root *AVLNode
	// contains filtered or unexported fields
}

AVLTree represents an AVL tree

func NewAVLTree 

func NewAVLTree() *AVLTree

NewAVLTree creates a new AVL tree

func (*AVLTree) InOrderTraversal 

func (t *AVLTree) InOrderTraversal(result *[]int)

InOrderTraversal performs inorder traversal of the tree

func (*AVLTree) Insert 

func (t *AVLTree) Insert(key int)

Insert adds a new node to the tree

func (*AVLTree) Search 

func (t *AVLTree) Search(key int) bool

Search looks for a value in the tree

type BPlusNode added in v1.1.0 

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

BPlusNode represents a node in the B+ tree

type BPlusTree added in v1.1.0 

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

BPlusTree represents a B+ tree

func NewBPlusTree added in v1.1.0 

func NewBPlusTree() *BPlusTree

NewBPlusTree creates a new B+ tree

func (*BPlusTree) Clear added in v1.1.0 

func (bt *BPlusTree) Clear()

Clear removes all keys from the tree

func (*BPlusTree) Insert added in v1.1.0 

func (bt *BPlusTree) Insert(key int)

Insert adds a new key to the tree

func (*BPlusTree) IsEmpty added in v1.1.0 

func (bt *BPlusTree) IsEmpty() bool

IsEmpty returns true if the tree is empty

func (*BPlusTree) Search added in v1.1.0 

func (bt *BPlusTree) Search(key int) bool

Search finds a key in the tree

func (*BPlusTree) Size added in v1.1.0 

func (bt *BPlusTree) Size() int

Size returns the number of keys in the tree

type BTree 

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

BTree represents a B-tree

func NewBTree 

func NewBTree(t int) *BTree

NewBTree creates a new B-tree with minimum degree t

func (*BTree) Delete 

func (tree *BTree) Delete(k int)

Delete removes a key from the B-tree

func (*BTree) GetInOrder 

func (tree *BTree) GetInOrder() []int

GetInOrder returns all keys in the B-tree in sorted order

func (*BTree) Insert 

func (tree *BTree) Insert(k int)

Insert inserts a key into the B-tree

func (*BTree) Search 

func (tree *BTree) Search(k int) bool

Search searches for a key in the B-tree

type BTreeNode 

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

BTreeNode represents a node in B-tree

type Color 

type Color bool

Color represents the color of a node in Red-Black tree 

const (
	RED   Color = true
	BLACK Color = false
)

type IBinaryTree 

type IBinaryTree interface {
	Insert(data int)
	Search(data int)
	Exists(data int) bool
	Delete(data int)
	Max() int
	Min() int
	Print(pType string)
	List(pType string) []int
}

func BinaryTree 

func BinaryTree(data int) IBinaryTree

type RBNode 

type RBNode struct {
	Key                 int
	Color               Color
	Left, Right, Parent *RBNode
}

RBNode represents a node in Red-Black tree

type RadixNode added in v1.1.0 

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

RadixNode represents a node in the Radix Tree

type RadixTree added in v1.1.0 

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

RadixTree represents a radix tree (compact trie) data structure

func NewRadixTree added in v1.1.0 

func NewRadixTree() *RadixTree

NewRadixTree creates a new empty radix tree

func (*RadixTree) Clear added in v1.1.0 

func (rt *RadixTree) Clear()

Clear removes all keys from the tree

func (*RadixTree) Delete added in v1.1.0 

func (rt *RadixTree) Delete(key string) bool

Delete removes a key from the tree

func (*RadixTree) Insert added in v1.1.0 

func (rt *RadixTree) Insert(key string, value interface{})

Insert adds a key-value pair to the tree

func (*RadixTree) IsEmpty added in v1.1.0 

func (rt *RadixTree) IsEmpty() bool

IsEmpty returns true if the tree is empty

func (*RadixTree) Keys added in v1.1.0 

func (rt *RadixTree) Keys() []string

Keys returns all keys in the tree

func (*RadixTree) Search added in v1.1.0 

func (rt *RadixTree) Search(key string) (interface{}, bool)

Search finds a key in the tree and returns its value

func (*RadixTree) Size added in v1.1.0 

func (rt *RadixTree) Size() int

Size returns the number of keys in the tree

type RedBlackTree 

type RedBlackTree struct {
	Root *RBNode
	NIL  *RBNode // Sentinel node
	// contains filtered or unexported fields
}

RedBlackTree represents a Red-Black tree

func NewRedBlackTree 

func NewRedBlackTree() *RedBlackTree

NewRedBlackTree creates a new Red-Black tree

func (*RedBlackTree) InOrderTraversal 

func (t *RedBlackTree) InOrderTraversal(result *[]int)

InOrderTraversal performs an inorder traversal of the tree

func (*RedBlackTree) Insert 

func (t *RedBlackTree) Insert(key int)

Insert adds a new key to the tree

func (*RedBlackTree) Search 

func (t *RedBlackTree) Search(key int) bool

Search looks for a key in the tree

type SegmentTree 

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

SegmentTree represents a segment tree data structure

func NewSegmentTree 

func NewSegmentTree(arr []int, combine func(int, int) int) *SegmentTree

NewSegmentTree creates a new segment tree from an array

func (*SegmentTree) GetArray 

func (st *SegmentTree) GetArray() []int

GetArray returns the current array

func (*SegmentTree) Query 

func (st *SegmentTree) Query(left int, right int) int

Query returns the result of the combine function over the range [left, right]

func (*SegmentTree) Update 

func (st *SegmentTree) Update(i int, val int)

Update updates the value at index i to val

type SplayNode added in v1.1.0 

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

Node represents a node in the Splay Tree

type SplayTree added in v1.1.0 

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

SplayTree represents a self-adjusting binary search tree

func NewSplayTree added in v1.1.0 

func NewSplayTree() *SplayTree

NewSplayTree creates and returns a new Splay Tree

func (*SplayTree) Clear added in v1.1.0 

func (st *SplayTree) Clear()

Clear removes all nodes from the tree

func (*SplayTree) Delete added in v1.1.0 

func (st *SplayTree) Delete(key int) bool

Delete removes a node with the given key from the tree

func (*SplayTree) Insert added in v1.1.0 

func (st *SplayTree) Insert(key int)

Insert adds a new key to the tree

func (*SplayTree) IsEmpty added in v1.1.0 

func (st *SplayTree) IsEmpty() bool

IsEmpty returns true if the tree is empty

func (*SplayTree) Search added in v1.1.0 

func (st *SplayTree) Search(key int) bool

Search finds a node with the given key and splays it to the root

func (*SplayTree) Size added in v1.1.0 

func (st *SplayTree) Size() int

Size returns the number of nodes in the tree

type TSTNode added in v1.1.0 

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

TSTNode represents a node in the Ternary Search Tree

type TernarySearchTree added in v1.1.0 

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

TernarySearchTree represents a ternary search tree data structure

func NewTernarySearchTree added in v1.1.0 

func NewTernarySearchTree() *TernarySearchTree

NewTernarySearchTree creates a new empty ternary search tree

func (*TernarySearchTree) Clear added in v1.1.0 

func (tst *TernarySearchTree) Clear()

Clear removes all keys from the tree

func (*TernarySearchTree) Delete added in v1.1.0 

func (tst *TernarySearchTree) Delete(key string) bool

Delete removes a key from the tree

func (*TernarySearchTree) Insert added in v1.1.0 

func (tst *TernarySearchTree) Insert(key string, value interface{})

Insert adds a key-value pair to the tree

func (*TernarySearchTree) IsEmpty added in v1.1.0 

func (tst *TernarySearchTree) IsEmpty() bool

IsEmpty returns true if the tree is empty

func (*TernarySearchTree) Keys added in v1.1.0 

func (tst *TernarySearchTree) Keys() []string

Keys returns all keys in the tree

func (*TernarySearchTree) Search added in v1.1.0 

func (tst *TernarySearchTree) Search(key string) (interface{}, bool)

Search finds a key in the tree and returns its value

func (*TernarySearchTree) Size added in v1.1.0 

func (tst *TernarySearchTree) Size() int

Size returns the number of keys in the tree

func (*TernarySearchTree) StartsWith added in v1.1.0 

func (tst *TernarySearchTree) StartsWith(prefix string) []string

StartsWith returns all strings in the tree that start with the given prefix

type Trie 

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

Trie represents a Trie (prefix tree)

func NewTrie 

func NewTrie() *Trie

NewTrie creates a new Trie

func (*Trie) Delete 

func (t *Trie) Delete(word string) bool

Delete removes a word from the trie

func (*Trie) GetAllWords 

func (t *Trie) GetAllWords() []string

GetAllWords returns all words stored in the trie

func (*Trie) GetWordsWithPrefix 

func (t *Trie) GetWordsWithPrefix(prefix string) []string

GetWordsWithPrefix returns all words that start with the given prefix

func (*Trie) Insert 

func (t *Trie) Insert(word string)

Insert adds a word to the trie

func (*Trie) Search 

func (t *Trie) Search(word string) bool

Search returns true if the word is in the trie

func (*Trie) StartsWith 

func (t *Trie) StartsWith(prefix string) bool

StartsWith returns true if there is any word in the trie that starts with the given prefix

type TrieNode 

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

TrieNode represents a node in Trie

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.