CODEWITHSUNDEEP
c++binary-treebinary-search-treeavl-tree
Asher Yartsev
Asher Yartsev

Reputation: 87

AVL tree implementation via inheritance

I was asked to implement an AVL tree , and I did it- now it works for all stress-tests I could think about. now I see we were advised to implement it, s.t it inherits from binary search tree that inherits from a binary tree. I want to it right- I'll be glad to get an advice on which invariants (fields that have to appear) should appear in each of them ( the binary tree, the search and the AVL). thank you! here is my implementation for it: enter image description here

Upvotes: 0

Views: 1717

Answers (1)

kabanus
kabanus

Reputation: 25895

I'll give you some tips. When coding object oriented code, I find it useful to design top down - that is, implement the parent class, and then inherit and decide what needs to be added/overriden.

Examples:

binary tree:

  1. Well, you obviously need a node, with two children (how you implement that is your thing). Node needs a data field.
  2. Insertion - with no restriction, you can insert after a node to the left, to the right or replace the parent. Which of these you implement and how is up to you.
  3. Traversal - go left than right, right than left etc...
  4. Lookup has no restriction, so you will have to traverse the entire tree (worst case)

All these are general properties of a binary tree. You could come up with more (printing for debug uses etc...). We inherit all these and start with:

binary search tree

  1. Node doesn't really change, does it?
  2. Well now insertion is not determined at all by you! You do not insert to a specific node you insert to the entire tree. You need to look for the place you want to insert, then you can call the base insertion.
  3. Traversal doesn't change does it?
  4. Lookup can be improved drastically, and probably should be overridden completely.
  5. You can think of new methods that didn't make sense for a non ordered search tree, though I don't have any coming to mind. Some may consider adding a compare (less than for example) operator to a node, overloading it to compare to the data type or another node.

Finally, you inherit this to make an AVL tree. Try and consider what can be inherited as is, what needs to be completely overridden, and what needs some work before calling a base class. You can google/wikipedia for common tree operations (namely I didn't mention delete, for example). Good luck.

EDIT

AS davmac mentions, the node of an AVL changes - it needs an additional field! We had two children we inherited, and the data field, but now we also need a balance factor. This is an example of when to add a field.

Upvotes: 2

Related Questions