tree

package
v0.0.0-...-d7c879d Latest Latest
Warning

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

 Go to latest Published: Oct 24, 2023 License: Apache-2.0 Imports: 7 Imported by: 0

Documentation

Index

Constants

View Source 
const (
	// 红节点
	RED = true
	// 黑节点
	BLACK = false
)

二分搜索树是二叉树,因为其中序列遍历的有序性也称二分搜索树为排序树

二分搜索树的每隔节点的值: 

大于其左子节点的所有节点的值
小于其右子节点的所有节点的值

为了满足此特性,二分搜索树中不允许有相等的元素

每一棵子树也是二分搜索树

存入二分搜索树中的节点必须是可以比较的,想要存入基础类型就必须给基础类型实现 

common.CompareAble接口

Variables

This section is empty.

Functions

This section is empty.

Types

type AVLIsEmptyError 

type AVLIsEmptyError struct {
}

func (AVLIsEmptyError) Error 

func (AVLIsEmptyError) Error() string

type AVLTree 

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

自平衡二分搜索树

func CreateAVLTree 

func CreateAVLTree(comparator func(thisValue interface{}, compareValue interface{}) int) *AVLTree

创建avl树

func (*AVLTree) Add 

func (tree *AVLTree) Add(key interface{}, value interface{})

O(h) 添加元素

func (AVLTree) Contains 

func (tree AVLTree) Contains(key interface{}) bool

O(h) 查询二分搜索树中是否包含某个元素

func (AVLTree) Get 

func (tree AVLTree) Get(key interface{}) interface{}

查询key对应的value

func (AVLTree) GetSize 

func (tree AVLTree) GetSize() int

O(1) 获取元素个数

func (AVLTree) InOrder 

func (tree AVLTree) InOrder(operatorFunc func(key interface{}, value interface{}) bool)

二分搜索树的中序遍历,中序遍历的结果是升序排序的

func (AVLTree) IsBSTTree 

func (tree AVLTree) IsBSTTree() bool

O(n) 检查当前节点是不是二分搜索树

func (AVLTree) IsBalanceTree 

func (tree AVLTree) IsBalanceTree() bool

O(n) 检查一颗树是不是平衡二叉树

func (AVLTree) IsEmpty 

func (tree AVLTree) IsEmpty() bool

O(1) 判断是否为空

func (AVLTree) LevelOrder 

func (tree AVLTree) LevelOrder(operatorFunc func(key interface{}, value interface{}) bool)

借助队列实现二分搜索树的层序遍历

func (AVLTree) Maximum 

func (tree AVLTree) Maximum() (interface{}, interface{}, error)

O(h) 查找最小的元素

func (AVLTree) Minimum 

func (tree AVLTree) Minimum() (interface{}, interface{}, error)

O(h) 查找二分搜索树中最小的元素

func (AVLTree) PostOrder 

func (tree AVLTree) PostOrder(operatorFunc func(key interface{}, value interface{}) bool)

二分搜索树的后序遍历

func (AVLTree) PreOrder 

func (tree AVLTree) PreOrder(operatorFunc func(key interface{}, value interface{}) bool)

前序遍历,进行一些操作

func (AVLTree) PreOrderNR 

func (tree AVLTree) PreOrderNR(operatorFunc func(key interface{}, value interface{}) bool)

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

func (*AVLTree) RemoveElement 

func (tree *AVLTree) RemoveElement(key interface{}) (interface{}, error)

O(h) 删除二分搜索树中任意节点

func (*AVLTree) RemoveMaximum 

func (tree *AVLTree) RemoveMaximum() (interface{}, interface{}, error)

O(h) 删除二分搜索树的最大的节点

func (*AVLTree) RemoveMinimum 

func (tree *AVLTree) RemoveMinimum() (interface{}, interface{}, error)

O(h) 删除二分搜索树的最小的节点

func (AVLTree) String 

func (tree AVLTree) String() string

type ArraySegmentTree 

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

线段树(区间树) 解决对固定个数的元素,指定区间进行查询问题 此线段树用于计算[i,j]区间内元素的和

func CreateArraySegmentTree 

func CreateArraySegmentTree(slice array.Array, aggregator func(leftChildValue interface{}, rightChildValue interface{}) interface{}) *ArraySegmentTree

创建一个线段树

func (ArraySegmentTree) GetSize 

func (tree ArraySegmentTree) GetSize() int

获取线段树区间大小

func (ArraySegmentTree) Query 

