我正在实现BST(二进制搜索树)、RBT(红黑树)和AVLT(AVL树)。我写了一个BST如下：
use std::cell::RefCell;
use std::rc::Rc;
use std::cmp::max;
type RcRefBaseNode<T> = Rc<RefCell<BaseNode<T>>>;
type BaseNodeLink<T> = Option<RcRefBaseNode<T>>;
struct BaseNode<T: Ord> {
pub key: T,
left: BaseNodeLink<T>,
right: BaseNodeLink<T>,
}
struct BaseTree<T: Ord> {root: BaseNodeLink<T>}
impl<T: Ord> BaseTree<T> {
fn new(data: T) -> Self {
Self{
root: Some(Rc::new(RefCell::new(BaseNode{
key: data,
left: None,
right: None
})))
}
}
fn is_empty(&self) -> bool {
match self.root {
None => false,
Some(_) => true
}
}
fn height(&self) -> usize {
match &self.root {
None => 0,
Some(node) => node.borrow().height(),
}
}
fn print_in_order(&self) {
unimplemented!()
}
fn count_leaves(&self) {
unimplemented!()
}
}
impl <T: Ord> BaseNode<T> {
fn height(&self) -> usize {
let left_height: usize;
match &self.left {
None => left_height = 0,
Some(node) => left_height = node.borrow().height(),
};
let right_height: usize;
match &self.right {
None => right_height = 0,
Some(node) => right_height = node.borrow().height(),
};
max(left_height, right_height) + 1
}
fn print_in_order(&self) {
unimplemented!()
}
fn count_leaves(&self) -> usize {
unimplemented!()
}
// other functions for querying
}
将有更多的方法来查询有关该树的信息。我意识到RBT和AVLT的查询函数将与BST的查询函数相同
// ============== Red-Black Tree ============== //
type RcRefRBTNode<T> = Rc<RefCell<RedBlackTreeNode<T>>>;
type RBNodeLink<T> = Option<RcRefRBTNode<T>>;
#[derive(Clone, Debug, PartialEq)]
enum NodeColor {
Red,
Black,
}
struct RedBlackTreeNode<T> {
pub key: T,
pub color: NodeColor,
parent: RBNodeLink<T>,
left: RBNodeLink<T>,
right: RBNodeLink<T>,
}
struct RedBlackTree<T: Ord> {root: RBNodeLink<T>}
// same implementation for query functions like is_empty, height, count_leaves, etc.
和
// ============== AVL Tree ============== //
type RcRefAVLTNode<T> = Rc<RefCell<AVLTreeNode<T>>>;
type AVLNodeLink<T> = Option<RcRefAVLTNode<T>>;
struct AVLTreeNode<T> {
pub key: T,
pub height: usize,
parent: AVLNodeLink<T>,
left: AVLNodeLink<T>,
right: AVLNodeLink<T>,
}
struct AVLTree<T: Ord> {root: AVLNodeLink<T>}
// same implementation for query functions like is_empty, height, count_leaves, etc.
我知道他们对insert和delete会有不同的代码，但如何为查询函数重用这些代码？
您可以将可查询节点的概念提取到一个trait中，然后使用它写入高度，然后为每个节点类型实现该trait。
例如，height函数只使用左成员和右成员，但traits不能访问成员，只能访问函数，所以我们需要一些访问器函数。您的其他查询函数可能意味着您需要为此添加更多函数。
trait QueryableTreeNode {
fn left(&self) -> &Option<Rc<RefCell<Self>>>;
fn right(&self) -> &Option<Rc<RefCell<Self>>>;
}
现在，高度函数可以使用这个特性重写
fn height<QTN: QueryableTreeNode>(qn:&QTN) -> usize {
let left_height = match &qn.left() {
None => 0,
Some(node) => height(&*node.borrow()),
};
let right_height = match &qn.right() {
None => 0,
Some(node) => height(&*node.borrow()),
};
max(left_height, right_height) + 1
}
接下来，我们让我们的节点类型实现特征
impl <T:Ord> QueryableTreeNode for BaseNode<T> {
fn left(&self) -> &BaseNodeLink<T> { return &self.left; }
fn right(&self) -> &BaseNodeLink<T> { return &self.right; }
}
impl <T:Ord> QueryableTreeNode for AVLTreeNode<T> {
fn left(&self) -> &AVLNodeLink<T> { return &self.left; }
fn right(&self) -> &AVLNodeLink<T> { return &self.right; }
}
最后，我们在树类型中实现该功能，方法是将节点上的新功能移交给
impl<T> BaseTree<T> {
fn height(&self) -> usize {
match &self.root {
None => 0,
Some(node) => height(&*node.borrow()),
}
}
}
你可以在操场上找到它的编译版本。
我将在这里尝试回答一个与Rust中的代码重用有关的更一般的问题。如果你的主要目标是写尽可能少的代码，那么Rust可能不是你想要的工具。
也就是说，您应该考虑三种主要方法：单形态化、虚拟化和枚举。
根据Rust书籍：
单态化是通过填充编译时使用的具体类型，将泛型代码转换为特定代码的过程。
您将使用单形态化进行一些复制/粘贴。然后就是虚拟化。在Rust中，这通常意味着使用特征对象。
最后，我们有枚举。我喜欢列举某些任务。使用enum，您可以指定一些顶级类型，如Tree，然后枚举要构建的树的种类。
这里有一个例子：
struct AVLTree;
struct BSTTree;
enum Tree {
AVL(AVLTree),
BST(BSTTree),
}
fn traverse(tree: Tree) {
match tree {
Tree::AVL(avl) => traverse_avl(avl),
Tree::BST(bst) => traverse_bst(bst),
}
}
fn traverse_avl(tree: AVLTree) {}
fn traverse_bst(tree: BSTTree) {}
抛开你的评论和对必须复制/粘贴代码的担忧，我可以看出上面的解决方案并不是你想要的。
使用虚拟化可以完成您想要做的事情，但这会让您付出代价。这里有一个资源描述了rust中大量的代码重用方法(以及一个优点/缺点列表)。
现在，我将继续讨论代码重用这一更一般的主题。编写代码就是做出选择，做出权衡。重用代码是指重用资源–时间、能量、逻辑等。
而"；不要重复你自己"(DRY)通常是一条很好的规则，有时它是有保证的，有时。。。你明白了。重用代码和以DRY方式编码也可能是代码质量的标志。
就是这样。DRY代码可以是代码质量的标志，就是这样。注意，我没有说好或坏质量。只是质量。有时候重用是件好事，有时候又是件坏事。有时它会产生可维护的代码。有时它会导致代码难以维护。
有时最容易维护的代码是可以轻松复制、粘贴和/或删除的代码。
泛型编程中的一种常见模式是，当您有几个部分共享的类型时，将共享部分放入泛型类型中，并在其类型参数中放入唯一部分(这可能是满足某些特性所必需的)。
您有三个结构：BaseTree、AvlTree和RedBlackTree。它们在树的平衡方式上有所不同"平衡"；是一种行为，所以让我们制作一个包含平衡特定类型树的代码的特性：
trait Balance {
type Data; // extra data that each node must store to balance the tree
fn insert_balanced<T>(&self, root: &mut Link<T, Self>, value: T);
}
(在本例中，我只考虑insert_balanced；在实际代码中，您可能希望添加remove_balanced，再加上其他可平衡的操作，如retain、union、intersection、split等。无论与API相关，您都希望在其上提供共享接口。)
以下是我们的Node和BaseTree类型：
struct Node<T, B: ?Sized + Balance> {
value: T,
balance_data: B::Data,
left: Link<T, B>,
right: Link<T, B>,
}
type Link<T, B> = Option<Box<Node<T, B>>>;
struct BaseTree<T, B: Balance> {
root: Link<T, B>,
// Putting the balancer as an actual field of the struct allows you to defer
// the choice of balancer to runtime, like in `BaseTree<T, Box<dyn Balance>>`
balancer: B,
}
现在，您可以在BaseTree<_, _>上编写所有二进制搜索树通用的算法，对于需要特殊逻辑的算法，请参阅balancer:
impl<T, B: Balance> BaseTree<T, B> {
fn search(&self, _value: &T) -> Option<&T> {
// Here write code to traverse the binary search tree ignoring the balancing part
todo!()
}
fn insert(&mut self, value: T) {
// Here defer to the implementation of `insert_balanced` for `B`
self.balancer.insert_balanced(&mut self.root, value)
}
}
实现一种特定类型的自平衡树需要创建一个实现Balance的类型并用它参数化BaseType。最简单的是一个简单的二进制搜索树，它不包含平衡代码：
struct NoBalancer {}
impl Balance for NoBalancer {
type Data = (); // unbalanced trees require no extra data
fn insert_balanced<T>(&self, _root: &mut Link<T, Self>, _value: T) {
todo!() // code to just insert with no balancing at all
}
}
type BinarySearchTree<T> = BaseTree<T, NoBalancer>;
(操场上有三种树的树桩。)
这类似于策略模式的静态调度版本。实现Balance的类型是一种平衡策略。在这种情况下，模式主要不是用于允许对策略进行运行时调度(尽管您可以这样做)，而是用于分离平衡的代码和不关心平衡的代码，以便后者可以重用。