在RUST中實作二叉搜索樹的遞回插入方法

我正在學習 Rust 并嘗試實作一個簡單的二叉搜索樹（實際上它正在重寫下面的 Java 實作）。這是我所做的：

use std::cmp::Ordering;

// Node of this BST, the two generic types are key and value
struct Node<K:Ord, V> {
    key: K,
    value: V,
    left: Option<Box<Node<K, V>>>,
    right: Option<Box<Node<K, V>>>,
    number_of_nodes: i32,
}

impl<K: Ord, V> Node<K, V> {
    // Create a new node
    fn new(key: K, value: V, number_of_nodes: i32) -> Node<K, V>{
        Node {
            key,
            value,
            left: None,
            right: None,
            number_of_nodes,
        }
    }
}

struct BST<K: Ord ,V> {
    root: Option<Box<Node<K, V>>>,
}

impl<K: Ord, V> BST<K, V> {
    // Get the size of this BST
    fn size(&self) -> i32 {
        size(&self.root)
    }

    // Search for key. Update value if found, otherwise insert the new node
    fn put(&self, key: K, value: V) {
        self.root = put(&self.root, key, value)
    }
}

// Function for recursively get the size of a sub BST 
fn size<K: Ord, V>(node: &Option<Box<Node<K, V>>>) -> i32 {
    match node {
        Some(real_node) => real_node.number_of_nodes,
        None => 0,
    }
}

// Function for recursively put a new node to this BST
fn put<K: Ord, V>(node: &Option<Box<Node<K, V>>>, key: K, value: V) -> &Option<Box<Node<K, V>>>{
    match node {
        None => {
            let new_node = Some(Box::new(Node::new(key, value, 1)));
            return &new_node;
        },
        Some(real_node) => {
            match key.cmp(&real_node.key) {
                Ordering::Less => real_node.left = *put(&real_node.left, key, value),
                Ordering::Greater => real_node.right = *put(&real_node.right, key, value), 
                Ordering::Equal => real_node.value = value,
            }
            real_node.number_of_nodes = size(&real_node.right)   size(&real_node.left)   1;
            node
        },
    }
}

但是這段代碼不會編譯，在這一行self.root = put(&self.root, key, value)，我得到一個錯誤：

不匹配的型別
預期列舉 'Option<Box<Node<K, V>>>' 找到參考 '&Option<Box<Node<K, V>>>'

我不知道如何解決這個問題，我試圖將&self引數更改為self或self.root，*self.root但我遇到了更多錯誤。我對 Rust 中的參考感到非常困惑，我想做的就是用 Rust 重寫以下 Java 代碼。

public class BST<Key extends Comparable<Key>, Value>
{
    private Node root;              //root of BST

    private class Node
    {
        private Key key;            // key
        private Value val;          // associated value
        private Node right, left;   // left and right subtrees
        private int N;              // number of nodes in subtree

        public Node(Key key, Value val, int N)
        {
            this.key = key;
            this.val = val;
            this.N = N;
        }
    }

    // Returns the number of key-value pairs in this symbol table.
    public int size()
    {
        return size(root);
    }

    // Return number of key-value pairs in BST rooted at x
    private int size(Node x)
    {
        if (x == null) return 0;
        else return x.N;
    }

    public void put(Key key, Value val)
    {
        root = put(root, key, val);
    }

    private Node put(Node x, Key key, Value val)
    {
        if (x == null) return new Node(key, val, 1);
        int cmp = key.compareTo(x.key);
        if (cmp < 0) x.left = put(x.left, key, val);
        else if (cmp > 0) x.right = put(x.right, key, val);
        else x.val = val;
        x.N = size(x.left)   size(x.right)   1;
        return x;
    }
} 

這很簡單，Java因為我不需要處理參考。所以這是我的問題：

1. 我該如何解決這個不匹配的錯誤？
2. 該遞回函式的正確回傳型別put是 &Option<Box<Node<K, V>>>or Option<Box<Node<K, V>>>？有什么不同？
3. 我是否以正確的方式重寫此Java代碼？rust-analyzer 只報告這個不匹配的錯誤，但我不知道它是否會像我預期的那樣作業。老實說，當我處理 rust 中的參考時，我并不完全理解我在做什么，尤其是當它是 struct 或 enum 的參考時

學習 Rust 很難，因為我在系統編程語言方面沒有太多經驗，我感謝你們的幫助 :)

uj5u.com熱心網友回復：

最簡單的選擇是對節點進行可變參考：

impl<K: Ord, V> BST<K, V> {
    // ...

    fn put(&mut self, key: K, value: V) {
        put(&mut self.root, key, value)
    }
}

fn put<K: Ord, V>(node: &mut Option<Box<Node<K, V>>>, key: K, value: V) {
    match node {
        None => {
            *node = Some(Box::new(Node::new(key, value, 1)));
        }
        Some(real_node) => {
            if key < real_node.key {
                put(&mut real_node.left, key, value);
            } else {
                put(&mut real_node.right, key, value);
            }

            real_node.number_of_nodes = size(&real_node.right)   size(&real_node.left)   1;
        }
    }
}

注意我改變了鍵相等時的插入行為，因為在原始的 Rust 和 Java 代碼中，即使沒有插入新節點，存盤節點數量的變數也會增加。

或者，您可以按值獲取節點并回傳修改后的節點：

impl<K: Ord, V> BST<K, V> {
    // ...

    pub fn put(&mut self, key: K, value: V) {
        self.root = put(self.root.take(), key, value);
    }
}

fn put<K: Ord, V>(node: Option<Box<Node<K, V>>>, key: K, value: V) -> Option<Box<Node<K, V>>> {
    match node {
        None => Some(Box::new(Node::new(key, value, 1))),
        Some(mut real_node) => {
            if key < real_node.key {
                real_node.left = put(real_node.left, key, value);
            } else {
                real_node.right = put(real_node.right, key, value);
            }

            real_node.number_of_nodes = size(&real_node.right)   size(&real_node.left)   1;
            Some(real_node)
        }
    }
}

如果您還沒有閱讀 Rust 書的所有權和參考章節，我建議您閱讀。

標籤：爪哇算法锈二叉搜索树

上一篇：如何解決陣列問題以檢查元素是否大于、小于或等于其鄰居

下一篇：確定穿過網格中正方形的單條線的演算法