func (tree ArraySegmentTree) Query(queryL int, queryR int) (interface{}, error)

O(log(n)) 对区间[l,r]进行查询

func (*ArraySegmentTree) Set 

func (tree *ArraySegmentTree) Set(i int, value interface{}) error

O(log(n)) 更新数组中的值

func (ArraySegmentTree) String 

func (tree ArraySegmentTree) String() string

type BsTree 

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

二分搜索树

func CreateBstTree 

func CreateBstTree(comparator func(thisValue interface{}, compareValue interface{}) int) *BsTree

创建二分搜索树

func (*BsTree) Add 

func (tree *BsTree) Add(key interface{}, value interface{})

O(h) 添加元素

func (BsTree) Contains 

func (tree BsTree) Contains(key interface{}) bool

O(h) 查询二分搜索树中是否包含某个元素

func (BsTree) Get 

func (tree BsTree) Get(key interface{}) interface{}

查询key对应的value

func (BsTree) GetSize 

func (tree BsTree) GetSize() int

O(1) 获取元素个数

func (BsTree) InOrder 

func (tree BsTree) InOrder(operatorFunc func(key interface{}, value interface{}) bool)

二分搜索树的中序遍历,中序遍历的结果是升序排序的

func (BsTree) IsEmpty 

func (tree BsTree) IsEmpty() bool

O(1) 判断是否为空

func (BsTree) LevelOrder 

func (tree BsTree) LevelOrder(operatorFunc func(key interface{}, value interface{}) bool)

借助队列实现二分搜索树的层序遍历

func (BsTree) MaxDepth 

func (tree BsTree) MaxDepth() int

获取树的最大高度

func (BsTree) Maximum 

func (tree BsTree) Maximum() (interface{}, interface{}, error)

O(h) 查找最小的元素

func (BsTree) Minimum 

func (tree BsTree) Minimum() (interface{}, interface{}, error)

O(h) 查找二分搜索树中最小的元素

func (BsTree) PostOrder 

func (tree BsTree) PostOrder(operatorFunc func(key interface{}, value interface{}) bool)

二分搜索树的后序遍历

func (BsTree) PreOrder 

func (tree BsTree) PreOrder(operatorFunc func(key interface{}, value interface{}) bool)

前序遍历,进行一些操作

func (BsTree) PreOrderNR 

func (tree BsTree) PreOrderNR(operatorFunc func(key interface{}, value interface{}) bool)

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

func (*BsTree) RemoveElement 

func (tree *BsTree) RemoveElement(key interface{}) (interface{}, error)

O(h) 删除二分搜索树中任意节点

func (*BsTree) RemoveMaximum 

func (tree *BsTree) RemoveMaximum() (interface{}, interface{}, error)

O(h) 删除二分搜索树的最大的节点

func (*BsTree) RemoveMinimum 

func (tree *BsTree) RemoveMinimum() (interface{}, interface{}, error)

O(h) 删除二分搜索树的最小的节点

func (BsTree) String 

func (tree BsTree) String() string

type BstIsEmptyError 

type BstIsEmptyError struct {
}

func (BstIsEmptyError) Error 

func (BstIsEmptyError) Error() string

type QuickUnionFind 

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

快速合并和查询 使用一种数组表示的森林来实现并查集. 1.相同集合的元素所属同一个根 2.合并元素的时候将一个元素所属集合的根节点修改为另一个元素所属集合的根

func CreateQuickUnionFind 

func CreateQuickUnionFind(size int) *QuickUnionFind

创建大小为size的快速合并和查询的并查集

func (QuickUnionFind) GetSetNum 

func (uf QuickUnionFind) GetSetNum() int

获取集合数量

func (QuickUnionFind) GetSize 

func (uf QuickUnionFind) GetSize() int

func (QuickUnionFind) IsConnected 

func (uf QuickUnionFind) IsConnected(p int, q int) bool

O(h) h为树的高度 查询两个节点是否连接

func (*QuickUnionFind) UnionElements 

func (uf *QuickUnionFind) UnionElements(p int, q int) error

O(h) h为树的高度 将两个元素所在的集合合并成一个集合

type RBTIsEmptyError 

type RBTIsEmptyError struct {
}

func (RBTIsEmptyError) Error 

func (RBTIsEmptyError) Error() string

type RedBlackTree 

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

红黑树

func CreateRedBlackTree 

func CreateRedBlackTree(comparator func(thisValue interface{}, compareValue interface{}) int) *RedBlackTree

创建redBlack树

