README
¶
AVL Tree Binary Search Tree for Go
Table of Contents
Documentation
You can find the package documentation at https://pkg.go.dev/github.com/jrpalma/arg
Overview
AVL is a Go package used to insert, search, and delete in O(log n). The package also has the ability traverse the AVL tree in ascending and descending order. The AVL API is relatively simple and can be used quickly.
Installing
You can install avl under your GOPATH if your version of Go does not support modules. Run the following command to install avl under your GOPATH:
go get github.com/jrpalma/avl
AVL also support Go modules. All you have to do is initialize your project and import avl into your project. If your project has not been initialized, all you have to do is run the following command under your project:
# You will have to specify <project path>
# if you are outside your GOPATH
go mod init <project path>
Concepts
An AVL Tree is a data structure that can insert, search, and delete in O(log n). The package provides the ability to insert, search, and delete by using the Put, Get, and Del methods respectively. Because Go does not support generics at this time, AVL uses the Key interface and type assertion to insert, search, and delete.
Interface
AVL uses the Key interface to be able to properly balance the tree. In order to insert, search, and delete records, the record must implement the Key interface. The following code describes the Key interface and User record that impelements the Key interface by the user ID.
type Key interface {
Less(Key) bool
Equals(Key) bool
}
type User interface {
ID uint64
Name string
Age uint8
}
func (u *User) Less(k Key) bool {
return u.ID < k.(User).ID
}
func (u *User) Equals(k Key) bool {
return u.ID == k.(User).ID
}
Operations
AVL has the ability to insert, search and delete. The following piece of code makes uses the User struct above to be able to insert, search, and delete by user ID.
cache := &avl.Tree{}
cache.Put(&User{ID: 10, Name: "Joe Smith", Age: 19})
cache.Put(&User{ID: 11, Name: "Bob Palmer", Age: 41})
cache.Put(&User{ID: 12, Name: "Tom McDonals", Age: 27})
user := cache.Get(&User{ID: 10})
if user, ok := user.(*User); ok {
user.Age = 20
}
user.Del(&User{ID: 12})
Traversing
AVL has the ability to traverse the tree in ascending and descending order. The function must return false in order to stop traversing. This can be achieved by simply calling the VisitAscending and VisitDescending functions like in the following example.
cache.VisitAscending(func(k Key) bool {
fmt.Printf("%+v\n", k.(*User))
return true
})
cache.VisitDescending(func(k Key) bool {
fmt.Printf("%+v\n", k.(*User))
return true
})
Contributing
- Fork it
- Clone it
git clone https://github.com/user_name/avl && cd avl) - Create your feature branch (
git checkout -b my-new-feature) - Make changes and add them (
git add .) - Commit your changes (
git commit -m 'Add some feature') - Push to the branch (
git push origin my-new-feature) - Create new pull request
Documentation
¶
Overview ¶
Example (Usage) ¶
ExampleUsage Shows how this package can be used
package main
import (
"fmt"
)
func NewUserStore() *UserStore {
return &UserStore{tree: &Tree{}}
}
type UserVisit func(*User) bool
type User struct {
ID uint64
Age uint8
}
func (u *User) Less(k Key) bool {
return u.ID < k.(*User).ID
}
func (u *User) Equals(k Key) bool {
return u.ID == k.(*User).ID
}
type UserStore struct {
tree *Tree
}
func (us *UserStore) Get(id uint64) *User {
v := us.tree.Get(&User{ID: id})
if v == nil {
return nil
}
return v.(*User)
}
func (us *UserStore) Size() int {
return us.tree.Size()
}
func (us *UserStore) Clear() {
us.tree.Clear()
}
func (us *UserStore) Has(id uint64) bool {
return us.tree.Has(&User{ID: id})
}
func (us *UserStore) Del(id uint64) {
us.tree.Del(&User{ID: id})
}
func (us *UserStore) Put(u *User) {
us.tree.Put(u)
}
func (us *UserStore) VisitAscending(v UserVisit) {
us.tree.VisitAscending(func(k Key) bool {
v(k.(*User))
return true
})
}
func (us *UserStore) VisitDescending(v UserVisit) {
us.tree.VisitDescending(func(k Key) bool {
v(k.(*User))
return true
})
}
// ExampleUsage Shows how this package can be used
func main() {
us := NewUserStore()
for i := 1; i <= 256; i++ {
us.Put(&User{ID: uint64(i)})
}
if us.Size() != 256 {
panic("Size should be 256")
}
user := us.Get(128)
if user == nil {
panic("Should have user with ID 128")
}
fmt.Printf("%+v\n", user)
if !us.Has(128) {
panic("Should have user ID 128")
}
us.Del(128)
if us.Has(128) {
panic("Should not have user ID 128")
}
us.Clear()
}
Output: &{ID:128 Age:0}
Index ¶
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Tree ¶
type Tree struct {
// contains filtered or unexported fields
}
Tree An AVL tree to insert, search, and delete in O(log n)
func (*Tree) Get ¶
Get Searches for node with the Key k and returns the key. It returns nil if the Key cannot be found in the tree.
func (*Tree) Put ¶
Put Inserts a node with Key k into the tree. The node is not inserted if a node with the Key k alredy exist.
func (*Tree) VisitAscending ¶
VisitAscending Traverse the tree from the smallest to the largest Key by calling the Visit function v.
func (*Tree) VisitDescending ¶
VisitDescending Traverse the tree from the largest to the smalles Key by calling the Visit function v.
Source Files