JStructure

JavaScript 版本的数据结构，提供常用的数据结构封装，基于清华大学邓俊辉老师的数据结构课程

进度

• [x] List (linked-list)
• [x] Vector
• [x] Stack
• [x] Queue
• [x] SegmentTree
• [x] UnionFind
• [x] BinTree
  • [x] BST (BinanySearchTree)
  • [ ] BTree
• [x] Trie
• [ ] Graph
• [x] Heap
  • [ ] LeftHeap
• [ ] Priority Queue

Table of Contents

Table of Contents

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

AVL

Extends BST

AVL 类(AVL 树, 继承自 BST)

Returns AVL Instance

insert

插入元素

Parameters

• e Anyone 要插入的数据元素

Returns BinNode

remove

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

Parameters

• e Anyone 要插入的数据元素

Returns Boolean 是否成功删除

balanced

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

Parameters

• x
• 要判断的节点 BinNode

Returns Boolean

AVLBalanced

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

Parameters

• x
• 要判断的节点 BinNode

Returns Boolean

balFac

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

Parameters

• x
• 要判断的节点 BinNode

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

height

获取节点的高度

Parameters

• x
• 要判断的节点 BinNode

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

BST

Extends BinTree

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

Returns BST Instance

search

查找元素 e 所在的节点

Parameters

• e Anyone 要搜索的元素

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

insert

插入元素

Parameters

• e Anyone 要插入的数据元素

Returns BinNode

remove

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

Parameters

• e Anyone 要插入的数据元素

Returns Boolean 是否成功删除

removeAt

删除某个节点

Parameters

• x BinNode 要删除的节点

Returns BinNode 返回接替者

searchIn

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

Parameters

• v BinNode 要搜索的树的根节点
• e Anyone 要搜索的元素
• parent
• p BinNode 当前搜索节点的父节点

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

BinNode

BinNode 类(二叉树节点类)

Parameters

• e Anyone (optional, default null)
• parent BinNode 父节点 (optional, default null)
• lc BinNode 左子节点 (optional, default null)
• rc BinNode 右子节点 (optional, default null)

Returns BinNode Instance

data

节点存储数据

parent

父节点

lc

左子节点

rc

右子节点

height

以该节点为根的树高度

size

节点为根的子树规模

Returns Boolean

isRoot

判断是否是根节点

Returns Boolean

isLChild

判断是否是左子节点

Returns Boolean

isRChild

判断是否是右子节点

Returns Boolean

hasParent

判断是否有父节点

Returns Boolean

hasLChild

判断是有左子节点

Returns Boolean

hasRChild

判断是有左子节点

Returns Boolean

hasChild

判断是有子节点

Returns Boolean

hasBothChild

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

Returns Boolean

isLeaf

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

Returns Boolean

sibling

兄弟节点

Returns BinNode

uncle

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

Returns BinNode

fromParentTo

获取来自父节点的引用

Returns Array [object, key]

pred

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

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

succ

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

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

insertAsLC

将元素作为左子节点插入

Parameters

• e Anyone

Returns BinNode 返回插入额节点

insertAsRC

将元素作为右子节点插入

Parameters

• e Anyone

Returns BinNode 返回插入额节点

travLevel

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

Parameters

• p
• visit
• 访问函数 function

Returns void

travPre

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

Parameters

• p BinNode 遍历的节点
• visit
• 访问函数 function

Returns void

travIn

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

Parameters

• p BinNode 遍历的节点
• visit
• 访问函数 function

Returns void

travPost

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

Parameters

• p BinNode 遍历的节点
• visit
• 访问函数 function

Returns void

swap

交换量几个节点的数据

Parameters

• node1 BinNode 要交换的节点1
• node2 BinNode 要交换的节点2

Returns void

BinTree

BinTree 类(二叉树类)

Returns BinTree Instance

size

树的规模

Returns number

size

更新树的规模

Parameters

• num

Returns number

empty

树是否为空

Returns Boolean

root

树根节点

Returns BinNode

root

重置根节点

Parameters

• _root

Returns BinNode

updateHeightAbove

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

Parameters

• p BinNode 要更新的节点

Returns number 返回更新后的高度

insertAsRoot

