红色的黑色树木与OCaml中的类

Question

有谁知道如何在OCaml中使用类实现红黑树？ 至少类属性和初始值设定项？我是OCaml的新手。

我尝试过：

type data  = {key: int; value: string}
class node (data: data) = 
object (self)
val mutable d = data
val mutable color = 1
val mutable left = ref (None: node option) 
val mutable right = ref (None: node option) 
val mutable parent = ref (None: node option) 
method getLeft = left
method getRight = right
method getParent = parent
method getColor = color
method getData = d
method setLeft (l: node option ref) = left := !l
method setRight (l: node option ref) = right := !l
method setParent (l: node option ref) = parent := !l
end;;

class rbtree =
object (self)
val mutable root = ref (None: node option)
val mutable nullNode = ref (None: node option)
method searchNode (aNode: node option ref) (key: data) = begin
if aNode = nullNode || key == (!aNode)#getData then aNode;
end;
end;;

我收到错误This expression has type node option It has no method getData

我正在尝试的是制作类似这样用C++编写的代码：

struct Node
{
int data;
Node *parent;
Node *left;
Node *right;
int color;
};
typedef Node *NodePtr;
class RedBlackTree
{
private:
NodePtr root;
NodePtr TNULL;
void initializeNULLNode(NodePtr node, NodePtr parent)
{
node->data = 0;
node->parent = parent;
node->left = nullptr;
node->right = nullptr;
node->color = 0;
}
NodePtr searchTreeHelper(NodePtr node, int key)
{
if (node == TNULL || key == node->data)
{
return node;
}
if (key < node->data)
{
return searchTreeHelper(node->left, key);
}
return searchTreeHelper(node->right, key);
}
};

Answer 1

对于您看到的错误，@Shon是正确的。你有这个表达式：

if aNode = nullNode || key == (!aNode)#getData then aNode;

aNode的类型是node option ref.所以这意味着!anode的类型是node option.选项值不是对象(类的实例(。因此，您不能在其上调用getData的方法。

同样，正如@Shon所说，您需要检索!aNode的值(如果有的话(。这将为您提供一个节点，该节点是一个对象，并且确实具有getData方法。

在if测试中内联编写此代码会很混乱。所以你可以写一个这样的函数：

let node_option_has_value node_opt value =
match node_opt with
| None -> false
| Some node -> node#getData = value

作为附带注释，您不应该使用物理相等运算符(==(进行比较。此运算符适用于特殊情况，不适用于一般用途。

OCaml 中的相等比较运算符是=(如我的示例代码所示(。