-
Notifications
You must be signed in to change notification settings - Fork 2
/
check.go
38 lines (35 loc) · 880 Bytes
/
check.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
package splaytree
// Check verifies that the tree
// is a proper binary search tree.
func (tree *SplayTree) Check() {
if !tree.isBinarySearchTree() {
panic("IsBinarySearchTree failed")
}
}
// Return true if tree is a proper binary search tree.
func (tree *SplayTree) isBinarySearchTree() bool {
if tree.root == nil {
return true
}
min, max := tree.root.isBinarySearchTree()
return min != nil && max != nil
}
// Return the minimum and maximum element at this node.
func (node *node) isBinarySearchTree() (Item, Item) {
min, max := node.item, node.item
if node.left != nil {
lmin, lmax := node.left.isBinarySearchTree()
if lmax == nil || !lmax.Less(min) {
return nil, nil
}
min = lmin
}
if node.right != nil {
rmin, rmax := node.right.isBinarySearchTree()
if rmin == nil || !max.Less(rmin) {
return nil, nil
}
max = rmax
}
return min, max
}