-
Notifications
You must be signed in to change notification settings - Fork 16
/
deno_red_black_tree.deno.txt
111 lines (86 loc) · 5.75 KB
/
deno_red_black_tree.deno.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
DENO_RED_BLACK_TREE
VERSION ==> #Part of Deno
#Browser compatible
/=+===============================+=\
/ : : \
)==: BINARY SEARCH TREE :==(
\ :_______________________________: /
\=+===============================+=/
std/collections/
binary_search_tree.ts
BinarySearchTree.from(ARRAYLIKE #Same as new BinarySearchTree() + multiple insert(VAL)
|ITERABLE|BINARY_SEARCH_TREE #OPTS:
[, OPTS])->BINARY_SEARCH_TREE2 # - compare FUNC: like new BinarySearchTree(FUNC)
# - map(VAL, INDEX)->VAL: map values
new BinarySearchTree([FUNC]) #Binary search tree
#Left child < parent < right child
#No self-balancing
#FUNC(VAL, VAL2)->-1|0|1
# - defines order
# - also defines equality, e.g. for find()
# - can be descend (>) or ascend (def, <)
BINARY_SEARCH_TREE.insert(VAL) #Add a new node
->BOOL #Return false when VAL already present
BINARY_SEARCH_TREE.remove(VAL)
->BOOL #Return false when VAL not present
BINARY_SEARCH_TREE.find(VAL)
->VAL|null #
BINARY_SEARCH_TREE.min|max(VAL) #Find leftmost|rightmost VAL
->VAL|null #Return null if no values
BINARY_SEARCH_TREE
[Symbol.iterator]()
BINARY_SEARCH_TREE.lnrValues()
->ITERABLETOR #Iterate in LNR order (in-order)
BINARY_SEARCH_TREE.nlrValues()
->ITERABLETOR #Iterate in NLR order (pre-order)
BINARY_SEARCH_TREE.lrnValues()
->ITERABLETOR #Iterate in LRN order (post-order)
BINARY_SEARCH_TREE.rnlValues()
->ITERABLETOR #Iterate in RNL order (reverse in-order)
BINARY_SEARCH_TREE.lvlValues()
->ITERABLETOR #Iterate in level order (BFS)
BINARY_SEARCH_TREE.size #NUM of values
BINARY_SEARCH_TREE.clear() #Remove all values
BINARY_SEARCH_TREE.isEmpty()->BOOL#
/=+===============================+=\
/ : : \
)==: BINARY SEARCH NODE :==(
\ :_______________________________: /
\=+===============================+=/
std/collections/
binary_search_node.ts
new BinarySearchNode #Node of a BINARY_SEARCH_TREE
(BINARY_SEARCH_NODE|null, VAL) #First argument is parent (null if root)
BinarySearchNode
.from(BINARY_SEARCH_NODE)
->BINARY_SEARCH_NODE2 #Clone
BINARY_SEARCH_NODE.left|right #BINARY_SEARCH_NODE2 or null (def)
#null by default, i.e. does not implement how to add nodes or balance the tree
BINARY_SEARCH_NODE #Whether node is the STR ('left|right') child
.directionFromParent()->STR|null #null if root
BINARY_SEARCH_NODE
.findMin|MaxNode()
->BINARY_SEARCH_NODE #Find lestmost|rightmost child
BINARY_SEARCH_NODE
.findSuccessorNode()
->BINARY_SEARCH_NODE|null #Find next node in order
/=+===============================+=\
/ : : \
)==: RED BLACK TREE :==(
\ :_______________________________: /
\=+===============================+=/
std/collections/red_black_tree.ts
new RedBlackTree([FUNC]) #Like BinarySearchTree but as a red-black tree, i.e. self-balancing
#Same methods
/=+===============================+=\
/ : : \
)==: RED BLACK NODE :==(
\ :_______________________________: /
\=+===============================+=/
std/collections/red_black_nodea.ts
new RedBlackNode #Like BinarySearchNode but for a RED_BLACK_TREE
(BINARY_SEARCH_NODE|null, VAL) #Same methods, except following ones
RED_BLACK_NODE.parent #RED_BLACK_NODE|null
RED_BLACK_NODE.red #BOOL