jstructures 0.8.2 | Documentation

jstructures

0.8.2

AVL ▸
- Static members
- .balanced
- .AVLBalanced
- .balFac
- .height
- Instance members
- #insert
- #remove
BST ▸
- Static members
- .removeAt
- .searchIn
- Instance members
- #search
- #insert
- #remove
BinNode ▸
- Static members
- .travLevel
- .travPre
- .travIn
- .travPost
- .swap
- Instance members
- #data
- #parent
- #lc
- #rc
- #height
- #size
- #isRoot
- #isLChild
- #isRChild
- #hasParent
- #hasLChild
- #hasRChild
- #hasChild
- #hasBothChild
- #isLeaf
- #sibling
- #uncle
- #fromParentTo
- #pred
- #succ
- #insertAsLC
- #insertAsRC
BinTree ▸
- Instance members
- #size
- #size
- #empty
- #root
- #root
- #updateHeightAbove
- #insertAsRoot
- #insertAsLC
- #insertAsRC
- #attachAsLC
- #attachAsRC
- #remove
- #secede
- #travLevel
- #travPre
- #travIn
- #travPost
Heap ▸
- Instance members
- #size
- #percolateUp
- #percolateDown
- #insert
- #getMax
- #delMax
properParent
ListNode ▸
- Instance members
- #insertAsSucc
- #insertAsPred
List ▸
- Instance members
- #size
- #first
- #last
- #insertAsFirst
- #insertAsLast
- #insertA
- #insertB
- #remove
- #disordered
- #findElem
- #search
- #deduplicate
- #uniquify
- #traverse
- #valid
- #selectMax
- #insertionSort
- #selectionSort
- #merge
- #mergeSort
Queue ▸
- Instance members
- #enqueue
- #dequeue
- #front
- #empty
- #size
SegmentTree ▸
- Instance members
- #size
- #leftChild
- #rightChild
- #build
- #query
- #update
Stack ▸
- Instance members
- #push
- #pop
- #top
- #empty
- #size
Trie ▸
- Instance members
- #size
- #root
- #insert
- #find
UnionFind ▸
- Instance members
- #find
- #union
- #isConnected
- #toString
Vector ▸
- Static members
- .binSearch
- .bubbleSort
- .merge
- .mergeSort
- Instance members
- #size
- #insert
- #removeRange
- #remove
- #disordered
- #findElem
- #search
- #deduplicate
- #uniquify
- #traverse

Need help reading this?

AVL

AVL 类(AVL 树, 继承自 BST)

new AVL(): AVL

Extends BST

Returns

AVL: Instance

Static Members

▸ balanced(x, 要判断的节点)

判断某个节点是否理想平衡即：左右高度相等

balanced(x: any, 要判断的节点: BinNode): Boolean

Parameters

x (any)

要判断的节点 (BinNode)

Returns

Boolean:

▸ AVLBalanced(x, 要判断的节点)

判断某个节点是否AVL平衡即：-2<左高度-右高度<2

AVLBalanced(x: any, 要判断的节点: BinNode): Boolean

Parameters

x (any)

要判断的节点 (BinNode)

Returns

Boolean:

▸ balFac(x, 要判断的节点)

获取节点的平衡因子 x.lc.height - x.rc.height;

balFac(x: any, 要判断的节点: BinNode): number

Parameters

x (any)

要判断的节点 (BinNode)

Returns

number: 左子树高度和右子树高度的差值

▸ height(x, 要判断的节点)

获取节点的高度

height(x: any, 要判断的节点: BinNode): number

Parameters

x (any)

要判断的节点 (BinNode)

Returns

number: 节点高度，空树高 -1，叶子高 0

Instance Members

▸ insert(e)

插入元素

insert(e: Anyone): BinNode

Parameters

e (Anyone) 要插入的数据元素

Returns

BinNode:

▸ remove(e)

删除元素, 注意是删除节点，非节点为根的子树

remove(e: Anyone): Boolean

Parameters

e (Anyone) 要插入的数据元素

Returns

Boolean: 是否成功删除

BST

BST 类(二叉搜索树类, 继承自 BinTree)

new BST(): BST

Extends BinTree

Returns

BST: Instance

Static Members

▸ removeAt(x)

