Vấn đề tham chiếu C#

Question

Tôi đang tham gia khóa học thuật toán tại trường đại học và đối với một trong các dự án của tôi, tôi muốn triển khai cây đỏ đen trong C# (bản thân quá trình triển khai không phải là dự án. chọn giúp tôi).

cây đỏ-đen của tôi nên giữ phím chuỗi, và đối tượng tôi tạo cho mỗi nút trông như thế này:

class sRbTreeNode 
{ 
    public sRbTreeNode Parent = null; 
    public sRbTreeNode Right = null; 
    public sRbTreeNode Left = null; 
    public String Color; 
    public String Key; 

    public sRbTreeNode() 
    { 
    } 

    public sRbTreeNode(String key) 
    { 
     Key = key; 
    } 
} 

tôi đã thêm một số phương pháp cơ bản để in cây, tìm gốc rễ, min/khóa tối đa (theo bảng chữ cái), v.v ...

Tôi gặp sự cố khi chèn các nút (do đó, xây dựng cây). Bất kỳ ai quen thuộc với cây đỏ đen đều biết rằng khi thêm một nút vào một bên, bạn có thể đã thay đổi số dư của cây. Để khắc phục điều này, bạn cần phải "xoay" quanh các nút trên cây để cân bằng cây.

Tôi đã viết một phương pháp RightRotate và LeftRotate trong mã giả, và sau đó khi tôi cố gắng triển khai nó trong C#, tôi chạy vào một loạt các vấn đề tham chiếu với đối tượng sRbTreeNode mà tôi đã tạo.

Đây là pseudo-code tôi đã viết cho các phương pháp LeftRotate:

LeftRotate(root, node) 
    y <- node.Right; 
    node.Right <- y.Left; 
    if (y.Left != null) 
     y.Left.Parent <- node; 
    y.Parent <- node.Parent; 
    if (node.Parent = null) 
     root <- y; 
    else 
     if (node = node.Parent.Left) 
      node.Parent.Left = y; 
     else 
      node.Parent.Right = y; 
    y.Left <- node; 
    node.Parent <- y 

tôi nhận được một gợi ý để thực hiện nó thẳng về phía trước, nhưng không sử dụng từ khóa 'ref', mà tôi đã cố gắng lúc đầu. Đây là cách tôi đã làm nó:

public static void LeftRotate(sRbTreeNode root, sRbTreeNode node) 
    { 
     sRbTreeNode y = node.Right; 
     node.Right = y.Left; 
     if (y.Left != null) 
      y.Left.Parent = node; 
     y.Parent = node.Parent; 
     if (node.Parent == null) 
      root = y; 
     else 
      if (node == node.Parent.Left) 
       node.Parent.Left = y; 
      else 
       node.Parent.Right = y; 
     y.Left = node; 
     node.Parent = y; 
    } 

Bây giờ, khi tôi gỡ lỗi, tôi thấy rằng nó hoạt động tốt, nhưng các đối tượng tôi vượt qua phương pháp này chỉ được luân chuyển trong phạm vi của phương pháp. Khi nó rời khỏi phương pháp này, có vẻ như không có sự thay đổi nào đối với các nút thực tế. Đó là lý do tại sao tôi nghĩ đến việc sử dụng từ khóa 'ref' ngay từ đầu.

Tôi đang làm gì sai?

Answer 1

Bởi vì trong cơ thể của phương pháp của bạn, bạn làm như sau:

root = y; 

bạn cần phải vượt qua root với một modifier ref. node không cần, bởi vì node chính nó không bao giờ được cập nhật để trỏ đến một ndoe khác. .

Answer 2

Tôi không hiểu tại sao bạn nên có bất kỳ vấn đề nào với tham chiếu - các nút Trái/Phải/Phụ huynh có thể được sao chép giống như trong mã giả này.

Bạn sẽ có thể mở rộng nó thành C# mà không quá nhiều phiền toái - trừ khi bạn đang sử dụng từ khóa 'ref', trong trường hợp này bạn có thể nhận được kết quả không thể đoán trước.

Có lẽ nếu bạn có thể hiển thị mã bạn đã thực sự viết cho đến thời điểm này và chúng tôi có thể giúp gỡ lỗi đó.

Answer 3

khuyến nghị của tôi:

• Không bao gồm con trỏ mẹ. Chúng không cần thiết cho các thuật toán chèn hoặc xóa và sẽ làm cho mã của bạn phức tạp hơn. Ví dụ: LeftRotate có thể được viết chỉ với một tham số và sẽ dài khoảng một nửa nếu bạn không sử dụng con trỏ cha mẹ.
• Sử dụng số enum cho thuộc tính Color thay vì string và khởi chạy nó trong hàm tạo.
• Đọc this article nếu bạn chưa có.