-
Notifications
You must be signed in to change notification settings - Fork 2
/
sup.go
41 lines (39 loc) · 870 Bytes
/
sup.go
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
package splaytree
// Supremum finds the smallest element greater than a given.
// Return the supremum if present, else nil.
func (tree *SplayTree) Supremum(item Item) Item {
if item == nil || tree.root == nil {
return nil
}
tree.splay(item)
if item.Less(tree.root.item) {
return tree.root.item
}
if tree.root.right != nil {
node := tree.root.right
for node.left != nil {
node = node.left
}
return node.item
}
return nil
}
// Infimum finds the largest element smaller than a given.
// Return the infimum if present, else nil.
func (tree *SplayTree) Infimum(item Item) Item {
if item == nil || tree.root == nil {
return nil
}
tree.splay(item)
if tree.root.item.Less(item) {
return tree.root.item
}
if tree.root.left != nil {
node := tree.root.left
for node.right != nil {
node = node.right
}
return node.item
}
return nil
}