二叉查找树递归插入法在RUST中的实现

mepcadol  于 2022-11-12  发布在  其他
关注(0)|答案(1)|浏览(124)

我正在学习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)行,我得到一个错误:
不匹配的类型
需要枚举'选项框节点',但找到引用'&选项框节点'
我不知道如何修正这个问题,我试着将&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.如何修复不匹配的错误?
1.递归函数put&Option<Box<Node<K, V>>>Option<Box<Node<K, V>>>的正确返回类型是什么?有什么区别?
1.我重写Java代码的方法正确吗?rust-analyzer只报告了这个不匹配的错误,但我不知道它是否会像我期望的那样工作。老实说,我不完全理解我在rust-analyzer中处理引用时在做什么,尤其是当它是struct或enum的引用时
这是很难学习 rust ,因为我没有太多的经验,在系统编程语言,我感谢你们的帮助:)

toiithl6

toiithl61#

最简单的方法是使用一个对节点的可变引用:

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)
        }
    }
}

如果你还没有读过这本书的话,我建议你阅读一读。

相关问题