tree

Documentation

Index

• Constants
• func BSTreeToString(n *BSTreeNode, depth int, buffer *bytes.Buffer)
• func NewAVLTreeNode(k interface{}, v interface{}) *avlTreeNode
• func NewRBTreeNode(key interface{}, value interface{}) *rbTreeNode
• type AVLTree
  • func NewAVLTree() *AVLTree
  • func (at *AVLTree) Add(key interface{}, val interface{})
  • func (at *AVLTree) Contains(key interface{}) bool
  • func (at *AVLTree) Get(key interface{}) interface{}
  • func (at *AVLTree) IsBST() bool
  • func (at *AVLTree) IsBalanced() bool
  • func (at *AVLTree) IsEmpty() bool
  • func (at *AVLTree) Remove(key interface{}) interface{}
  • func (at *AVLTree) Set(key interface{}, val interface{})
  • func (at *AVLTree) Size() int
  • func (at *AVLTree) String() string
• type BSTree
  • func NewBSTree() *BSTree
  • func (tree *BSTree) Add(e interface{})
  • func (tree *BSTree) Contains(e interface{}) bool
  • func (tree *BSTree) InOrder()
  • func (tree *BSTree) IsEmpty() bool
  • func (tree *BSTree) LevelOrder()
  • func (tree *BSTree) Maximum() interface{}
  • func (tree *BSTree) Minimum() interface{}
  • func (tree *BSTree) PostOrder()
  • func (tree *BSTree) PreOrder()
  • func (tree *BSTree) PreOrderNR()
  • func (tree *BSTree) Remove(e interface{})
  • func (tree *BSTree) RemoveMax() interface{}
  • func (tree *BSTree) RemoveMin() interface{}
  • func (tree *BSTree) Size() int
  • func (tree *BSTree) String() string
• type BSTreeNode
  • func NewBSTreeNode(e interface{}) *BSTreeNode
• type ITree
• type Merger
• type RBTree
  • func NewRBTree() *RBTree
  • func (rt *RBTree) Add(key interface{}, val interface{})
  • func (rt *RBTree) Contains(key interface{}) bool
  • func (rt *RBTree) Get(key interface{}) interface{}
  • func (rt *RBTree) IsEmpty() bool
  • func (rt *RBTree) KeySet() []interface{}
  • func (rt *RBTree) Remove(key interface{}) interface{}
  • func (rt *RBTree) Set(key interface{}, val interface{})
  • func (rt *RBTree) Size() int
  • func (rt *RBTree) String() string
• type SegmentTree
  • func NewSegmentTree(arr []interface{}, merger Merger) *SegmentTree
  • func (st *SegmentTree) Get(index int) interface{}
  • func (st *SegmentTree) Query(queryL int, queryR int) interface{}
  • func (st *SegmentTree) Set(index int, e interface{})
  • func (st *SegmentTree) Size() int
  • func (st *SegmentTree) String() string
• type Trie
  • func NewTrie() *Trie
  • func (trie *Trie) Add(word string)
  • func (trie *Trie) AddWord(word string)
  • func (trie *Trie) Search(word string) bool
  • func (trie *Trie) Size() int
  • func (trie *Trie) String() string
• type TrieNode
  • func NewNode() *TrieNode
  • func (t *TrieNode) String() string

Constants

const BLACK = false

const RED = true

Functions

func BSTreeToString

func BSTreeToString(n *BSTreeNode, depth int, buffer *bytes.Buffer)

生成以 BSTreeNode 为根节点，深度为 depth 的描述二叉树的字符串

func NewAVLTreeNode

func NewAVLTreeNode(k interface{}, v interface{}) *avlTreeNode

生成 avlTreeNode 节点

func NewRBTreeNode

func NewRBTreeNode(key interface{}, value interface{}) *rbTreeNode

生成node节点，默认为红色

Types

type AVLTree

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

AVLTree 平衡二叉树

func NewAVLTree

func NewAVLTree() *AVLTree

func (*AVLTree) Add

func (at *AVLTree) Add(key interface{}, val interface{})

向二分搜索树中添加新的元素(key, value)

func (*AVLTree) Contains

func (at *AVLTree) Contains(key interface{}) bool

func (*AVLTree) Get

func (at *AVLTree) Get(key interface{}) interface{}

func (*AVLTree) IsBST

func (at *AVLTree) IsBST() bool

判断该二叉树是否是一颗二分搜索树，判断它的key 是否有序排序

func (*AVLTree) IsBalanced

func (at *AVLTree) IsBalanced() bool

判断该二叉树是否是一棵平衡二叉树

func (*AVLTree) IsEmpty

func (at *AVLTree) IsEmpty() bool

func (*AVLTree) Remove

func (at *AVLTree) Remove(key interface{}) interface{}