删除某个节点

removeAt(x: BinNode): BinNode

Parameters

x (BinNode) 要删除的节点

Returns

BinNode: 返回接替者

▸ searchIn(v, e, parent, p)

以 v 为根节点查找元素 e 所在的节点

searchIn(v: BinNode, e: Anyone, parent: any, p: BinNode): [BinNode]

Parameters

v (BinNode) 要搜索的树的根节点

e (Anyone) 要搜索的元素

parent (any)

p (BinNode) 当前搜索节点的父节点

Returns

[BinNode]: 返回两项，第一项是搜索命中的节点，第二项是命中节点的父节点

Instance Members

▸ search(e)

查找元素 e 所在的节点

search(e: Anyone): [BinNode]

Parameters

e (Anyone) 要搜索的元素

Returns

[BinNode]: 返回两项，第一项是搜索命中的节点，第二项是命中节点的父节点

▸ insert(e)

插入元素

insert(e: Anyone): BinNode

Parameters

e (Anyone) 要插入的数据元素

Returns

BinNode:

▸ remove(e)

删除元素, 注意是删除节点，非节点为根的子树

remove(e: Anyone): Boolean

Parameters

e (Anyone) 要插入的数据元素

Returns

Boolean: 是否成功删除

BinNode

BinNode 类(二叉树节点类)

new BinNode(e: Anyone, parent: BinNode, lc: BinNode, rc: BinNode): BinNode

Parameters

(Anyone
            = null)

parent

(BinNode
            = null)

父节点

(BinNode
            = null)

左子节点

(BinNode
            = null)

右子节点

Returns

BinNode: Instance

Static Members

▸ travLevel(p, visit, 访问函数)

当前节点作为根节点的子树层次遍历 BFS

travLevel(p: any, visit: any, 访问函数: function): void

Parameters

p (any)

visit (any)

访问函数 (function)

Returns

void:

▸ travPre(p, visit, 访问函数)

当前节点作为根节点的子树前序遍历 DFS

travPre(p: BinNode, visit: any, 访问函数: function): void

Parameters

p (BinNode) 遍历的节点

visit (any)

访问函数 (function)

Returns

void:

▸ travIn(p, visit, 访问函数)

当前节点作为根节点的子树中序遍历 DFS

travIn(p: BinNode, visit: any, 访问函数: function): void

Parameters

p (BinNode) 遍历的节点

visit (any)

访问函数 (function)

Returns

void:

▸ travPost(p, visit, 访问函数)

当前节点作为根节点的子树后序遍历 DFS

travPost(p: BinNode, visit: any, 访问函数: function): void

Parameters

p (BinNode) 遍历的节点

visit (any)

访问函数 (function)

Returns

void:

▸ swap(node1, node2)

交换量几个节点的数据

swap(node1: BinNode, node2: BinNode): void

Parameters

node1 (BinNode) 要交换的节点1

node2 (BinNode) 要交换的节点2

Returns

void:

Instance Members

▸ data

节点存储数据

data

▸ parent

父节点

parent

▸ lc

左子节点

▸ rc

右子节点

▸ height

以该节点为根的树高度

height

▸ size

节点为根的子树规模

size

Returns

Boolean:

▸ isRoot

判断是否是根节点

isRoot

Returns

Boolean:

▸ isLChild

判断是否是左子节点

isLChild

Returns

Boolean:

▸ isRChild

判断是否是右子节点

isRChild

Returns

Boolean:

▸ hasParent

判断是否有父节点

hasParent

Returns

Boolean:

▸ hasLChild

判断是有左子节点

hasLChild

Returns

Boolean:

▸ hasRChild

判断是有左子节点

hasRChild

Returns

Boolean:

▸ hasChild

判断是有子节点

hasChild

Returns

Boolean:

▸ hasBothChild

判断是有完整子节点 (即左右子节点都有)

hasBothChild

Returns

Boolean:

▸ isLeaf

判断是否是叶子节点(没有子节点)

isLeaf

Returns

Boolean:

▸ sibling

兄弟节点

sibling

Returns

BinNode:

▸ uncle

叔叔节点(即父节点的兄弟节点)

uncle

Returns

BinNode:

▸ fromParentTo

获取来自父节点的引用

