blob: c318dc5b9f56e4c38eaf28348286e3d8a282f7a3 (
plain)
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
112
113
114
115
116
117
118
119
120
121
122
123
124
125
|
// AVL Tree Example
Node `alias Nullable[Table[Node left; Node right; I64 height; Any key; Any value]]
Avl_Compare_Fn `alias Fn[Result[I64 value; Error error]; Any key_a; Any key_b]
AVL `alias Table[Node root; U64 size; Avl_Compare_Fn compare_fn]
height : `{[Node node] ? node {[node] node.height } { 0 } }
max : `{[I64 a; I64 b] ? a > b { a } { b } }
get_balance : `{[Node n]
? n {
- (height `sync n.left; height `sync n.right)
} {
0
}
}
min_value_node : `{[Node n]
@ n.left { n : n.left }
n
}
new_node : `{[Any key; Any value]
Node (.left `null; .right `null; .height 1; .key key; .value value)
}
right_rotate : `{[Node y]
? !y { `return `null }
x : y.left;
t2 : x.right;
y.height : 1 + max `sync (height `sync y.left; height `sync y.right)
x.height : 1 + max `sync (height `sync x.left; height `sync x.right)
x
}
left_rotate : `{[Node x]
? !x { `return `null }
y : x.right;
t2 : y.left;
x.height : 1 + max `sync (height `sync x.left; height `sync x.right)
y.height : 1 + max `sync (height `sync y.left; height `sync y.right)
y
}
`export avl_init : `{[Avl_Compare_Fn compare_fn]
AVL (.root `null; .size 0; .compare_fn compare_fn)
}
`export avl_insert : `{[AVL avl; Any key; Any value]
insert : `{[Node n]
? !n {
avl.size +: 1
`return new_node `sync (key; value)
}
cmp : avl.compare_fn `sync (n.key; key)
? {
cmp < 0 { n.left : insert `sync n.left }
cmp > 0 { n.right : insert `sync n.right }
{
n.value : value
`return n
}
}
n.height : 1 + max `sync (height `sync n.left; height `sync n.right)
balance : get_balance `sync n
? {
& (balance > 1; cmp < 0) { right_rotate `sync n }
& (balance < -1; cmp > 0) { left_rotate `sync n }
& (balance > 1; cmp > 0) {
n.left : left_rotate `sync n.left
right_rotate `sync n
}
& (balance < -1; cmp < 0) {
n.right : right_rotate `sync n.right
left_rotate `sync n
}
{ n }
}
}
avl.root : insert `sync avl.root
Void
}
`export avl_delete : `{[Avl avl; Any key]
delete : `{[Node n; Any key]
? !n { `return n }
cmp : avl.compare_fn `sync (n.key; key)
? {
cmp < 0 { n.left : delete `sync (n.left; key)
cmp > 0 { n.right : delete `sync (n.right; key)
{
? | (!n.left; !n.right) {
n : ? n.left { n.left } { n.right }
} {
tmp : min_value_node `sync n.right
n.key : tmp.key
n.value : tmp.value
n.right : delete `sync (n.right; tmp.key)
}
}
}
? !n { `return n }
n.height : 1 + max `sync (height `sync n.left; height `sync n.right)
balance : get_balance `sync n
? {
& (balance > 1; 0 <= get_balance `sync n.left) { right_rotate `sync n }
& (balance > 1; 0 > get_balance `sync n.left {
n.left : left_rotate `sync n.left
right_rotate `sync n
}
& (balance < -1; 0 >= get_balance `sync n.right) { left_rotate `sync n }
& (balance < -1; 0 > get_balance `sync n.right) {
n.right : right_rotate `sync n.right
left_rotate `sync n
}
{ n }
}
}
avl.root : delete `sync (avl.root; key)
Void
}
|