作为树根节点插入

Parameters

• e Anyone 要插入的数据元素

Returns BinNode

insertAsLC

作为节点的左孩子插入

Parameters

• p BinNode 要插入的位置
• e Anyone 要插入的数据元素

Returns BinNode

insertAsRC

作为节点的右孩子插入

Parameters

• p BinNode 要插入的位置
• e Anyone 要插入的数据元素

Returns BinNode

attachAsLC

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

Parameters

• p BinNode 要插入的位置
• s BinTree 要接入的数

Returns BinNode

attachAsRC

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

Parameters

• p BinNode 要插入的位置
• s BinTree 要接入的数

Returns BinNode

remove

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

Parameters

• p BinNode 要删除的根节点

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

secede

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

Parameters

• p BinNode 要删除的根节点

Returns BinTree 返回分离出来的子树

travLevel

树的层次遍历

Parameters

• visit
• 访问函数 function

Returns void

travPre

树的前序遍历

Parameters

• visit
• 访问函数 function

Returns void

travIn

树的中序遍历

Parameters

• visit
• 访问函数 function

Returns void

travPost

树的后序遍历

Parameters

• visit
• 访问函数 function

Returns void

Heap

Heap 堆

Parameters

• elems (optional, default [])
• length (optional, default 0)

Returns Heap Instance

size

获取堆的大小

Returns number

percolateUp

元素上滤操作

Parameters

• i Number 上滤的元素索引

Returns Number 上滤的终止位置

percolateDown

元素下滤操作

Parameters

• i Number 下滤的元素索引

Returns Number 下滤的终止位置

insert

e 元素插入

Parameters

• e Anyone

Returns void

getMax

返回堆的最大元素

Returns Anyone

delMax

删除堆的最大元素

Parameters

• e Anyone

Returns void

properParent

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

Parameters

• n
• i

ListNode

ListNode 类

Parameters

• e Anyone? 初始数组

Returns ListNode Instance

insertAsSucc

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

Parameters

• e Anyone

Returns ListNode

insertAsPred

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

Parameters

• e Anyone

Returns ListNode

List

Linked-list 类

Parameters

• _elem Array 初始数组

Returns List Instance

size

获取列表长度/大小

Returns number

first

获取列表首节点

Returns ListNode

last

获取列表末节点

Returns ListNode

insertAsFirst

将 e 作为首节点插入列表

Parameters

• e Anyone

Returns ListNode

insertAsLast

将 e 作为末节点插入列表

Parameters

• e Anyone

Returns ListNode

insertA

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

Parameters

• p
• e Anyone

Returns number

insertB

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

Parameters

• p
• e Anyone

Returns number

remove

删除指定节点 p

Parameters

• p number 要删除元素

Returns Anyone e 删除的元素

disordered

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

Returns Number

findElem

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

Parameters

• e Anyone 要搜索的元素
• n number 最大搜索次数 (optional, default this[size])
• p ListNode 从p节点往前查找, 默认为 tailer，查找全部 (optional, default this[tailer])

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

search

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

Parameters

• e Anyone 要搜索的元素
• n number 最大搜索次数 (optional, default this[size])
• p ListNode 从p节点往前查找, 默认为 tailer，查找全部 (optional, default this[tailer])

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

deduplicate

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

Returns number 被删除的元素个数

uniquify

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

Returns number 被删除的元素个数

traverse

向量的遍历

Parameters

• visit function 访问函数

Returns any void

valid

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

Parameters

• p ListNode

Returns boolean

selectMax

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

Parameters

• p ListNode 排序起始节点 (optional, default this[header].succ)
• n number (optional, default this[size])

Returns ListNode

insertionSort

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

Parameters

• p ListNode 排序起始节点 (optional, default this[header].succ)
• n number (optional, default this[size])

Returns ListNode 排序后的起始节点

selectionSort

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

Parameters

• p ListNode 排序起始节点 (optional, default this[header].succ)
• n number (optional, default this[size])

Returns ListNode 排序后的起始节点

merge

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

Parameters

• p ListNode 合并起始节点
• n number
• he List 要合并的另外一个列表
• q ListNode 合并的另外一个列表起始节点
• m number 要合并的另外一个列表的节点数

