While working on my own non-TR implementation of PFDS RB Tree following[1] and heavily consulting the pfds implementation in the Racket package catalog[2][3][4], when trying to implement key deletion, I found an issue with the implementation by Hari Prashanth K R (krhari). Apparently he is no longer involved with Racket and apparently Asumu Takikawa only migrated the package to the new package system (huge thanks for that, btw).
A minimal erring example is:
#lang typed/racket
(require pfds/red-black-tree)
(random-seed 1)
(define numbers : (Listof Integer)
(set->list
(list->set
(ann
(for/list ((i : Integer (in-range 0 100)))
(ann (random 0 10000) Integer))
(Listof Integer)))))
(displayln numbers)
(define t : (RedBlackTree Integer) (redblacktree <))
t
(define l (redblacktree->list t))
l
(define t1
(for/fold ((t : (RedBlackTree Integer) t))
((n : Integer (in-list numbers)))
(insert n t)
#;((cast insert (Integer)
(ann t (RedBlackTree Integer))
(ann n Integer)))))
t1
(define t2
(for/fold ((t : (RedBlackTree Integer) t1))
((n (in-list numbers)))
(delete n t)))
t2
And obligatory output:
(2463 8863 6799 4239 2255 575 8991 527 2718 5022 7166 1518 4174 7710 5325 3773 6541 829 557 8973 4028 652 9324 5212 6732 1596 8476 5067 7787 5707 1051 2298 7322 4490 6329 8889 5593 8825 1736 9416 6504 8808 6424 4120 4824 4728 3031 2503 183 679 7319 6535 343 1591 39 2327 2230 5558 3142 8774 1174 8838 1398 1046 2054 725 4309 7957 2837 6293 9845 7013 3893 7124 9636 2164 5124 4003 3235 7699 5139 3795 179 659 3155 6451 6066 3698 4450 9921 3345 1504 224 5616 960 8880 4512 1680 5696)
#<RBTree>
'()
#<RBTree>
Invariaance violation 'sub1
context...:
/home/joe/.local/share/racket/8.5/pkgs/pfds/pfds/red-black-tree.rkt:206:0: bal-right
/home/joe/.local/share/racket/8.5/pkgs/pfds/pfds/red-black-tree.rkt:148:0: del-help
[repeats 2 more times]
/home/joe/.local/share/racket/8.5/pkgs/pfds/pfds/red-black-tree.rkt:136:0: delete
body of "/home/joe/Projects/Programming/algorithms/pfds-rb-test.rkt"
Of course I was looking for an error in my own implementation before I realized, that probably the original implementation of re-balancing after deletion may be flawed. The original paper by Chris Okasaki just states:
Finally, it is natural to wonder whether similar improvements are possible for
deleting an element from a red-black tree. Unfortunately, it appears that the answer
is no. The two most straightforward algorithms known to us are still the well-known
bottom-up and top-down algorithms, amply described elsewhere (Cormen et al.,
1990; Weiss, 1998).
And guess what, the referenced publication (Weiss, 1998) contains only some Java implementation with hints on how to make it "more functional" to put it at best.
Does anyone have more experience with PFDS in Racket and particularly the methods for re-balancing RB trees in functional setting?
What I really like about the current implementation in pfds/red-black-tree is the reuse of the pattern-matching re-balancing at least for parts of the code. Frankly I do not know at the moment whether a proper reuse is even possible in this case.
I've got some ideas how to explore this problem further - should be easy to pin-point the problematic case(s) with my 4 (yes, four) implementations - but I'd like to see any hints from someone independent as I have been looking into this probably for too long.
There are more issues with the implementation in pfds package - but it's more of a "nice to have" improvements in reality. The issue described here is the only severe one I found. And of course, the insertion goes straight from the original paper and is implemented correctly. Or at least it matches my implementation from scratch which seems to be working OK so far
[1] https://www.cambridge.org/core/services/aop-cambridge-core/content/view/62BC5EA75A2C95E3F6EE95AE3DADF0E5/S0956796899003494a.pdf/red-black-trees-in-a-functional-setting.pdf
[2] pfds
[3] 7 Red-Black Trees
[4] https://github.com/takikawa/tr-pfds/blob/master/pfds/red-black-tree.rkt