CODEWITHSUNDEEP
javadesign-patterns
blz
blz

Reputation: 414

How to design a general Node for a Binary Search Tree?

My design problem is that I'm trying to write a general class that would fit several possible subtypes. Specifically, I'm trying to write a Node class for a binary search tree, that would fit several implementations of search trees (Avl Tree, 2-3 Tree, Red-Black tree, etc.) My problem is: different Trees require different variables in the Node class in order to maintain efficiency. AvlTree need a height variable, RedBlackTree need a color variable (which an AvlTree have no use for), and so on. What's the best design solution:

  1. declare many variables in the Node (color, height, balancing factor,...), and just give many constructors?
  2. Have a a variable of type Object in Node, called metadata, which every implementation will use to contain its metadata?
  3. Something else?

Upvotes: 2

Views: 870

Answers (2)

Ioane Sharvadze
Ioane Sharvadze

Reputation: 2148

I had same problem and decided to go with this simple solution. 

abstract class BSTnode<K, M> {
    K key;
    M meta; 
    BSTnode<K> left;
    BSTnode<K> right;
    BSTnode<K> parent;
}

This simply solves the problem for your metadata.

Upvotes: 0

Abstraction is everything.
Abstraction is everything.

Reputation: 250

How to design a general Node for a Binary Search Tree?

ok, you asked...

First, that is a great link below there. And will certainly expose
the breadth of your question, strictly keeping to Data Structs.

Abstract_Hierarchies make everything so much easier. At least you are thinking in the right direction. As I see some have mentioned here, at least superficially, the best approach (Language Agnostic) is always the same in OOP.

By the way, Java is an excellent language, to begin practicing OOP principles. In fact, I just deleted that paragraph...