fromParentTo

Returns

Array: [object, key]

▸ pred

获取中序遍历下的直接前驱

pred

Returns

BinNode: 返回前驱节点，不存在则返回 null

▸ succ

获取中序遍历下的直接后继

succ

Returns

BinNode: 返回后继节点，不存在则返回 null

▸ insertAsLC(e)

将元素作为左子节点插入

insertAsLC(e: Anyone): BinNode

Parameters

e (Anyone)

Returns

BinNode: 返回插入额节点

▸ insertAsRC(e)

将元素作为右子节点插入

insertAsRC(e: Anyone): BinNode

Parameters

e (Anyone)

Returns

BinNode: 返回插入额节点

BinTree

BinTree 类(二叉树类)

new BinTree(): BinTree

Returns

BinTree: Instance

Instance Members

▸ size

树的规模

size

Returns

number:

▸ size

更新树的规模

size

Parameters

num (any)

Returns

number:

▸ empty

树是否为空

empty

Returns

Boolean:

▸ root

树根节点

root

Returns

BinNode:

▸ root

重置根节点

root

Parameters

_root (any)

Returns

BinNode:

▸ updateHeightAbove(p)

更新节点以及祖先节点的高度

updateHeightAbove(p: BinNode): number

Parameters

p (BinNode) 要更新的节点

Returns

number: 返回更新后的高度

▸ insertAsRoot(e)

作为树根节点插入

insertAsRoot(e: Anyone): BinNode

Parameters

e (Anyone) 要插入的数据元素

Returns

BinNode:

▸ insertAsLC(p, e)

作为节点的左孩子插入

insertAsLC(p: BinNode, e: Anyone): BinNode

Parameters

p (BinNode) 要插入的位置

e (Anyone) 要插入的数据元素

Returns

BinNode:

▸ insertAsRC(p, e)

作为节点的右孩子插入

insertAsRC(p: BinNode, e: Anyone): BinNode

Parameters

p (BinNode) 要插入的位置

e (Anyone) 要插入的数据元素

Returns

BinNode:

▸ attachAsLC(p, s)

作为节点的左孩子接入子树

attachAsLC(p: BinNode, s: BinTree): BinNode

Parameters

p (BinNode) 要插入的位置

s (BinTree) 要接入的数

Returns

BinNode:

▸ attachAsRC(p, s)

作为节点的右孩子接入子树

attachAsRC(p: BinNode, s: BinTree): BinNode

Parameters

p (BinNode) 要插入的位置

s (BinTree) 要接入的数

Returns

BinNode:

▸ remove(p)

删除某个节点作为根的子树

remove(p: BinNode): number

Parameters

p (BinNode) 要删除的根节点

Returns

number: 返回删除节点的总个数

▸ secede(p)

分离某个节点作为根的子树

secede(p: BinNode): BinTree

Parameters

p (BinNode) 要删除的根节点

Returns

BinTree: 返回分离出来的子树

▸ travLevel(visit, 访问函数)

树的层次遍历

travLevel(visit: any, 访问函数: function): void

Parameters

visit (any)

访问函数 (function)

Returns

void:

▸ travPre(visit, 访问函数)

树的前序遍历

travPre(visit: any, 访问函数: function): void

Parameters

visit (any)

访问函数 (function)

Returns

void:

▸ travIn(visit, 访问函数)

树的中序遍历

travIn(visit: any, 访问函数: function): void

Parameters

visit (any)

访问函数 (function)

Returns

void:

▸ travPost(visit, 访问函数)

树的后序遍历

travPost(visit: any, 访问函数: function): void

Parameters

visit (any)

访问函数 (function)

Returns

void:

Heap

Heap 堆

new Heap(elems: any, length: any): Heap

Parameters

elems

(any
            = [])

length

(any
            = 0)

Returns

Heap: Instance

Instance Members

▸ size

获取堆的大小

size

Returns

number:

▸ percolateUp

元素上滤操作

percolateUp

Parameters

i (Number) 上滤的元素索引

Returns

Number: 上滤的终止位置

▸ percolateDown

元素下滤操作

percolateDown

Parameters

i (Number) 下滤的元素索引

Returns

Number: 下滤的终止位置

▸ insert(e)

e 元素插入

