0

I am coding a Binary Tree as part of a learning exercise. I am trying to accommodate the two ways of deleting a node in a binary tree: DeleteByMerge and DeleteByCopy.

What is the best way to offer choice for a user to choose between these methods?

I am leaning towards a composition approach(like a strategy) :

public class BinaryTree{

   BtreeDelete del;
   public BinaryTree(){
      this.del = new DeleteByCopy();
   }

   public BinaryTree(BtreeDelete del){
      this.del = del;
   }

   public boolean delete(Node node){
       // Common code
       del.delete()
   }

}

Classes DeleteByMerge and DeleteByCopy implement the interface BtreeDelete, so I could wire up during instantiation like this:

BinaryTree btree = new BinaryTree(new DeleteByMerge());

OR

BinaryTree btree = new BinaryTree(new DeleteByCopy());

.

Inheritance Based approach:

public class BinaryTree{

   public BinaryTree(){

   }

   public boolean delete(Node node){
       // Common code
       deleteNode();
   }

   // An overriddable hook with a default implementation
   protected boolean deleteNode(Node node){
        //By default implementation for DeleteByCopy is provided
   }

}

Different implementations for delete will demand a separate subclass(leading to a possible explosion of classes):

public class BtreeDelByMerge extends BinaryTree{

   protected boolean deleteNode(Node node){
       // Code for deleting a node by Merging
   }
}

My qualm with the Inheritance approach is BtreeDelByMerge is not a type of Btree, it's behaviour does not change by much and having a to create a separate subclass for just one of its methods seems unnatural. Also it does not tend as well as the composition approach if I wanted a tree with a particular implementation of insert along with delete etc.

Are there any particular advantages going the inheritance way in this case? Also, is it a good idea to offer the choice at all? For ex: The Collections framework does not offer too many choices, so the implementations are well encapsulated and consistent but rigid.

ChrisOdney
  • 6,066
  • 10
  • 38
  • 48
  • 1
    Why is `BtreeDelByMerge` not a type of `Btree`? I see you didn't extend it from `Btree`, but you have it inheriting `deleteNode()` so I assume that's what you're doing. Personally I'd go with inheritance here. If you're worried about too many implementations, allowing people to plug-and-play helper objects via the constructor is only going to compound that. – musical_coder Oct 22 '13 at 05:40
  • 1
    Look at [this post](http://stackoverflow.com/questions/49002/prefer-composition-over-inheritance). Both `DeleteByCopy` and `DeleteByMerge` provide the method `deleteNode`, I think it's appropriate that they share the same interface on that matter. – Ben Barkay Oct 22 '13 at 05:41
  • @musical_coder Yeah you are right, I edited the code to inherit from BinaryTree. With the inheritance approach how do I give the same flexibility as the composition approach when it comes to wiring up different implementations? – ChrisOdney Oct 22 '13 at 06:24
  • You could make just a few private implementations of deleteNode() inside Btree, then have people pass an enum designating which one they want to the constructor. But again, if you want to limit the number of implementations, just create a few varieties of Btree without any wiring done in the constructor. – musical_coder Oct 22 '13 at 14:28

1 Answers1

1

I think that depends on the implementation of deleteNode. If all it does is working on the node itself then your first approach (the strategy approach) looks clean and elegant.

If there's a case (or a case may exist in the future) in which the deletion could be made more efficient by using protected members/method of the class, I would choose the inheritance approach.

For example: let's say you have an inner hash map that helps you traverse through the tree faster then just be walking left/right/parent, and you make this map protected. Now, if you choose the strategy approach, you won't be able to use that map and you might need it for faster deletions. If you choose the inheritance approach and make the map protected you might be able to improve the naive algorithm for deletion.

Also, this is only an exercise, but if you were to face such dilemma in a "real-life" scenario you need to remember that deciding over an API is a commitment. You should take the in consideration the points I mentioned.

  1. Making a strategy - easier for others to inject a behaviour.
  2. Inheritance - easier to use class inner implementation.
Avi
  • 21,182
  • 26
  • 82
  • 121
  • Damn! this is the reason I actually started out with inheritance! I will definitely need access to a lot of encapsulated elements which is not possible via Strategy, but in that case using inheritance means lesser flexibility to the user. As I asked above, how would you let the user wire up a tree with different implementation for insert, delete etc - in case of the inheritance approach? – ChrisOdney Oct 22 '13 at 06:00
  • Making a decision usually means making compromises and you should choose what would probably better serve your needs. You can also make a combination of the two but it might not be that elegant. – Avi Oct 22 '13 at 06:06
  • Use inner classes (non-static) if you want composition AND access to implementation. – siledh Oct 22 '13 at 12:39
  • @siledh - That's a possibility. I don't care for it too much though, it can lead to an unclear code too easily – Avi Oct 22 '13 at 12:56