在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中的相等比较运算符为=（如我的示例代码）。