insert(e: Anyone): void

Parameters

e (Anyone)

Returns

void:

▸ getMax()

返回堆的最大元素

getMax(): Anyone

Returns

Anyone:

▸ delMax(e)

删除堆的最大元素

delMax(e: Anyone): void

Parameters

e (Anyone)

Returns

void:

properParent

得到父子三者（最多三个) 中的最大值

properParent

Parameters

n (any)

i (any)

ListNode

ListNode 类

new ListNode(e: Anyone?): ListNode

Parameters

e (Anyone?) 初始数组

Returns

ListNode: Instance

Instance Members

▸ insertAsSucc(e)

将元素 e 作为当前节点的直接后继插入

insertAsSucc(e: Anyone): ListNode

Parameters

e (Anyone)

Returns

ListNode:

▸ insertAsPred(e)

将元素 e 作为当前节点的直接前驱插入

insertAsPred(e: Anyone): ListNode

Parameters

e (Anyone)

Returns

ListNode:

List

Linked-list 类

new List(_elem: Array): List

Parameters

_elem (Array) 初始数组

Returns

List: Instance

Instance Members

▸ size

获取列表长度/大小

size

Returns

number:

▸ first

获取列表首节点

first

Returns

ListNode:

▸ last

获取列表末节点

last

Returns

ListNode:

▸ insertAsFirst(e)

将 e 作为首节点插入列表

insertAsFirst(e: Anyone): ListNode

Parameters

e (Anyone)

Returns

ListNode:

▸ insertAsLast(e)

将 e 作为末节点插入列表

insertAsLast(e: Anyone): ListNode

Parameters

e (Anyone)

Returns

ListNode:

▸ insertA(p, e)

e 作为节点 p 的直接后继插入

insertA(p: any, e: Anyone): number

Parameters

p (any)

e (Anyone)

Returns

number:

▸ insertB(p, e)

e 作为节点 p 的直接前驱插入

insertB(p: any, e: Anyone): number

Parameters

p (any)

e (Anyone)

Returns

number:

▸ remove(p)

删除指定节点 p

remove(p: number): Anyone

Parameters

p (number) 要删除元素

Returns

Anyone: e 删除的元素

▸ disordered()

返回列表中相邻元素逆序对总数, 当返回为0则代表列表有序

disordered(): Number

Returns

Number:

▸ findElem(e, n, p)

从节点p往前查找目标元素 e 所在最后节点, 最多查询 n 个

findElem(e: Anyone, n: number, p: ListNode): ListNode

Parameters

e (Anyone) 要搜索的元素

(number
            = this[size])

最大搜索次数

(ListNode
            = this[tailer])

从p节点往前查找, 默认为 tailer，查找全部

Returns

ListNode: 等于 e 的元素最后的节点

▸ search(e, n, p)

从节点p的n的真前驱中查找不大于 e 的最后者

search(e: Anyone, n: number, p: ListNode): ListNode

Parameters

e (Anyone) 要搜索的元素

(number
            = this[size])

最大搜索次数

(ListNode
            = this[tailer])

从p节点往前查找, 默认为 tailer，查找全部

Returns

ListNode: 等于 e 的元素最后的节点

▸ deduplicate()

剔除重复元素，保证每个元素都是唯一的

deduplicate(): number

Returns

number: 被删除的元素个数

▸ uniquify()

有序列表剔除重复元素，保证每个元素都是唯一的

uniquify(): number

Returns

number: 被删除的元素个数

▸ traverse(visit)

向量的遍历

traverse(visit: function): any

Parameters

visit (function) 访问函数

Returns

any: void

▸ valid(p)

判断节点是否合法，存在，且不是首尾哨兵

valid(p: ListNode): boolean

Parameters

p (ListNode)

Returns

boolean:

▸ selectMax(p, n)

从起始位置 p 的n个元素中找到最大者, 相同大小后者优先

selectMax(p: ListNode, n: number): ListNode

Parameters

(ListNode
            = this[header].succ)

排序起始节点

(number
            = this[size])

Returns

ListNode:

▸ insertionSort(p, n)

列表的插入排序, 对起始位置为 p 的 n 的元素进行排序

insertionSort(p: ListNode, n: number): ListNode

Parameters

