tree

package
v1.3.0 Latest Latest
Warning

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

 Go to latest Published: Mar 8, 2025 License: MIT Imports: 4 Imported by: 0

README

Tree Data Structures Package

This package provides implementations of various tree data structures in Go. All implementations are thread-safe and support concurrent operations.

Features

Binary Search Tree
  • Basic binary search tree implementation
  • Thread-safe operations with RWMutex
  • Supports:
    • Insert
    • Search/Exists
    • Delete
    • Min/Max value finding
    • Multiple traversal orders (Infix, Prefix, Postfix)
    • Custom traversal directions (LNR, RNL, NLR, NRL, LRN, RLN)
AVL Tree
  • Self-balancing binary search tree
  • Maintains height balance property
  • Operations:
    • Insert with automatic rebalancing
    • Search
    • InOrder traversal
  • Balance operations:
    • Left rotation
    • Right rotation
    • Height updates
    • Balance factor calculation
Red-Black Tree
  • Self-balancing binary search tree with color properties
  • Maintains Red-Black properties:
    • Root is black
    • Red nodes can't have red children
    • All paths have same number of black nodes
  • Operations:
    • Insert with color fixing
    • Search
    • InOrder traversal
  • Balance operations:
    • Left rotation
    • Right rotation
    • Color adjustments
B+ Tree
  • Optimized for storage systems
  • Multiple keys per node
  • All data stored in leaf nodes
  • Leaf nodes linked for range queries
Segment Tree
  • Efficient for range queries
  • Supports range updates
  • Used for computational geometry
Radix Tree
  • Compressed prefix tree
  • Memory efficient for strings
  • Fast prefix matching
Ternary Search Tree
  • Hybrid between binary tree and trie
  • Efficient for string operations
  • Space-efficient compared to standard tries

Usage Examples

Binary Search Tree
// Create a new binary tree
tree := BinaryTree(10)

// Insert elements
tree.Insert(5)
tree.Insert(15)
tree.Insert(3)

// Search for elements
tree.Search(5)  // prints: 5: available in the tree
exists := tree.Exists(15) // returns: true

// Find min/max
min := tree.Min() // returns: 3
max := tree.Max() // returns: 15

// Print in different orders
tree.Print("LNR") // Inorder: 3 5 10 15
tree.Print("NLR") // Preorder: 10 5 3 15
AVL Tree
// Create a new AVL tree
avl := NewAVLTree()

// Insert elements (tree automatically balances)
avl.Insert(10)
avl.Insert(20)
avl.Insert(30)

// Search for elements
found := avl.Search(20) // returns: true

// Get sorted elements
var result []int
avl.InOrderTraversal(&result)
Red-Black Tree
// Create a new Red-Black tree
rb := NewRedBlackTree()

// Insert elements (tree maintains Red-Black properties)
rb.Insert(10)
rb.Insert(20)
rb.Insert(30)

// Search for elements
found := rb.Search(20) // returns: true

// Get sorted elements
var result []int
rb.InOrderTraversal(&result)

Implementation Details

Thread Safety
  • All tree implementations use sync.RWMutex
  • Read operations use RLock
  • Write operations use Lock
  • Proper lock/unlock handling with defer
Performance Characteristics
Binary Search Tree
  • Average case: O(log n) for all operations
  • Worst case: O(n) when unbalanced
AVL Tree
  • All operations: O(log n) guaranteed
  • Extra space for height information
  • More rotations than Red-Black tree
Red-Black Tree
  • All operations: O(log n) guaranteed
  • Less rotations than AVL tree
  • Slightly more space for color information

Testing

Each tree implementation comes with comprehensive test coverage. Run tests using:

go test ./...

Contributing

Contributions are welcome! Please ensure that any new features or modifications come with:

  • Proper documentation
  • Thread safety considerations
  • Comprehensive test cases
  • Example usage

License

This package is distributed under the MIT license. See the LICENSE file for more details.

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.