Why not mix and match the OO and the functional? Maybe you have a standard class for performing generic operations on trees, but certain tree-types require particular ops so you can just field those out to coderefs e.g

package Tree::Ops;

sub delete { ... }
sub join   { ... }

1;

# ... later

sub search { ... }

my $tree = Tree::Struct->new(
    someops  => 'Tree::Ops',
    searchop => \&search
);
[download]

This has the benefits of re-usability, flexibility and all those funky OO features. Or you could declare the functions straight into the symbol table of said package e.g

sub Tree::Ops::avl_search { ... }
[download]

Gaining all the benefits of being in a class while still giving the control to the user^[1].
HTH

_________
broquaint

^[1] I'm sure I should've used a bunch of OO buzzwords there ... ah well ;-)