(ListNode
            = this[header].succ)

排序起始节点

(number
            = this[size])

Returns

ListNode: 排序后的起始节点

▸ selectionSort(p, n)

列表的选择排序, 对起始位置为 p 的 n 的元素进行排序

selectionSort(p: ListNode, n: number): ListNode

Parameters

(ListNode
            = this[header].succ)

排序起始节点

(number
            = this[size])

Returns

ListNode: 排序后的起始节点

▸ merge(p, n, he, q, m)

列表的归并排序之归并, 对起始位置为 p 的 n 的元素进行排序

merge(p: ListNode, n: number, he: List, q: ListNode, m: number): ListNode

Parameters

p (ListNode) 合并起始节点

n (number)

he (List) 要合并的另外一个列表

q (ListNode) 合并的另外一个列表起始节点

m (number) 要合并的另外一个列表的节点数

Returns

ListNode: 归并后的起始节点

▸ mergeSort(p, n)

列表的归并排序, 对起始位置为 p 的 n 的元素进行排序

mergeSort(p: ListNode, n: number): ListNode

Parameters

(ListNode
            = this[header].succ)

排序起始节点

(number
            = this[size])

Returns

ListNode: 排序后的起始节点

Queue

Queue 类

new Queue(): Queue

Returns

Queue: Instance

Instance Members

▸ enqueue(e)

e 加入队列尾部(排队)

enqueue(e: Anyone): void

Parameters

e (Anyone)

Returns

void:

▸ dequeue()

将队首出队

dequeue(): Anyone

Returns

Anyone: e 之前压入的元素

▸ front

指向队首元素

front

Returns

Anyone: e 之前压入的元素

▸ empty

判断队列是否为空

empty

Returns

Boolean:

▸ size

当前队列列长度(规模)

size

Returns

number:

SegmentTree

Segment-tree 线段树(区间树)类

new SegmentTree(data: any, mergeFn: any, _elem: Array): List

Parameters

data (any)

mergeFn (any)

_elem (Array) 初始数组

Returns

List: Instance

Instance Members

▸ size

获取数据长度/大小

size

Returns

number:

▸ leftChild(index)

左节点的索引

leftChild(index: any): number

Parameters

index (any)

Returns

number:

▸ rightChild(index)

右节点的索引

rightChild(index: any): number

Parameters

index (any)

Returns

number:

▸ build(index, left, right)

构建线段树

build(index: any, left: any, right: any): void

Parameters

index (any)

left (any)

right (any)

Returns

void:

▸ query(qL, qR)

查询线段树的某一区间

query(qL: Number, qR: Number): Anyone

Parameters

qL (Number) 查询的区间开始值

qR (Number) 查询的区间结束值

Returns

Anyone:

▸ update(index, val)

更新某个值

update(index: Number, val: Anyone): void

Parameters

index (Number) 原数组的索引

val (Anyone) 修改后的值

Returns

void:

Stack

Stack 类

new Stack(): Stack

Returns

Stack: Instance

Instance Members

▸ push(e)

e 作为压入栈顶

push(e: Anyone): void

Parameters

e (Anyone)

Returns

void:

▸ pop()

将栈顶出栈

pop(): Anyone

Returns

Anyone: e 之前压入的元素

▸ top

指向栈顶元素，并不出栈

top

Returns

Anyone: e 之前压入的元素

▸ empty

判断栈是否为空

empty

Returns

Boolean:

▸ size

当前栈高度(规模)

size

Returns

Number:

Trie

new Trie(): Trie

Returns

Trie: Instance

Instance Members

▸ size

获取字典树的大小, 包含单词的数量

size

Returns

number:

▸ root

获取字典树的跟节点

root

Returns

number:

▸ insert(word)

插入 word

insert(word: String): void

Parameters

word (String) 要插入的单词

Returns

void:

▸ find(word)

查找 word

find(word: String): Boolean

Parameters

word (String) 要查找的单词

Returns

Boolean:

UnionFind

UnionFind 并查集类

new UnionFind(size: Number): UnionFind

Parameters

size (Number) 集合规模

Returns

UnionFind: Instance

Instance Members

▸ find(p)

查找p所属的集合编号

find(p: Number): Number

Parameters

p (Number)

Returns

Number:

