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
|
use v6d;
###############################################################################
=begin comment
Perl Weekly Challenge 130, Task #2: Binary Search Tree
=end comment
###############################################################################
#--------------------------------------#
# Copyright © 2021 PerlMonk Athanasius #
#--------------------------------------#
#==============================================================================
=begin comment
The BinTree class below is adapted from class BinaryTree used in the solution
to Task #2 of the Perl Weekly Challenge 94.
The implementation of methods is-bst() and !isBST() is adapted from:
https://en.wikipedia.org/wiki/Binary_search_tree#Verification
=end comment
#==============================================================================
#==============================================================================
unit class BinTree;
#==============================================================================
#------------------------------------------------------------------------------
my class Node
#------------------------------------------------------------------------------
{
has Int $.value;
has Node $.parent is rw;
has Node $.left is rw;
has Node $.right is rw;
}
has Node $!root;
#------------------------------------------------------------------------------
submethod BUILD( Int:D :$value )
#------------------------------------------------------------------------------
{
$!root = Node.new( value => $value, parent => Nil,
left => Nil, right => Nil );
}
#------------------------------------------------------------------------------
method append-node( UInt:D $depth, UInt:D $sequence, Int:D $value --> Bool:D )
#------------------------------------------------------------------------------
{
my Node $parent = $!root;
my UInt $m = 2 ** $depth;
my UInt $seq = $sequence;
my UInt $level = $depth;
while $level > 1
{
$m = ($m / 2).Int;
if $seq < $m
{
$parent.left.defined or return False;
$parent = $parent.left;
}
else
{
$parent.right.defined or return False;
$parent = $parent.right;
$seq -= $m;
}
--$level;
}
my Node $new-node = Node.new( value => $value, parent => $parent,
left => Nil, right => Nil );
if $seq == 0
{
$parent.left = $new-node;
}
else
{
$parent.right = $new-node;
}
return True;
}
#------------------------------------------------------------------------------
method is-bst( --> Bool:D )
#------------------------------------------------------------------------------
{
return self!isBST( $!root, -Inf, +Inf );
}
subset Int-or-Inf where Int:D | -Inf | +Inf;
#------------------------------------------------------------------------------
method !isBST
(
Node $node,
Int-or-Inf:D $min,
Int-or-Inf:D $max
--> Bool:D
)
#------------------------------------------------------------------------------
{
return True if !$node.defined;
return False if $node.value < $min || $node.value > $max;
return self!isBST( $node.left, $min, $node.value - 1 ) &&
self!isBST( $node.right, $node.value + 1, $max );
}
##############################################################################
|
