-
Notifications
You must be signed in to change notification settings - Fork 13
/
check.go
61 lines (55 loc) · 1.26 KB
/
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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
// SPDX-License-Identifier: ISC
// Copyright (c) 2014-2019 Bitmark Inc.
// Use of this source code is governed by an ISC
// license that can be found in the LICENSE file.
package avl
import (
"fmt"
)
// CheckUp - check the up pointers for consistency
func (tree *Tree) CheckUp() bool {
return checkUp(tree.root, nil)
}
// internal: consistency checker
func checkUp(p *Node, up *Node) bool {
if nil == p {
return true
}
if p.up != up {
fmt.Printf("fail at node: %v actual: %v expected: %v\n", p.key, p.up.key, up.key)
return false
}
if !checkUp(p.left, p) {
return false
}
return checkUp(p.right, p)
}
// CheckCounts - check left and right node counts are ok
func (tree *Tree) CheckCounts() bool {
b, _ := checkCounts(tree.root)
return b
}
func checkCounts(p *Node) (bool, int) {
if nil == p {
return true, 0
}
bl := true
nl := 0
if nil != p.left {
bl, nl = checkCounts(p.left)
if p.leftNodes != nl {
fmt.Printf("fail at node: %v left actual: %d record: %d\n", p.key, nl, p.leftNodes)
bl = false
}
}
br := true
nr := 0
if nil != p.right {
br, nr = checkCounts(p.right)
if p.rightNodes != nr {
fmt.Printf("fail at node: %v right actual: %d record: %d\n", p.key, nr, p.rightNodes)
br = false
}
}
return bl && br, 1 + nl + nr
}