func (*RedBlackTree) Add 

func (tree *RedBlackTree) Add(key interface{}, value interface{})

O(h) 添加元素

func (RedBlackTree) Contains 

func (tree RedBlackTree) Contains(key interface{}) bool

O(h) 查询二分搜索树中是否包含某个元素

func (RedBlackTree) Get 

func (tree RedBlackTree) Get(key interface{}) interface{}

查询key对应的value

func (RedBlackTree) GetSize 

func (tree RedBlackTree) GetSize() int

O(1) 获取元素个数

func (RedBlackTree) InOrder 

func (tree RedBlackTree) InOrder(operatorFunc func(key interface{}, value interface{}) bool)

二分搜索树的中序遍历,中序遍历的结果是升序排序的

func (RedBlackTree) IsEmpty 

func (tree RedBlackTree) IsEmpty() bool

O(1) 判断是否为空

func (RedBlackTree) LevelOrder 

func (tree RedBlackTree) LevelOrder(operatorFunc func(key interface{}, value interface{}) bool)

借助队列实现二分搜索树的层序遍历

func (RedBlackTree) MaxDepth 

func (tree RedBlackTree) MaxDepth() int

获取树的最大高度

func (RedBlackTree) Maximum 

func (tree RedBlackTree) Maximum() (interface{}, interface{}, error)

O(h) 查找最小的元素

func (RedBlackTree) Minimum 

func (tree RedBlackTree) Minimum() (interface{}, interface{}, error)

O(h) 查找二分搜索树中最小的元素

func (RedBlackTree) PostOrder 

func (tree RedBlackTree) PostOrder(operatorFunc func(key interface{}, value interface{}) bool)

二分搜索树的后序遍历

func (RedBlackTree) PreOrder 

func (tree RedBlackTree) PreOrder(operatorFunc func(key interface{}, value interface{}) bool)

前序遍历,进行一些操作

func (RedBlackTree) PreOrderNR 

func (tree RedBlackTree) PreOrderNR(operatorFunc func(key interface{}, value interface{}) bool)

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

func (*RedBlackTree) RemoveElement 

func (tree *RedBlackTree) RemoveElement(key interface{}) (interface{}, error)

O(h) 删除二分搜索树中任意节点

func (*RedBlackTree) RemoveMaximum 

func (tree *RedBlackTree) RemoveMaximum() (interface{}, interface{}, error)

O(h) 删除二分搜索树的最大的节点

func (*RedBlackTree) RemoveMinimum 

func (tree *RedBlackTree) RemoveMinimum() (interface{}, interface{}, error)

O(h) 删除二分搜索树的最小的节点

func (RedBlackTree) String 

func (tree RedBlackTree) String() string

type SegmentTree 

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

func CreateSegmentTree 

func CreateSegmentTree(slice array.Array, aggregator func(leftChildValue interface{}, rightChildValue interface{}) interface{}) *SegmentTree

创建一个动态线段树

func (SegmentTree) GetSize 

func (tree SegmentTree) GetSize() int

获取线段树区间大小

func (SegmentTree) Query 

func (tree SegmentTree) Query(queryL int, queryR int) (interface{}, error)

O(log(n)) 对区间[l,r]进行查询

func (*SegmentTree) Set 

func (tree *SegmentTree) Set(i int, value interface{}) error

O(log(n)) 更新线段树原数组中的值

func (SegmentTree) String 

func (tree SegmentTree) String() string

type SplayIsEmptyError 

type SplayIsEmptyError struct {
}

func (SplayIsEmptyError) Error 

func (SplayIsEmptyError) Error() string

type SplayNode 

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

伸展树:伸展树也是二分搜索树 二分搜索树是二叉树,因为其中序列遍历的有序性也称二分搜索树为排序树

二分搜索树的每隔节点的值: 

大于其左子节点的所有节点的值
小于其右子节点的所有节点的值

为了满足此特性,二分搜索树中不允许有相等的元素

每一棵子树也是二分搜索树

存入二分搜索树中的节点必须是可以比较的,想要存入基础类型就必须给基础类型实现 

common.CompareAble接口

type SplayTree 

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

伸展树: 伸展树的特性是将最近集中访问的元素移动到树的头部.虽然curd的均摊时间复杂度是O(n)的.

func CreateSplayTree 

func CreateSplayTree(comparator func(thisValue interface{}, compareValue interface{}) int) *SplayTree

创建伸展树

func (*SplayTree) Add 

func (tree *SplayTree) Add(key interface{}, value interface{})

