rust - 如何重用二进制搜索树，红黑树和AVL树的代码？

Question

我正在实现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的查询函数相同。 RBT和AVLT的结构如下:

// ============== 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会有不同的代码，但是如何为查询功能重用这些代码？

Answer 1

您可以将可查询节点的概念提取为特征，然后使用该特征编写高度，然后为每种节点类型实现该特征。
例如，height函数仅使用左成员和右成员-但是特征不能访问成员，只能访问函数-因此我们需要一些访问器函数。您的其他查询功能可能意味着您需要为此添加更多功能。

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

您可以在playground中找到其编译版本。