tree

Documentation

Index

• Variables
• func New(typ Type) search.Persistable
• func RBValid(bst *BST) (bool, error)
• type BST
  • func (bst *BST) Copy() interface{}
  • func (bst *BST) Delete(n search.Node) error
  • func (bst *BST) InOrderTraverse() []search.Node
  • func (bst *BST) Insert(inNode search.Node) error
  • func (bst *BST) Search(key interface{}) (bool, interface{})
  • func (bst *BST) SearchDown(key interface{}, down int) (search.Comparable, interface{})
  • func (bst *BST) SearchUp(key interface{}, up int) (search.Comparable, interface{})
  • func (bst *BST) Size() int
  • func (bst *BST) String() string
  • func (bst *BST) ToPersistent() search.DynamicPersistent
  • func (bst *BST) ToStatic() search.Static
• type FnSet
• type Type

Variables

var (
	AvlFnSet = &FnSet{
		InsertFn: avlInsert,
		DeleteFn: avlDelete,
		SearchFn: nopNode,
	}
)

var (
	// RbFnSet performs RB insert and
	// RB delete for inserts and deletes,
	// and does nothing on lookups.
	RbFnSet = &FnSet{
		InsertFn: rbInsert,
		DeleteFn: rbDelete,
		SearchFn: nopNode,
	}
)

var (
	SplayFnSet = &FnSet{
		InsertFn: splay,
		DeleteFn: splayDelete,
		SearchFn: splay,
	}
)

Functions

func New

func New(typ Type) search.Persistable

New returns a tree as defined by the input type. Hypothetically, this is the only exported function in this package not on a tree structure.

func RBValid

func RBValid(bst *BST) (bool, error)

RBValid returns whether the given BST is a valid Red Black tree

Types

type BST

type BST struct {
	*FnSet
	// contains filtered or unexported fields
}

BST is a generic binary search tree implementation. BST relies on the idea that numberous BST types are implicitly the same, but with unique functions to update their balance after each insert, delete, or search (sometimes) operation.

func (*BST) Copy

func (bst *BST) Copy() interface{}

func (*BST) Delete

func (bst *BST) Delete(n search.Node) error

Delete : Because we allow duplicate keys, because real data has duplicate keys, we require you specify what you want to delete at the given key or nil if you know for sure that there is only one value with the given key (or do not care what is deleted).

func (*BST) InOrderTraverse

func (bst *BST) InOrderTraverse() []search.Node

InOrderTraverse : There are multiple ways to traverse a tree. The most useful of these is the in-order traverse, and that's what we provide here. Other traversal methods can be added as needed.

func (*BST) Insert

func (bst *BST) Insert(inNode search.Node) error

Insert :

func (*BST) Search

func (bst *BST) Search(key interface{}) (bool, interface{})

Search :

func (*BST) SearchDown

func (bst *BST) SearchDown(key interface{}, down int) (search.Comparable, interface{})

SearchDown acts as SearchUp, but rounds down.

func (*BST) SearchUp

func (bst *BST) SearchUp(key interface{}, up int) (search.Comparable, interface{})

SearchUp performs a search, and rounds up to the nearest existing key if no node of the query key exists. SearchUp takes an optional number of times to get a node's successor, meaning you can SearchUp(key, 2) to get the value in a tree 2 greater than the input key, whether or not the input exists.

func (*BST) Size

func (bst *BST) Size() int

Size :

func (*BST) String

func (bst *BST) String() string

func (*BST) ToPersistent

func (bst *BST) ToPersistent() search.DynamicPersistent

ToPersistent converts this BST into a Persistent BST.

func (*BST) ToStatic

func (bst *BST) ToStatic() search.Static

ToStatic on a BST figures out where all nodes would exist in an array structure, then constructs an array with a length of the maximum index found.

If static stays in its own package this presents a potential import cycle-- or else all of static's tests need to exist outside of static, as it can't create an instance of a staticBST by itself.

type FnSet

type FnSet struct {
	InsertFn func(*node) *node
	DeleteFn func(*node) *node
	SearchFn func(*node) *node
}

FnSet represents the fields that need to be attached to a BST to let it generically act as any type of BST.

type Type

type Type int

Type represents the underlying algorithm for updating points on a dynamic binary search tree. This implementation relies on the idea that, in principle, all binary search trees share a lot in common (finding where to insert, delete, search), and any remaining details just depend on what specific BST type is being used.

const (
	AVL      Type = iota
	RedBlack      // RB would probably be okay.
	Splay
)

TreeType enum