我的设计问题是我正在尝试编写一个适合几种可能的子类型的通用类。具体来说,我正在尝试为二进制搜索树编写一个Node类,以适合搜索树的几种实现(Avl树,2-3树,红黑树等)。我的问题是:不同的树需要不同的树Node类中的变量以保持效率。 AvlTree需要一个height变量,RedBlackTree需要一个颜色变量(AvlTree没用),等等。最佳设计解决方案是什么:
在Node中声明许多变量(颜色,高度,平衡因子等),并给出许多构造函数?
在Node中是否有一个Object类型的变量,称为元数据,每个实现都将使用该变量来包含其元数据?
还有别的吗
最佳答案
如何为二叉搜索树设计通用节点?
好,你问...
首先,下面是一个很好的链接。并且一定会暴露
问题的广度,严格遵守数据结构。
Abstract_Hierarchies使一切变得如此简单。
至少您在思考正确的方向。正如我在这里看到的,至少从表面上讲,最佳方法(语言不可知)在OOP中始终是相同的。
顺便说一句,Java是开始实践OOP原理的优秀语言。实际上,我只是删除了该段...
IFace,IFaces,FullInterface。建立任何良好的抽象层次结构的秘诀是“裸露骨头”的实现。
(我不会在这里实现泛型,但是Java仅对此提供了强大的支持。java.util.collection是集合层次结构的根)。
但是,泛型实际上是为您内置的语言。一切都是Java中的对象。您去了...您可以想象的任何类型的最抽象表示。
根据您的特定要求:使用伪...或伪伪
这就是我所能掌握的一切。伪伪(无论如何)。
INode必须至少具有:
一个私有数据成员或密钥。
至此,至少引用2个,但不超过2个。
子INodes(此处带来的不便。java不
使用户可以通过指针直接访问内存,例如
C / C ++)显然是2,但“至少”是
在思考进步时非常重要的方法
实施。只是绝对的本质,仅此而已。
公共访问器和专用数据的更改器。
管理器功能声明。(简短列表,我不记得了
Java是否支持运算符重载)
考虑到这种情况,无法想象op等于如何处理。
由于INode除其数据外是无用的(不是整个)
结构,这是我要设置专用访问密钥的地方。
(特定于Java),这也意味着
上面的管理器功能,INode不会声明
公开CTOR。 Java版本的C ++朋友类(ITree)
就您而言(查找类访问键/ Java)。这也是
展示单例图案的属性。
- -停在这里。尽管看起来很不完整,但这是
第一阶段抽象INode的实现
层次结构。
对于二叉树数据结构而言,这已足够。
(扩展或实现)的INode接口
具体的二叉树节点类。到目前为止很简单。
接下来,我们正在寻找满足以下条件的设计规定:
BST节点类。可以想象,尽管既不方便也不
适当地将我们当前的INode接口实现为
Binary Search Tree Node class。(no ... no ... no ... modifications !!)
它是...“为修改而关闭,&为扩展而开放;
我们将从新的接口扩展INode ...我想我将其称为IOrderedNode接口应该始终具有超描述性
命名约定。 (我知道,发生了什么事)。其实呢
确实反映了二叉树和
二进制搜索树。二叉搜索树只是有序的
二叉树。显然有与此相关的含义
琐碎,不同。主要是,
串行数据结构。这意味着,我们应该回到INode
并评估(不要更改!)私有数据成员。
--------
希望我们在考虑抽象可扩展性时考虑周全
该数据成员的。如果我没记错的话,java中的泛型已经
增强了多功能性...我将留给您。借用一个概念
从C ++开始,我会使用通用指针来表示模板Arg的类型。要么
更好的是,一个空指针(不能在那里使用星号,因为它会格式化我的文本)不会比这更抽象!我的意思是(无效)(星号);
暂时不要使用Java,因为Java中的所有类型都是
整数类型,通过从Object类的
ToString()方法。应该仔细考虑用户定义的类型(UDT)
在这里,由于跨数据结构的不同实现
将实现一系列IFace扩展。 (指针,refs:在Java中)始终是基础级别上最好的初始类型。他们可以
适用于甚至指向甚至是最复杂的UDT的引用。
好的,返回那些我们将要利用的串行属性。
遍历::预订,订购,订购,广度优先。由于我们只是在探索INode层次结构,
我们应该开始考虑将在
关联的数据结构,并尝试识别任何下属
依赖关系将需要出现在我们的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...
*
*******************************************/