IFace, IFaces, FullInterface. The secret to building any good abstract hierarchy is 'bare bones' implementation. (I won't implement the generics here, but Java has robust support just for this. java.util.collection this is the root of the collections hierarchy).

However, generics are virtually built into the language for you. Everything is an Object in Java. There you go...The most abstract representation of any type you can imagine.

To your specific requirements: in pseudo...or pseudo-pseudo that's all I was ever able to grasp. The pseudo-pseudo(whatever).

INode must have at least:

  1. One Private DATA member or Key.

  2. Reference to at LEAST, BUT at this point, not more than 2. Child INodes(a minor inconvenience here. java does not give users direct access to memory via pointers, like C/C++) Obviously, this is exactly 2, but 'AT LEAST' is a very important methodology when thinking about progressive implementation. Just the absolute essence, no more.

  3. Public accessor and mutator for private DATA.

  4. Manager function Declarations.(short list, I don't recall
    whether or not operator overloading is supported in java or not) Can't imagine how the op equals is handled, given the case...hmmm

  5. Since an INode is useless(not entireley) apart from its Data
    structure, This is where I would set up private access keys. (Java specific) this also means, in reference to the Manager functions above, INode will not declare a public CTOR. java's version of C++ friend class (ITree) In your case.(look up class access key/Java). This also Exhibits properties of the Singleton Pattern. ---STOP HERE. This, while appearing quite incomplete, is the First stage Implementation of the abstract INode Hierarchy.

This is enough for a Binary Tree Data Structure.
(extend or implement) the INode Interface for a concrete Binary Tree Node class. So far so simple.

Next, we are looking for the design provisions that will satisfy
a BST Node class. It is conceivable, though neither convenient nor
proper, to implement our current INode Interface as a
Binary Search Tree Node class.(no...no...no...modifications!!)it is what
it is...'Closed for Modifcation && Open for Extension;

We will Extend INode from our new Interface...I think I will call it IOrderedNode Interfaces should always have hyper descriptive
naming conventions. (I know, what happened to mine). Actually, it
does reflect the primary difference between a Binary Tree, and a
Binary Search Tree. A Binary Search Tree is simply an Ordered
Binary Tree. There are implications related to this, apparently
trivial, difference. Mainly, all of the practicality of having a
Serial Data Structure. This means, that we should go back to INode
and evaluate (NOT CHANGE!!) the private Data member. --------

Hopefully, we were thoughtful when considering the abstract extensibility
of that Data member. If I remember right, generics in java have been
augmented in versatility...I will leave that to you. To borrow a concept
from C++, I would have used a generic pointer to type of template Arg. Or
better yet a void pointer(can't use the asterisk there 'cause it formats my text) doesn't get more abstract than that! the(void)(star), I mean;

Forget for a moment that you are using java, because all types in java are
integral types, via the hash code inherited from the Object class's
ToString() method. User Defined Types (UDTs) should be well thought out here, because of the disparate implementations across Data Structures that
will implement the series of IFace extensions. (pointers, refs: in java) are always the best initial types at the base levels. They can be
adapted to point to, or hold reference to even the most complex UDT.

Ok, back those Serial attributes we were about to exploit.
Traversals::Pre-Order, In-Order, Post-Order, Breadth-First. Since we are only exploring the INode hierarchy, we should start considering the algorithms that will be implemented in
the associated Data Structures, and try to identify any subordinate
dependencies that will need to appear in our IOrderedNode 

//I think from here on out I will just write the code...
//20 min later...this stupid @$$ message box is the worst
//dev environment I have EVER! worked in...
//......(granted it isn't that)
//40 min later in Visual Studio. Tired of working without
//a net...no KB short cts...NO TAB! no auto formatting...?

template<class T>
class IcanOnlyBeaBT;//fwd _decl 
                //or a doubley linked list, an Adapter, a...
                //keep thinking as you go...
template<class T>
class INode
{   
    friend class IcanOnlyBeaBT<T>;//this takes care of access
public:

//  At this level we have protected
//  access for derived classes--
//  EXCEPT! with TEMPLATED classes!
//  in C++ this is NOT an issue WHEN.
//  1. data members are 'captured' by
//     template instantiation
//  2. and 3. are the exact same answer
//     as 1. only I would be forced to
//     elaborate on two specific instances
//     with the only advantage being a 
//     sufficing ward on those nit-pickers
//     who love to leave comments like
//
//          "Weellll...NOT exactly"
//
//          I dont care. I would rather
//          write my explaination for not 
//          explaining further...

        /************************************/
        // (no worries here in java - C#)
        // implement now to enforce the
        // design on higher level abstractions;
        // protected access may become 
        // private in remote derived classes
        // we never want to come back here!!!
        // push dependencies up! up! up!


     INode() : whatever_Data_I_want_Ha_Ha(nullptr) {}
     virtual void SetWhatEverDataIWant(T*) = 0;
     virtual T* GetWhateverDataIWant() = 0;
     virtual T* GetWhateverDataIWant() const = 0;
 protected:
     virtual ~INode() = 0;
     T* whatever_Data_I_want_Ha_Ha;
     INode<T>*left_child;
     INode<T>*right_child;
 };

 template<class T>
 INode<T>::~INode() {} // don't worry about this it's cool
                      //...notice that   
                  // the member is protected...and pure virtual...
                  // it's just a boomerang--    

    // Notice how adaptable this Interface has become
    // after only one extension and implementation is refined. 

    // This is BOTTOM UP because we are BUILDING... 
    // ...this should be TOP DOWN as we DESIGN...
    // THINK--TOP DOWN...BUILD BOTTOM UP...

    // Push ALL negotiable DEPENDENCIES UP AS YOU BUILD.
    // Ideally, these were identified during design.
    // It rarely ever goes that way cleanly...
    // at least not for me, but try...try

    // As incremental implementation progresses, You
    // may start to identify some of these negotiable
    // dependencies...these two interfaces are still
    // super lean..and rather boring, but continue towards
    // the AVL, Red Black, Other Data structurs they will show.

    // Nodes are, for the most part, like a drawer full
    // of silverware. They CAN'T do anything unless
    // they are being used.

    // GO UP now!!!...BUT always JUST enough!!
    // No more; GOAL...to have a DESIGN SPECIFIC
    // hierarchy, that IS extensible in a MODULAR 
    // fasion, like LEGOS. ADAPTABLE to ANY COMPATIBLE
    // Data Structure, Not just TREES. Even from here...
    // there are other suitablilities coming to mind,
    // such as Graphs, Doubley Linked Lists, circular queues.
    // Nodes are common place in Data Structures...on...on...

    // Principle Attribute: ICanBe_A_BST Data Struct now.

    // fwd _decl: 
  template<class T>     
  class ICanBe_A_BST; //The BT Node was FIRST Abstraction, 
                // BST is SECOND.
                // OR a Composite Object Structure! for the  
                // Composite Design Pattern...or...or...or
                // BECAUSE, this IOrderedNode is more QUALIFIED 
                // and adaptable. LOOK HERE! Don't throw away
                // the specific sutibility of lower abstractions
                // This should be extended to fulfil design reqs
                // IOrderedNode is not intended to be a BT, 
                // IT 'IS A' BT by extension, BUT, it is a BST Node.

                // This abstract hierarchy, UPON DESIGN COMPLETION  
                // Will have pervasive extensibility @ unique levels.  
                // think {OPEN-CLOSED} open for EXTENSION, and
                // CLOSED for MODIFICATION...GOAL...DON'T...come
                // BACK inside this BLACK BOX once it is CLOSED..!  

template<class T>
class IOrderedNode : public INode<T>
{ 
              // RIGHT HERE! ALL previous implementation
              // Is abstracted AWAY. Look how clean it all is..
              // in java you would be Extending INode Interface HERE!.
              // Extending IN JAVA IS inheritance.
              // ALL public and protected members.
              // Closed for MOD. open for EXTENSION
public:                                
    IOrderedNode() : height(0) { }

protected:
//NOTICE!(I Can Be A BST Node IF!)my data is INTEGRAL & comparable.
//FOR instance a bool is unqualified--how can you order a tree
//when the only value is a 1 or a 0;
//UDT is dependent upon guess...
//THE USER who defind it(integral && comparable);

// Question: is there anything missing from this level 
// that would disqualify concrete instantiations from adequately
// filling the intended role? .....Seriously...
// I have been awake for two days now. This may need editing. 
// Regardless the process is the 
// same all the way to Red Black and beyond...

int height; //new data member; height of the tree at that node...
            //this comes in handy when computing the balance factor
            //on balanced trees...AVL, R&B,
};



/***********************NOTE:***********************
*
*   There are several considerations that have to be made 
*   when you are "leaving" data and and implementation "behind". 
*   We know we don't EVER want to come back here...
    (not a super realistic GOAL...)
*   Is the implementation specific to the level of bstraction.?...
*   YES? then leave it here. 

    IS...the DATA specific to the implementation ????
*   this deserves 4 Q-marks because, IF at all POSSIBLE PUSH
*   these IMPLEMENTATION DEPENDENCIES..UP This RESULTS in IoC
*   Inversion of Control Inversion of CONTROL INVERSION! of Control...
*   Implementation dependencies should come from higher level abs
*   to lower level Implementation...repeats you are seeing all over
    this now TLDR, are Cardinal principles of Object
*   Oriented Design. Not because I love commenting code...
    but since YOU asked...I won't leave out the 'life blood'.

*   Incidentally, there is a requisite 
    'AHAAH moment' that either comes
*       or it doesn't.
*
****************************   PERSONAL NOTE:*********************
*
*   I picked up java in the late 90's, and was like.
*   "...what the hell is an OBJECT..?" Two years of programming from a
*   procedural paradigm, in an OOP language-LATER! It hit me......
*   (I know...slow learner)...but I remember saying out loud....
*   'THAT...IS...THE...COOLEST...THING...I HAVE EVER...tripped over...
*   Consensually, OOP is considered to be in its INFANCY. 
*   Theories (opinions) are often the cause of some rather heated
*   contest. In fact, one of the most intense and persistant 
    "cival-war" I have ever encountered, nearly dominated an entire 
    forum. I didn't really know enough to have an opinion
*   one way or the other on the matter, but I remember thinking, 
    how absurd...and laughing alot.
*   The theoretical epicenter was localized on the issue of...
        wait for it...
*
*                   INHERITANCE v.s. COMPOSITION/AGGRAGATION
*
*       Hmm....Everybody knows that programming to interfaces, 
    adhereing to common sense, established design principles, 
    and proven patterns, can all be accomplished without inheriting
    from a single archtype...
*        "Not that there's anything wrong with that..." 
    I'm pretty sure, that was the vein of the row on that
         forum...Super entertaining though...
*
*******************************************/

Upvotes: 1

Related Questions