Returns ListNode 归并后的起始节点

mergeSort

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

Parameters

• p ListNode 排序起始节点 (optional, default this[header].succ)
• n number (optional, default this[size])

Returns ListNode 排序后的起始节点

Queue

Queue 类

Returns Queue Instance

enqueue

e 加入队列尾部(排队)

Parameters

• e Anyone

Returns void

dequeue

将队首出队

Returns Anyone e 之前压入的元素

front

指向队首元素

Returns Anyone e 之前压入的元素

empty

判断队列是否为空

Returns Boolean

size

当前队列列长度(规模)

Returns number

SegmentTree

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

Parameters

• data
• mergeFn
• _elem Array 初始数组

Returns List Instance

size

获取数据长度/大小

Returns number

leftChild

左节点的索引

Parameters

• index

Returns number

rightChild

右节点的索引

Parameters

• index

Returns number

build

构建线段树

Parameters

• index
• left
• right

Returns void

query

查询线段树的某一区间

Parameters

• qL Number 查询的区间开始值
• qR Number 查询的区间结束值

Returns Anyone

update

更新某个值

Parameters

• index Number 原数组的索引
• val Anyone 修改后的值

Returns void

Stack

Stack 类

Returns Stack Instance

push

e 作为压入栈顶

Parameters

• e Anyone

Returns void

pop

将栈顶出栈

Returns Anyone e 之前压入的元素

top

指向栈顶元素，并不出栈

Returns Anyone e 之前压入的元素

empty

判断栈是否为空

Returns Boolean

size

当前栈高度(规模)

Returns Number

Trie

Returns Trie Instance

size

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

Returns number

root

获取字典树的跟节点

Returns number

insert

插入 word

Parameters

• word String 要插入的单词

Returns void

find

查找 word

Parameters

• word String 要查找的单词

Returns Boolean

UnionFind

UnionFind 并查集类

Parameters

• size Number 集合规模

Returns UnionFind Instance

find

查找p所属的集合编号

Parameters

• p Number

Returns Number

union

链接两个元素

Parameters

• p Number
• q Number

Returns void

isConnected

判断两个元素是否相连

Parameters

• p Number
• q Number

Returns Boolean

toString

用来返回内部集合的情况

Returns String

Vector

Parameters

• _elem Array 初始数组 (optional, default [])

Returns Vector Instance

size

获取向量大小

Returns number

insert

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

Parameters

• r number 插入新元素的秩 0 <= r <= size
• e Anyone

Returns number

removeRange

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

Parameters

• lo number 要删除元素起始的秩 0 <= r <= size
• hi number 要删除元素结束的秩 0 <= r <= size

Returns number 删除的元素数量

remove

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

Parameters

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

Returns Anyone e 删除的元素

disordered

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

Returns Number

findElem

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

Parameters

• e Anyone 要搜索的元素
• lo number 要查找的起始秩 (optional, default 0)
• hi number 要查找的结束秩 (optional, default _elem.length)

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

search

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

Parameters

• e Anyone 要搜索的元素
• lo number 要查找的起始秩
• hi number 要查找的结束秩

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

deduplicate

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

Returns number 被删除的元素个数

uniquify

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

Returns number 被删除的元素个数

traverse

向量的遍历

Parameters

• visit function 访问函数

Returns any void

binSearch

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

Parameters

• _elem Vector 要搜索的有序向量或有序数组
• e Anyone 要搜索的元素
• lo number 要查找的起始秩 (optional, default 0)
• hi number 要查找的结束秩 (optional, default _elem.length)

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

bubbleSort

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

Parameters

• _elem Vector 要排序的向量或数据
• lo number 要查找的起始秩 (optional, default 0)
• hi number 要查找的结束秩 (optional, default _elem.length)

Returns void

merge

排序算法 归并排序之合并

Parameters

• _elem Vector 要排序的向量或数据
• lo number 要查找的起始秩
• mi
• hi number 要查找的结束秩

Returns void

mergeSort

排序算法 归并排序

Parameters

• _elem Vector 要排序的向量或数据
• lo number 要查找的起始秩 (optional, default 0)
• hi number 要查找的结束秩 (optional, default _elem.length)

Returns void