04-02-2006, 10:27 PM
I've been looking at this code for 3 days. I've chased it through manually dozens of times and all my research says that it should work flawlessly, but it doesn't.
number.txt:
13
65607
2
4
6
7
3
5
18
1
14
6
200
100
123
143
164
It displayed the tree correctly until it has to triple promote. Here is the tree before hand:
. 4,7
. 2 6 18,200
1 3 5 6 14 100,123 65607
Then when i try to insert 143, nothing happens except I loose 100 from the three node that its in. leaving me with:
. 4,7
. 2 6 18,200
1 3 5 6 14 123 65607
[/code]
Code:
TYPE two3node
leftbranch as two3node ptr
midbranch as two3node ptr
rightbranch as two3node ptr
leftvalue as integer
rightvalue as integer
tempbranch as two3node ptr 'for adding and promoting
tempvalue as integer
parent as two3node ptr
END TYPE
TYPE two3tree
Root as two3node ptr
depth as integer
size as integer
END TYPE
Declare Function Newtwo3node Overload (Value as integer) as two3node ptr
Declare Function Newtwo3node (lvalue as integer, rvalue as integer) as two3node ptr
Declare Function Newtwo3node () as two3node ptr
Declare Function Newtwo3tree () as two3tree ptr
Declare Sub DisplayAll(tree as Two3Tree ptr)
Declare Sub displaynode (p as two3node ptr, x as integer, y as integer, level as integer)
Declare Sub AddValue(tree as two3tree ptr, value as integer)
Declare Sub AddNode (pp as two3node ptr, tree as two3tree ptr, pnode as two3node ptr)
Declare Sub Deletesubtree(node as two3node ptr)
Declare Sub DeleteTwo3Tree(tree as two3tree ptr)
Declare Sub cprint (x as integer, y as integer, text as string, colour as integer)
Declare Sub display2node(x as integer, y as integer, node as two3node ptr)
Declare Sub display3node(x as integer, y as integer, node as two3node ptr)
Declare Function findrightleaf (tree as two3tree ptr, value as integer) as two3node ptr
Declare Sub sort(p as two3node ptr)
Declare Sub Inserttotemp (src as two3node ptr, dest as two3node ptr)
Declare Function greatestvalue (p as two3node ptr)
Dim shared twonodedisplay as integer ptr
dim shared threenodedisplay as integer ptr
dim shared fontarray(95, 5) as integer
dim shared diag
'load the font
OPEN "roman.fnt" FOR BINARY AS #1
st = 1
FOR l = 0 TO 95
FOR x = 0 TO 5
GET #1, st, fontarray(l, x)
st = st + 2
NEXT
NEXT
CLOSE
'*********
screenres 800, 600, 32 '800x600x32 bit window
'load the node bitmaps
BLOAD "23node2.bmp"
twonodedisplay = imagecreate(31, 18)
GET (0, 0) - (30, 17), twonodedisplay
threenodedisplay = imagecreate(58, 18)
GET (31, 0) - (88, 17), threenodedisplay
'*********
dim tre as two3tree ptr
tre = newTwo3Tree
Open "number.txt" for input as #1
While not eof(1)
If a then Addvalue tre, a
displayall tre
input #1, a
cprint 0,0,"Press Any Key to add " + STR$(a), rgb(0,25,50)
sleep
Wend
sleep
deletesubtree tre -> root
deallocate tre 'return mem to osx
close
Function Newtwo3node () as two3node ptr
return Newtwo3node(0,0)
End Function
Function Newtwo3node(value as integer) as two3node ptr
return Newtwo3node(value, 0)
End Function
Function Newtwo3node(lvalue as integer, rvalue as integer) as two3node ptr
dim temp as two3node ptr
temp = allocate(len(two3node))
temp -> leftvalue = lvalue
temp -> rightvalue = rvalue
temp -> leftbranch = 0
temp -> midbranch = 0
temp -> rightbranch = 0
temp -> parent = 0
return temp
End Function
Sub DisplayAll(tree as Two3Tree ptr)
BLOAD "aqua.bmp"
If tree = 0 or tree -> root = 0 then exit sub
displaynode tree -> root, 400, 100, 1
end sub
Sub displaynode (p as two3node ptr, xx as integer, xy as integer, level as integer)
IF not p -> rightvalue then
IF p -> leftbranch then 'it has children
LINE (xx, xy + 9) - (xx - 800 \ (3 ^ level), xy + 59), rgb(0,25,150)
LINE (xx, xy + 9) - (xx + 800 \ (3 ^ level), xy + 59), rgb(0,75,100)
displaynode p -> leftbranch, xx - 800 \ (3 ^ level), xy + 50, level + 1
displaynode p -> midbranch, xx + 800 \ (3 ^ level), xy + 50, level + 1 'no need to check if it has one branch is has 2
end if
display2node xx, xy, p
Else
IF p -> leftbranch then 'it has children
LINE (xx, xy + 9) - (xx - 800 \ (3 ^ level), xy + 59), rgb(0,25,150)
LINE (xx, xy + 9) - (xx, xy + 59), rgb(0,50,125)
LINE (xx, xy + 9) - (xx + 800 \ (3 ^ level), xy + 59), rgb(0,75,100)
displaynode p -> leftbranch, xx - 800 \ (3 ^ level), xy + 50, level + 1
displaynode p -> midbranch, xx, xy + 50, level + 1
displaynode p -> rightbranch, xx + 800 \ (3 ^ level), xy + 50, level + 1 'no need to check if it has one branch is has 3
end if
display3node xx, xy, p
End if
end sub
Sub AddValue(tree as two3tree ptr, value as integer)
dim temp as two3node ptr
temp = NewTwo3Node(value)
IF tree -> root = 0 then 'new root node
tree -> root = temp
tree -> size = 1
tree -> depth = 1
exit sub
end if
dim p as two3node ptr
p = findrightleaf(tree, value)
AddNode(p, tree, temp)
End Sub
Sub AddNode (pp as two3node ptr, tree as two3tree ptr, pnode as two3node ptr)
dim p as two3node ptr, node as two3node ptr
p = pp
node = pnode
If not p -> rightvalue then
p -> rightvalue = node -> leftvalue
IF p -> leftbranch = node then
p -> leftbranch = node -> leftbranch
else p -> midbranch = node -> leftbranch
end if
p -> rightbranch = node -> midbranch
deallocate node
sort p
else 'i have to promote
'first insert all the values
p -> tempvalue = node -> leftvalue
IF p -> leftbranch = node then
p -> leftbranch = node -> leftbranch
elseif p -> midbranch = node then p -> midbranch = node -> leftbranch
else p -> rightbranch = node -> leftbranch
end if
p -> tempbranch = node -> midbranch
sort p
'now split it up
dim node2 as two3node ptr
node2 = NewTwo3Node(p -> leftvalue)
node2 -> leftbranch = p -> leftbranch
node2 -> midbranch = p -> midbranch
node2 -> parent = p
IF node2 -> leftbranch then node2 -> leftbranch -> parent = node2
IF node2 -> midbranch then node2 -> midbranch -> parent = node2
deallocate node
node = NewTwo3Node(p -> rightvalue)
node -> leftbranch = p -> rightbranch
node -> midbranch = p -> tempbranch
node -> parent = p
IF node -> leftbranch then node -> leftbranch -> parent = node
IF node -> midbranch then node -> midbranch -> parent = node
p -> rightbranch = 0
p -> tempbranch = 0
p -> leftbranch = node2
p -> midbranch = node
p -> leftvalue = p -> tempvalue
p -> rightvalue = 0
p -> tempvalue = 0
tree -> size = tree -> size + 1
IF p -> parent then
Addnode p -> parent, tree, p
ELSE
tree -> root = p
tree -> depth = tree -> depth + 1
end if
end if
End Sub
Sub DeleteTwo3Tree(tree as Two3Tree ptr)
DeleteSubTree (tree -> root)
Deallocate tree
tree = 0
End Sub
Sub Deletesubtree(node as two3node ptr)
IF node -> rightbranch then Deletesubtree node -> rightbranch
If node -> midbranch then Deletesubtree node -> midbranch
If node -> leftbranch then DeleteSubtree node -> leftbranch
deallocate node
node = 0
end sub
sub display2node(x as integer, y as integer, node as two3node ptr)
put (x - 16, y), twonodedisplay, ALPHA, 196
dim strin as string
strin = STR$(node -> leftvalue) + ",_" + STR$(node -> rightvalue)
xx = x + 15 - len(strin) * 3
cprint xx - 5, y + 4, STR$(node -> leftvalue), 0
end sub
sub display3node(x as integer, y as integer, node as two3node ptr)
put (x - 29, y), threenodedisplay, ALPHA, 196
dim strin as string
strin = STR$(node -> leftvalue) + ",_" + STR$(node -> rightvalue)
xx = x + 29 - len(strin) * 3
cprint xx - 26, y + 4, STR$(node -> leftvalue) + ",_" + STR$(node -> rightvalue), 0
end sub
SUB cprint (x as integer, y as integer, text as string, colour as integer)
FOR ll = 1 TO LEN(text)
l = ASC(MID$(text, ll, 1)) - 33
IF l <> 62 AND l > -1 THEN
FOR a = x TO x + 5
LINE (a, y)-(a, y + 15), colour, , fontarray(l, a - x)
NEXT
END IF
x = x + 6
NEXT
END SUB
Function Newtwo3tree () as two3tree ptr
dim temp as two3tree ptr
temp = allocate(len(two3tree))
temp -> root = 0
temp -> depth = 0
temp -> size = 0
return temp
End Function
Function findrightleaf (tree as two3tree ptr, value as integer) as two3node ptr
dim p as two3node ptr
p = tree -> root
while p -> leftbranch 'traverse to the leaf level
IF value < p -> leftvalue then
p = p -> leftbranch
ELSEIF p -> rightvalue > 0 and value > p -> rightvalue then p = p -> rightbranch
ELSE p = p -> midbranch
end if
wend
return p
End Function
Sub Sort (p as two3node ptr)
If p -> tempvalue then
'get the tempvalue in the middle
If p -> tempvalue > p -> rightvalue then SWAP p -> tempvalue, p -> rightvalue
If p -> tempvalue < p -> leftvalue then SWAP p -> tempvalue, p -> leftvalue
END IF
IF p -> rightvalue then
IF p -> rightvalue < p -> leftvalue then SWAP p -> rightvalue, p -> leftvalue
END IF
'now lets order the branches
'lowest = left, highest = temp
FOR i = 0 TO 2 '3 times through to set right if in reverse order
IF p -> leftbranch then
If greatestvalue(p -> leftbranch) > p -> midbranch -> leftvalue then SWAP p -> leftbranch, p -> midbranch
END IF
IF p -> rightbranch then
IF greatestvalue (p -> midbranch) > p -> rightbranch -> leftvalue then swap p -> midbranch, p -> rightbranch
End if
IF p -> tempbranch then
IF greatestvalue (p -> rightbranch) > p -> tempbranch -> leftvalue then swap p -> rightbranch, p -> tempbranch
END IF
NEXT
END SUB
Sub Inserttotemp (src as two3node ptr, dest as two3node ptr)
dest -> tempvalue = src -> leftvalue
IF dest -> leftbranch = src then
dest -> leftbranch = src -> leftbranch
dest -> tempbranch = src -> rightbranch
ELSEIF dest -> midbranch = src then
dest -> midbranch = src -> leftbranch
dest -> tempbranch = src -> rightbranch
ELSE
dest -> rightbranch = src -> rightbranch
dest -> tempbranch = src -> leftbranch
END IF
sort dest
Deallocate src 'return memory to OS X
End Sub
Function greatestvalue (p as two3node ptr)
IF p -> rightvalue then return p -> rightvalue
return p -> leftvalue
End Function
number.txt:
13
65607
2
4
6
7
3
5
18
1
14
6
200
100
123
143
164
It displayed the tree correctly until it has to triple promote. Here is the tree before hand:
. 4,7
. 2 6 18,200
1 3 5 6 14 100,123 65607
Then when i try to insert 143, nothing happens except I loose 100 from the three node that its in. leaving me with:
. 4,7
. 2 6 18,200
1 3 5 6 14 123 65607
[/code]
f you play a Microsoft CD backwards you can hear demonic voices. The scary part is that if you play it forwards it installs Windows.