▸ union(p, q)

链接两个元素

union(p: Number, q: Number): void

Parameters

p (Number)

q (Number)

Returns

void:

▸ isConnected(p, q)

判断两个元素是否相连

isConnected(p: Number, q: Number): Boolean

Parameters

p (Number)

q (Number)

Returns

Boolean:

▸ toString()

用来返回内部集合的情况

toString(): String

Returns

String:

Vector

new Vector(_elem: Array): Vector

Parameters

_elem

(Array
            = [])

初始数组

Returns

Vector: Instance

Static Members

▸ binSearch(_elem, e, lo, hi)

在有序向量的区间[lo, hi)查找元素不大于 e 的元素的最大秩, 0 <= lo <= hi <= size

binSearch(_elem: Vector, e: Anyone, lo: number, hi: number): number

Parameters

_elem (Vector) 要搜索的有序向量或有序数组

e (Anyone) 要搜索的元素

(number
            = 0)

要查找的起始秩

(number
            = _elem.length)

要查找的结束秩

Returns

number: 不大于 e 的元素最大的秩

▸ bubbleSort(_elem, lo, hi)

排序算法起泡排序, 具有稳定性

bubbleSort(_elem: Vector, lo: number, hi: number): void

Parameters

_elem (Vector) 要排序的向量或数据

(number
            = 0)

要查找的起始秩

(number
            = _elem.length)

要查找的结束秩

Returns

void:

▸ merge(_elem, lo, mi, hi)

排序算法归并排序之合并

merge(_elem: Vector, lo: number, mi: any, hi: number): void

Parameters

_elem (Vector) 要排序的向量或数据

lo (number) 要查找的起始秩

mi (any)

hi (number) 要查找的结束秩

Returns

void:

▸ mergeSort(_elem, lo, hi)

排序算法归并排序

mergeSort(_elem: Vector, lo: number, hi: number): void

Parameters

_elem (Vector) 要排序的向量或数据

(number
            = 0)

要查找的起始秩

(number
            = _elem.length)

要查找的结束秩

Returns

void:

Instance Members

▸ size

获取向量大小

size

Returns

number:

▸ insert(r, e)

e 作为秩为 r 的元素插入，原后继元素依次后移

insert(r: number, e: Anyone): number

Parameters

r (number) 插入新元素的秩 0 <= r <= size

e (Anyone)

Returns

number:

▸ removeRange(lo, hi)

删除指定区间的元素, 原后继元素依次前移[lo, hi)

removeRange(lo: number, hi: number): number

Parameters

lo (number) 要删除元素起始的秩 0 <= r <= size

hi (number) 要删除元素结束的秩 0 <= r <= size

Returns

number: 删除的元素数量

▸ remove(r)

删除指定秩的元素, 原后继元素依次前移

remove(r: number): Anyone

Parameters

r (number) 要删除元素的秩 0 <= r <= size

Returns

Anyone: e 删除的元素

▸ disordered()

返回向量中相邻元素逆序对总数, 当返回为0则代表向量有序

disordered(): Number

Returns

Number:

▸ findElem(e, lo, hi)

在向量的区间 [lo, hi)查找元素等于 e 的最大秩

findElem(e: Anyone, lo: number, hi: number): number

Parameters

e (Anyone) 要搜索的元素

(number
            = 0)

要查找的起始秩

(number
            = _elem.length)

要查找的结束秩

Returns

number: 等于 e 的元素最大的秩

▸ search(e, lo, hi)

在有序向量的区间[lo, hi)查找元素e 所在的秩, 0 <= lo <= hi <= size

search(e: Anyone, lo: number, hi: number): number

Parameters

e (Anyone) 要搜索的元素

lo (number) 要查找的起始秩

hi (number) 要查找的结束秩

Returns

number: 不大于 e 的元素最大的秩

▸ deduplicate()

剔除重复元素，保证每个元素都是唯一的

deduplicate(): number

Returns

number: 被删除的元素个数

▸ uniquify()

有序向量剔除重复元素，保证每个元素都是唯一的

uniquify(): number

Returns

number: 被删除的元素个数

▸ traverse(visit)

向量的遍历

traverse(visit: function): any

Parameters

visit (function) 访问函数

Returns

any: void