OCaml 中类的红黑树

Question

有谁知道如何在 OCaml 中用 classes 实现红黑树？至少 class 属性和初始值设定项？我是 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。选项值不是对象（class 的实例）。所以你不能在上面调用方法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 中的相等比较运算符是 =（在我的示例代码中）。

OCaml 中类的红黑树

Red black trees with classes in OCaml

oop

binary-tree

ocaml

class

red-black-tree

OCaml 中 类 的红黑树

Red black trees with classes in OCaml

oop

binary-tree

ocaml

class

red-black-tree

OCaml 中类的红黑树