从二分搜索树中删除键为 key 的节点

func (*AVLTree) Set

func (at *AVLTree) Set(key interface{}, val interface{})

func (*AVLTree) Size

func (at *AVLTree) Size() int

func (*AVLTree) String

func (at *AVLTree) String() string

type BSTree

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

func NewBSTree

func NewBSTree() *BSTree

func (*BSTree) Add

func (tree *BSTree) Add(e interface{})

向二分搜索树中添加新的元素 e

func (*BSTree) Contains

func (tree *BSTree) Contains(e interface{}) bool

看二分搜索树中是否包含元素 e

func (*BSTree) InOrder

func (tree *BSTree) InOrder()

二分搜索树的中序遍历

func (*BSTree) IsEmpty

func (tree *BSTree) IsEmpty() bool

func (*BSTree) LevelOrder

func (tree *BSTree) LevelOrder()

二分搜索树的层序遍历

func (*BSTree) Maximum

func (tree *BSTree) Maximum() interface{}

寻找二分搜索树的最大元素

func (*BSTree) Minimum

func (tree *BSTree) Minimum() interface{}

寻找二分搜索树的最小元素

func (*BSTree) PostOrder

func (tree *BSTree) PostOrder()

二分搜索树的后序遍历

func (*BSTree) PreOrder

func (tree *BSTree) PreOrder()

二分搜索树的前序遍历

func (*BSTree) PreOrderNR

func (tree *BSTree) PreOrderNR()

二分搜索树的非递归前序遍历

func (*BSTree) Remove

func (tree *BSTree) Remove(e interface{})

从二分搜索树中删除元素为 e 的节点

func (*BSTree) RemoveMax

func (tree *BSTree) RemoveMax() interface{}

从二分搜索树中删除最小值所在的节点，返回最小值

func (*BSTree) RemoveMin

func (tree *BSTree) RemoveMin() interface{}

从二分搜索树中删除最小值所在的节点，返回最小值

func (*BSTree) Size

func (tree *BSTree) Size() int

func (*BSTree) String

func (tree *BSTree) String() string

type BSTreeNode

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

二分查找树

func NewBSTreeNode

func NewBSTreeNode(e interface{}) *BSTreeNode

type ITree

type ITree interface {
	Add(interface{}, interface{})
	Remove(interface{}) interface{}
	Contains(interface{}) bool
	Get(interface{}) interface{}
	Set(interface{}, interface{})
	Size() int
	IsEmpty() bool
}

type Merger

type Merger interface {
	Merge(interface{}, interface{}) interface{}
}

type RBTree

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

RBTree 红黑树

func NewRBTree

func NewRBTree() *RBTree

func (*RBTree) Add

func (rt *RBTree) Add(key interface{}, val interface{})

向红黑树中添加新的元素(key, value)

func (*RBTree) Contains

func (rt *RBTree) Contains(key interface{}) bool

func (*RBTree) Get

func (rt *RBTree) Get(key interface{}) interface{}

func (*RBTree) IsEmpty

func (rt *RBTree) IsEmpty() bool

func (*RBTree) KeySet

func (rt *RBTree) KeySet() []interface{}

获得红黑树所有的 key

func (*RBTree) Remove

func (rt *RBTree) Remove(key interface{}) interface{}

从二分搜索树中删除键为key的节点

func (*RBTree) Set

func (rt *RBTree) Set(key interface{}, val interface{})

func (*RBTree) Size

func (rt *RBTree) Size() int

func (*RBTree) String

func (rt *RBTree) String() string

type SegmentTree

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

func NewSegmentTree

func NewSegmentTree(arr []interface{}, merger Merger) *SegmentTree

func (*SegmentTree) Get

func (st *SegmentTree) Get(index int) interface{}

func (*SegmentTree) Query

func (st *SegmentTree) Query(queryL int, queryR int) interface{}

返回区间[queryL, queryR]的值

func (*SegmentTree) Set

func (st *SegmentTree) Set(index int, e interface{})

func (*SegmentTree) Size

func (st *SegmentTree) Size() int

func (*SegmentTree) String

func (st *SegmentTree) String() string

type Trie

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

func NewTrie

func NewTrie() *Trie

func (*Trie) Add

func (trie *Trie) Add(word string)

向Trie中添加一个新的单词word

func (*Trie) AddWord

func (trie *Trie) AddWord(word string)

* Adds a word into the data structure.

func (*Trie) Search

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

* Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter.

func (*Trie) Size

func (trie *Trie) Size() int

获得Trie中存储的单词数量

func (*Trie) String

func (trie *Trie) String() string

type TrieNode

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

func NewNode

func NewNode() *TrieNode

func (*TrieNode) String

func (t *TrieNode) String() string