O(h) 添加元素

func (*SplayTree) Contains 

func (tree *SplayTree) Contains(key interface{}) bool

O(h) 查询二分搜索树中是否包含某个元素

func (*SplayTree) Get 

func (tree *SplayTree) Get(key interface{}) interface{}

查询key对应的value,在get的过程中重新连接节点,以便加入二层伸展操作

func (SplayTree) GetSize 

func (tree SplayTree) GetSize() int

O(1) 获取元素个数

func (SplayTree) InOrder 

func (tree SplayTree) InOrder(operatorFunc func(key interface{}, value interface{}) bool)

二分搜索树的中序遍历,中序遍历的结果是升序排序的

func (SplayTree) IsEmpty 

func (tree SplayTree) IsEmpty() bool

O(1) 判断是否为空

func (SplayTree) LevelOrder 

func (tree SplayTree) LevelOrder(operatorFunc func(key interface{}, value interface{}) bool)

借助队列实现二分搜索树的层序遍历

func (SplayTree) MaxDepth 

func (tree SplayTree) MaxDepth() int

获取树的最大高度

func (SplayTree) Maximum 

func (tree SplayTree) Maximum() (interface{}, interface{}, error)

O(h) 查找最小的元素

func (SplayTree) Minimum 

func (tree SplayTree) Minimum() (interface{}, interface{}, error)

O(h) 查找二分搜索树中最小的元素

func (SplayTree) PostOrder 

func (tree SplayTree) PostOrder(operatorFunc func(key interface{}, value interface{}) bool)

二分搜索树的后序遍历

func (SplayTree) PreOrder 

func (tree SplayTree) PreOrder(operatorFunc func(key interface{}, value interface{}) bool)

前序遍历,进行一些操作

func (SplayTree) PreOrderNR 

func (tree SplayTree) PreOrderNR(operatorFunc func(key interface{}, value interface{}) bool)

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

func (*SplayTree) RemoveElement 

func (tree *SplayTree) RemoveElement(key interface{}) (interface{}, error)

O(h) 删除二分搜索树中任意节点,删除节点的时候进行伸展操作主要是为了压缩树的高度

func (*SplayTree) RemoveMaximum 

func (tree *SplayTree) RemoveMaximum() (interface{}, interface{}, error)

O(h) 删除二分搜索树的最大的节点

func (*SplayTree) RemoveMinimum 

func (tree *SplayTree) RemoveMinimum() (interface{}, interface{}, error)

O(h) 删除二分搜索树的最小的节点

func (SplayTree) String 

func (tree SplayTree) String() string

type Trie 

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

func CreateTrie 

func CreateTrie() *Trie

创建字典树

func (*Trie) Add 

func (trie *Trie) Add(word string)

O(len(word)) 向字典树中添加单词

func (Trie) Contains 

func (trie Trie) Contains(word string) bool

O(len(word)) 查询字典树中是否包含某个单词

func (Trie) GetSize 

func (trie Trie) GetSize() int

获取字典树中单词的数量

func (Trie) IsPrefix 

func (trie Trie) IsPrefix(prefix string) bool

O(len(word)) 查询字典树中是否包含某个字符串开头的字符串

func (Trie) Match 

func (trie Trie) Match(word string) bool

.过多的时候时效性无法保证 模糊搜索字符串,可以使用.表示所有与字符.

func (Trie) PrefixWords 

func (trie Trie) PrefixWords(prefix string) []string

满足前缀的单词过多的时候,无法保证较高的效率 返回所有以某个前缀开头的单词

type UF 

type UF interface {
	GetSize() int

	IsConnected(p int, q int) bool

	UnionElements(p int, q int) error
}

并查集

type UnionQuickFind 

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

并查集的实现 基于数组实现的并查集,支持快速查询 使用数组的索引表示元素,数组的值表示元素所属的集合id

func CreateUnionQuickFind 

func CreateUnionQuickFind(size int) *UnionQuickFind

创建大小为size的并查集合

func (UnionQuickFind) GetSize 

func (u UnionQuickFind) GetSize() int

func (UnionQuickFind) IsConnected 

func (u UnionQuickFind) IsConnected(p int, q int) bool

O(1) 检查数组索引代表的元素是否连通

func (*UnionQuickFind) UnionElements 

func (u *UnionQuickFind) UnionElements(p int, q int) error

O(n) 将索引所代表的元素合并到一个集合 将p和q索引所属的集合的元素都合并到一个集合中

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.