BST(0) - 二叉搜索树基础

Algorithm

January 14, 2023

作为一系列自平衡（self-balancing）的二叉搜索树的博文的起始，这篇先介绍基础部分，之后的各篇将专注于增/删节点后，树重新平衡的部分。

定义

二叉搜索树是二叉树，但是额外需要每个节点满足：左孩子（如果有的话）的 key 比它的小，而右孩子的 key 比它的大。

实现前言

考虑如何在实现上（Rust）把本文介绍的二叉搜索树的基础操作作为后面实现的具体种类的带自平衡的二叉搜索树的基础，也就是怎么用一种比较好的方式复用这些代码。

对于像 C++/C#/Java 风格的同时继承数据和行为的面向对象语言，可以使用同心圆套圈儿的 “继承“ 来复用代码。而对于 Rust 这种只有行为共享而没有数据共享的纯粹的抽象机制（Trait机制），由于不能对属性进行直接的访问，只能使用方法来访问属性，这会使实现的代码非常啰嗦（每次具体类型都需要实现一遍属性访问的方法）。另外一个问题在于由于对象需要放在堆上（避免定义上的循环引用和做对象的向上（upcast）或向下（downcast）地转换），实际上是使用 Rc<RefCell<Node>>，每次调用都要复杂解引用，这一点在前面 FibHeap 实现问题上已经讲过。

这里采取了完整包装（复杂包装）和重度使用宏机制来做代码复用。

完整包装

假定树的实际的内部节点为 Node_，包装器的节点为 Node ，为避免智能指针（Rc）造成的循环引用，还引入了包装器的弱引用版本 WeakNode，最后树结构为 Tree 。

内部节点 `Node_` 伪代码：

struct Node_ {
    left: Node,
    right: Node,
    paren: WeakNode,
    
    key,
    val
}

反向引用使用弱节点类型

包装的节点 `Node` 伪代码：

struct Node(Option<Rc<RefCell<Node_>>>)

包装器可能是一个实际的节点，或者是 none

弱引用的节点 `WeakNode`：

struct WeakNode(Option<Weak<RefCell<Node_>>>)

把强引用 Rc 替换成弱引用 Weak

树本身的结构：

struct Tree {
    root: Node
}

这种完整包装的优点在于可以完美地上位替代传统的基于指针结构的树结构的实现，但是肉眼可见地过于复杂，比如如果我们要访问节点 x 的左孩子：

x.0.clone().unwrap().as_ref().borrow().left

写这样出的代码简直是地狱！

好在可以用几乎完美的 Rust 宏来解决这件事

用宏抽象

关于使用宏来拓展语言的抽象机制主要有以下几个类别：

函数分发：函数根据参数个数进行函数分发；
代码 Mixin：定义语法 Item（结构体、函数、宏），实现方法；
嵌套压缩：省略掉每次固定的一长串儿连续的属性访问与方法调用

压缩包装

关于节点的访问的简化，是在前文 FibHeap 实现里面使用的那一套宏的升级。

访问与修改节点的指定属性的宏：

macro_rules! attr {
    ($node:expr, $attr:ident) => { 
        {
            /* to pass runtime borrow check  */
            if let Some(_unr) = $node.clone().0 {
                let _bor = _unr.as_ref().borrow();
                let _attr = _bor.$attr.clone();
                drop(_bor);
                _attr
            }
            else {
                panic!("Access {} on None", stringify!($attr));
            }
    	} 
    };
    ($node:expr, $attr:ident, $val:expr) => {
        {
            if let Some(bor) = $node.clone().0 {
                bor.as_ref().borrow_mut().$attr = $val
            }
            else {
                panic!("MAccess {} on None", stringify!($attr));
            }
    	}
    };
}

生成属性访问宏的宏：

由于从 API 设计的角度，部分属性需要使用指针来绕过生命周期的限制，从而返回引用，所以生成宏特制了这一部分

macro_rules! def_attr_macro {
    ($($name:ident),+) => {
        $(
            macro_rules! $name {
                ($node:expr) => {
                    attr!($$node, $name)
                };
                ($node:expr, $val:expr) => {
                    attr!($$node, $name, $$val)
                };
            }
            pub(crate) use $name;
        )+
    };
    (ptr | $($name:ident),+) => {
        $(
            macro_rules! $name {
                ($node:expr) => {
                    unsafe { &* attr!($$node, $name) }
                };
                ($node:expr, $val:expr) => {
                    attr!($$node, $name, $$val)
                };
            }
            pub(crate) use $name;

            concat_idents::concat_idents! (name_mut = $name, _mut {
                macro_rules! name_mut {
                    ($node:expr) => {
                        unsafe { &mut * attr!($$node, $name) }
                    };
                }
                pub(crate) use name_mut;
            });
        )+
    };
}

生成属性访问宏：

显然其中节点的 key 和 val 都是存储在堆上（通过 Box），节点里保存唯一的指针

def_attr_macro!(
    left, right, paren, height
);
def_attr_macro!(ptr | key, val);

堆上数据封装与解包的宏：

macro_rules! boxptr {
    ($v:expr) => {
        Box::into_raw(Box::new($v))
    };
}


macro_rules! unboxptr {
    ($ptr:expr) => {
        unsafe { *Box::from_raw($ptr) }
    };
}

对内部节点封装与解包：

macro_rules! node {
    (BST { $key:expr, $val:expr $(,$attr:ident : $attr_val:expr)* }) => {
        Node(Some(std::rc::Rc::new(std::cell::RefCell::new(Node_ {
            left: Node::none(),
            right: Node::none(),
            paren: WeakNode::none(),

            key: boxptr!($key),
            val: boxptr!($val),

            $(
                $attr: $attr_val
            ),*
        }))))
    };
    (FREE { $($attr:ident : $attr_val:expr),* }) => {
        Node(Some(std::rc::Rc::new(std::cell::RefCell::new(Node_ {
            $(
                $attr: $attr_val
            ),*
        }))))
    };
}


macro_rules! unwrap_into {
    ($node:expr) => {
        std::rc::Rc::try_unwrap($node.0.unwrap())
            .unwrap()
            .into_inner()
    };
}

辅助定义

实现内部节点：

macro_rules! impl_node_ {
    ({ $($name: ident : $ty: ty)* }) => {
        struct Node_<K, V> {
            left: Node<K, V>,
            right: Node<K, V>,
            paren: WeakNode<K, V>,

            key: *mut K,
            val: *mut V,

            /* extra attr */
            $(
                $name: $ty,
            )*
        }
        
        impl<K, V> Node_<K, V> {
            fn into_value(mut self) -> V {
                let oldval = self.val;
                self.val = std::ptr::null_mut();
                unboxptr!(oldval)
            }
        }
        
        impl<K, V> Drop for Node_<K, V> {
            fn drop(&mut self) {
                if !self.key.is_null() {
                    unboxptr!(self.key);
                }

                if !self.val.is_null() {
                    unboxptr!(self.val);
                }
            }
        }

        impl<K: Debug, V: Debug> std::fmt::Debug for Node_<K, V> {
            fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
                write!(f, "{:?}: {:?}", self.key, unsafe { &*self.val })
            }
        }
    };
}

注意，为了绕过对引用的生命周期的限制，采用了手动的方式管理内存，这意味着在节点解构方法上也要手动释放内存，而在返回值的时候也要对应把指针摆到 null 处避免 double free 的问题。

实现节点包装（强和弱）：

macro_rules! impl_node {
    () => {
        struct Node<K, V>(
            Option<std::rc::Rc<std::cell::RefCell<Node_<K, V>>>>,
        );

        /// Used for reverse reference to avoid circular-reference
        ///
        /// So we can easy auto drop
        struct WeakNode<K, V>(
            Option<std::rc::Weak<std::cell::RefCell<Node_<K, V>>>>,
        );

        impl<K, V> Node<K, V> {
            fn downgrade(&self) -> WeakNode<K, V> {
                WeakNode(
                    self.0.clone().map(|ref rc| std::rc::Rc::downgrade(rc)),
                )
            }

            #[allow(unused)]
            fn as_ptr(&self) -> *mut Node_<K, V> {
                match self.0 {
                    Some(ref rc) => rc.as_ptr(),
                    None => std::ptr::null_mut(),
                }
            }

            fn none() -> Self {
                Self(None)
            }

            fn is_some(&self) -> bool {
                self.0.is_some()
            }

            fn is_none(&self) -> bool {
                self.0.is_none()
            }

            #[allow(unused)]
            fn replace_val(&mut self, x: Node<K, V>) -> V {
                let oldvptr = attr!(self, val);
                attr!(self, val, attr!(x, val).clone());

                unboxptr!(oldvptr)
            }

            fn rc_eq(&self, other: &Self) -> bool {
                match self.0 {
                    Some(ref rc1) => {
                        if let Some(ref rc2) = other.0 {
                            std::rc::Rc::ptr_eq(rc1, rc2)
                        } else {
                            false
                        }
                    }
                    None => other.is_none(),
                }
            }
        }


        impl<K, V> Default for Node<K, V> {
            fn default() -> Self {
                Self::none()
            }
        }


        impl<K, V> Clone for Node<K, V> {
            fn clone(&self) -> Self {
                Self(self.0.clone())
            }
        }


        impl<K, V> PartialEq for Node<K, V> {
            fn eq(&self, other: &Self) -> bool {
                self.rc_eq(other)
            }
        }


        impl<K, V> Eq for Node<K, V> {}


        impl<K, V> WeakNode<K, V> {
            fn upgrade(&self) -> Node<K, V> {
                Node(self.0.clone().map(|weak|
                    if let Some(strong) = weak.upgrade() {
                        strong
                    }
                    else {
                        unreachable!("weak node upgrade failed")
                    }
                ))
            }

            fn none() -> Self {
                Self(None)
            }

            fn is_none(&self) -> bool {
                self.0.is_none()
            }
        }


        impl<K, V> Clone for WeakNode<K, V> {
            fn clone(&self) -> Self {
                Self(self.0.clone())
            }
        }
    };
}

实现树：

macro_rules! def_tree {
    (
        $(#[$attr:meta])*
        $treename:ident { $(
            $(#[$field_attr:meta])*
            $name: ident : $ty: ty),*
        }
    ) =>
    {
        $(#[$attr])*
        #[derive(Debug)]
        #[allow(unused)]
        pub struct $treename<K, V> {
            root: Node<K, V>,

            /* extra attr */
            $(
                $(#[$field_attr])*
                $name: $ty
            ),*
        }
    }
}


macro_rules! impl_tree_debug {
    ($treename:ident) => {
        impl<K: Ord, V> $treename<K, V> {
            pub fn debug_write<W: std::fmt::Write>(
                &self,
                f: &mut W
            ) -> std::fmt::Result
            where K: std::fmt::Debug, V: std::fmt::Debug
            {
                /* print header */

                writeln!(f, "{self:?}")?;


                /* print body */

                if self.root.is_none() {
                    return Ok(());
                }

                let mut this_q = crate::vecdeq![self.root.clone()];
                let mut lv = 1;

                while !this_q.is_empty() {
                    writeln!(f)?;
                    writeln!(f, "############ Level: {lv} #############")?;
                    writeln!(f)?;

                    let mut nxt_q = crate::vecdeq![];

                    while let Some(x) = this_q.pop_front() {
                        if left!(x).is_none() && right!(x).is_none() {
                            write!(f, "{x:?}")?;
                        }
                        else {
                            write!(f, "{x:?} | L-> ")?;

                            let left = left!(x);
                            if left.is_some() {
                                write!(f, "{left:?}")?;
                                nxt_q.push_back(left);
                            }
                            else {
                                write!(f, "nil")?;
                            }

                            write!(f, "; R-> ")?;

                            let right = right!(x);
                            if right.is_some() {
                                write!(f, "{right:?}")?;
                                nxt_q.push_back(right);
                            }
                            else {
                                write!(f, "nil")?;
                            }
                        }

                        writeln!(f)?;
                    }

                    this_q = nxt_q;
                    lv += 1;
                }

                writeln!(f, "------------- end --------------\n")?;

                Ok(())
            }


            pub fn debug_print(&self) where K: std::fmt::Debug, V: std::fmt::Debug
            {
                let mut cache = String::new();

                self.debug_write(&mut cache).unwrap();

                println!("{cache}")
            }
        }
    };
}


macro_rules! impl_tree {
    (
        $(#[$attr:meta])*
        $treename:ident {
            $(
                $(#[$field_attr:meta])*
                $name: ident : $ty: ty
            ),*
        }
    ) =>
    {
        def_tree!(
            $(#[$attr])*
            $treename {
                $(
                    $(#[$field_attr])*
                    $name : $ty
                ),*
            }
        );
        impl_tree_debug!($treename);

        impl<K: Ord, V> $treename<K, V> {
            pub fn get<Q>(&self, k: &Q) -> Option<&V>
            where K: std::borrow::Borrow<Q>, Q: Ord + ?Sized
            {
                let x = bst_search!(self.root, k);

                if x.is_some() {
                    Some(val!(x))
                }
                else {
                    None
                }
            }

            pub fn get_mut<Q>(&mut self, k: &Q) -> Option<&mut V>
            where K: std::borrow::Borrow<Q>, Q: Ord + ?Sized
            {
                let x = bst_search!(self.root, k);

                if x.is_some() {
                    Some(val_mut!(x))
                }
                else {
                    None
                }
            }
        }

    };
}

对树的实现宏分为三个宏是为了方便后面不同树种的灵活使用。

这里在树的实现里的 get 方法，有 Trait 条件 where K: Borrow<Q>, Q: Ord + ?Sized ，这也是 Rust 标准库里对于数据结构的 get 方法普遍采取的约束条件。

在这里有必要说明一下关于 Borrow 与 AsRef 的区别有，这两个广泛使用的类型表示的 Trait 有相同的签名：

pub trait Borrow<Borrowed>
where
    Borrowed: ?Sized,
{
    fn borrow(&self) -> &Borrowed;
}


pub trait AsRef<T>
where
    T: ?Sized,
{
    fn as_ref(&self) -> &T;
}

实现了上面的 Trait 比如 Borrow 就有 K: Borrow<Q> => K.borrow(): &Q

常见的都实现了两个 Trait 的比如 String -> &str , PathBuf -> &Path

这两个 Trait 的区别在于：

Borrow 有一个对于 T 的笼统类型实现（blanket implementation）：

impl<T> Borrow<T> for T 
where 
   T: ?Sized

这让我们可以直接把 &K 作为 K.borrow() 的返回类型，而 AsRef 由于类型系统的限制（为了避免另一个用于自动解引用的 blanket implementation 的重叠）

impl<T, U> AsRef<U> for &T
where
    T: AsRef<U> + ?Sized,
    U: ?Sized,

这个笼统实现是说任何 T.as_ref() -> &U 都有 &T.as_ref() -> &U ，但其中 AsRef<U> 与 AsRef<T> 存在语义重叠的部分，而现有的类型系统没法儿进行区分

Borrow 需要保证 Hash, Eq, Ord 与原类型的一致性

对以上用于压缩包装和辅助定义的宏的具体用例不清楚的，可以参考后续的关于具体自平衡二叉搜索树介绍的博文

错误定位

重度使用宏的编码方式的最大的问题在于，对几乎所有已知的编程语言，缺乏系统完整好用的调试手段，这是有待发展的领域，特别考虑到很多上世纪90年代创建的主流语言根本就没有宏机制。

对于 Rust 宏代码最大问题在于无法准确定位宏中的错误和 Debug ，宏展开后的代码没法能还原为在原宏中的位置。

所以为了缓解这个问题，需要我们手动的插入锚点，当调用失败的时候打印错误信息。

辅助方法

左右方向

不管是左右孩子还是左右旋转，都需要一个指示方向是左还是右的结构

#[derive(Clone, Copy, PartialEq, Eq, Debug)]
pub(crate) enum Dir {
    Left,
    Right,
}
pub(crate) use Dir::*;


impl Dir {
    fn rev(&self) -> Self {
        match self {
            Left => Right,
            Right => Left,
        }
    }

    fn is_left(&self) -> bool {
        matches!(self, Left)
    }
}

访问孩子

macro_rules! child {
    ($p:expr, $dir:expr) => {
        if $dir.is_left() {
            left!($p)
        }
        else {
            right!($p)
        }
    };
}

连接孩子

需要注意使用中会出现可能孩子或父母都是 none 的情况

macro_rules! conn_child {
    ($paren:expr, $child: expr, $dir:expr) => { {
        let child = $child.clone();
        let paren = $paren.clone();
        let dir = $dir;

        debug_assert!(!child.rc_eq(&paren));

        if paren.is_some() {
            if dir.is_left() {
                attr!(paren, left, child.clone());
            }
            else {
                attr!(paren, right, child.clone());
            }

            if child.is_some() {
                paren!(child, paren.downgrade());
            }
        }
    } };
}


macro_rules! conn_left {
    ($paren:expr, $child: expr) => {
        conn_child!($paren, $child, Left)
    };
}


macro_rules! conn_right {
    ($paren:expr, $child: expr) => {
        conn_child!($paren, $child, Right)
    };
}

索引孩子的方向

根据引用的相等性判断一个节点的孩子是它的左孩子还是右孩子

macro_rules! index_of_child {
    ($paren:expr, $child:expr) => {
        {
            let paren = &$paren;
            let child = &$child;

            if left!(paren).rc_eq(child) {
                Left
            } else if right!(paren).rc_eq(child) {
                Right
            } else {
                unreachable!()
            }
    	}
    };
}

断开连接

macro_rules! disconn {
    ($paren:expr, $child: expr) => {
        {
            let child = $child.clone();
            let paren = $paren.clone();

            if child.is_some() && paren.is_some() {
                let dir = index_of_child!(paren, child);

                if dir.is_left() {
                    left!(paren, Node::none());
                }
                else {
                    right!(paren, Node::none());
                }

                paren!(child, WeakNode::none());
            }
        }
    };
}

替换节点

这个操作可以称为：subtree_shift 或者 transplant ，就是把一个节点 u 从它的父节点那里替换为另一个节点 v 。

这需要检查节点 u ，如果是根节点，直接替换根节点，这时注意

替换的节点 v 的父节点仍然需要设置（设置为 none），因为有时要检查父节点是否为 none 来判断是否为根节点；
当 u 为根节点时设置 v 的父节点时仍然需要检查 v 是否为 none

macro_rules! subtree_shift {
    ($tree:expr, $u:expr, $v:expr) => {
        {
            let tree = &mut *$tree;
            let u = $u.clone();
            let v = $v.clone();

            if paren!(u).is_none() {
                if v.is_some() {
                    paren!(v, WeakNode::none());
                }

                tree.root = v;
            } else {
                let paren = paren!(u).upgrade();
                
				conn_child!(paren, v, index_of_child!(paren, u));
            }
    	}
    };
}

最小 vs 最大

/// Leftmost
macro_rules! bst_minimum {
    ($x:expr) => {
        {
            let mut x = $x.clone();

            while left!(x).is_some() {
                x = left!(x);
            }

            x
    	}
    };
}


/// Right most
macro_rules! bst_maximum {
    ($x:expr) => {
        {
            let mut x = $x.clone();

            while right!(x).is_some() {
                x = right!(x);
            }

            x
    	}
    };
}

最小/最大一个是用于前驱/后继的查询，还可以用在从一个有序的数据集里快速构建搜索二叉树的时候（这时候每次插入节点时可以跳过逐层比较，直接找到最大值，插入它的右节点）

前驱 vs 后继

Predecessor

该节点有左孩子，那么显然是左孩子（做为根的树）的最大值就是直接前驱；

否则，向上查询，如果节点恰好是是父节点的右孩子，那么父节点就是直接前驱，否则一路到根为止，向上 Left-most ，直到一个是右孩子关系是父节点，这样要么找到一个节点，要么返回一个 none 节点

Successor

该节点有右孩子，那么显然是右孩子（做为根的树）的最小值就是直接后继；

否则，向上 Right-most 直到一个左孩子关系的节点或者返回一个 none 节点

/// Return predecessor-node or none-node
macro_rules! bst_predecessor {
    ($x: expr) => {
    {
        let mut x = $x.clone();

        /* child: left, right-most */
        if left!(x).is_some() {
            bst_maximum!(left!(x))
        }
        /* paren: left-most-up, right */
        else {
            let mut y = paren!(x).upgrade();

            while y.is_some() && x.rc_eq(&left!(y)) {
                x = y;
                y = paren!(y).upgrade();
            }

            y
        }
    }
    };
}


/// Return successor-node or none-node
macro_rules! bst_successor {
    ($x: expr) => {
    {
        let mut x = $x.clone();

        /* child: right, left-most */
        if right!(x).is_some() {
            bst_minimum!(right!(x))
        }
        /* paren: right-most-up, left */
        else {
            let mut y = paren!(x).upgrade();

            while y.is_some() && x.rc_eq(&right!(y)) {
                x = y.clone();
                y = paren!(y).upgrade();
            }

            y
        }
    }
    };
}

基础操作

递归 vs 展开

关于二叉搜索树的基础操作实现有递归的版本和展开的版本，传统上认为，递归的版本由于存在函数栈展开时的开销（保存/恢复上下文），在时间效率上总是不如展开的版本，但实际上由于现代编译器的优化，情况可能相反。

比如在 C++ OJ 测试的时候，（插入新节点时）递归版本实际更快一点。

由于递归的实现总是很简单，这里重点列出展开版本的代码

搜索

显然就是简单的二叉搜索，直到找到匹配的 key 或者节点耗尽

macro_rules! bst_search {
    ($x: expr, $k: expr) => {
        {
            let mut x = $x.clone();
            let k = $k;

            while x.is_some() && k != key!(x).borrow() {
                if k < key!(x).borrow() {
                    x = left!(x);
                } else {
                    x = right!(x);
                }
            }

            x
    	}
    };
}

插入

先查询节点，直达找到同 key 的节点或者等下一层节点耗尽；
同 key 节点更新，不同 key 按照大小关系插入，需要特别考虑根节点为空的情况

/// Return Option<V>
macro_rules! bst_insert {
    ($tree: expr, $z: expr) => {
	{
        use std::cmp::Ordering::*;

        let mut y = Node::none();
        let mut x = $tree.root.clone();
        let z = $z;

        while !x.is_none() {
            y = x.clone();

            match key!(z).cmp(key!(x)) {
                Less => {
                    x = left!(x);
                }
                Equal => {
                    break;
                }
                Greater => {
                    x = right!(x);
                }
            }
        }

        if y.is_none() {
            $tree.root = z;
            None
        } else {
            match key!(z).cmp(key!(y)) {
                Less => {
                    conn_left!(y, z);
                    None
                }
                Equal => Some(y.replace_val(z)),
                Greater => {
                    conn_right!(y, z);
                    None
                }
            }
        }
    }
	};
}

删除

相对复杂的一个操作，最后返回（可选地）需要执行重平衡操作的起始节点。

如果节点的左孩子或右孩子为空，直接用不为空的那一个孩子代替被删除的节点（这时重平衡的点就是被删节点的父节点）；

如果节点的孩子都不为空，就找它的直接后继，这又要分两种情况：

如果被删节点的右孩子没有左孩子，也就是右孩子本身就是直接后继，这样直接做右孩子对被删节点的 subtree-shift ，然后右孩子的左枝连接到被删节点的左孩子（重平衡点为右孩子）；
如果右孩子有左孩子，那么直接后驱就是右孩子的 Left-most 假设为 y，这样相比第一种情况，首先还要额外处理 y 节点的右孩子的（Left-most 没有左孩子），subtree-shift(y, y.right) 。

/// Return retracing node
macro_rules! bst_delete {
    ($tree: expr, $z: expr) => { {
        let tree = &mut *$tree;
        let z = $z.clone();

        if left!(z).is_none() {
            subtree_shift!(tree, z, right!(z));
        } else if right!(z).is_none() {
            subtree_shift!(tree, z, left!(z));
        } else {
            /* case-1       case-2

                 z            z
                  \            \
                   y            z.right
                               /
                              / (left-most)
                             y
                              \
                              y.right
            */

            let y = bst_successor!(z);

            if !right!(z).rc_eq(&y) {
                subtree_shift!(tree, y, right!(y));
                conn_right!(y, right!(z));
            }

            subtree_shift!(tree, z, y);
            conn_left!(y, left!(z));
        }
    } };
}

惰性插/查/删

对于一些没有严格平衡因素约束的二叉搜索树，可以采用另一种删除的方式，就是删除时只标记节点，当被标记的节点到达阈值时，重构整棵树，典型的比如 替罪羊树（Scapegoat Tree）。

这样的话，当插入同 key 的新节点时可以恢复旧的被删节点，而查询时要排除被标记的节点。

扁平化

中序遍历树的某个子树，得到一个顺序化表示的子树的节点列表

/// In-order Traversals
macro_rules! bst_flatten {
    ($z: expr) => { {
        let mut x = $z;
        let mut stack = vec![];  // paths
        let mut nodes = vec![];

        debug_assert!(x.is_some());

        'outter: loop {
            while left!(x).is_some() {
                stack.push(x.clone());
                x = left!(x);
            }

            nodes.push(x.clone());

            while right!(x).is_none() {
                if let Some(p) = stack.pop() {
                    x = p;
                    nodes.push(x.clone());
                }
                else {
                    break 'outter
                }
            }

            x = right!(x);
        }

        for x in nodes.iter() {
            paren!(x, WeakNode::none());
            left!(x, Node::none());
            right!(x, Node::none());
            x.flatten_cleanup();
        }

        nodes
    } }
}

建构树

按照二分的思路，从一个有序列表上建构一棵平衡的二叉搜索树。

macro_rules! bst_build {
    ($nodes: expr) => { {
        fn bst_build_<K, V>(nodes: &[Node<K, V>]) -> Node<K, V> {
            let lo = 0;
            let hi = nodes.len();

            if lo == hi {
                return Node::none();
            }

            let mid = (hi + lo) / 2;

            let left = bst_build_(&nodes[lo..mid]);
            let right = bst_build_(&nodes[mid+1..hi]);

            let p = nodes[mid].clone();

            conn_left!(p, left);
            conn_right!(p, right);

            p.build_cleanup();

            p
        }

        bst_build_($nodes)
    } };
}

自平衡基础

二叉搜索树自平衡的基础是树的旋转（rotation），从模式上，又可以分为单旋和双次单旋，从方向上又可以分为左和右。

单旋

旋转的作用在于在保持 key 的大小关系的情况下调整某左右树的树高差距。如果右树过高，就向左旋转；如果左树过高，就向右旋转。

旋转完成后，根据不同种类的自平衡二叉树的需要，执行定制的用于收尾更新的 rotate_cleanup 操作，传入参数是旧的根 x 和旋转后新的根 z 。

以左旋为例子，根节点 x 变为左孩子，而让 x 的右孩子 z 变为根节点；源 z 的左孩子变为 x 的右节点；

右旋则是一个镜像相反的过程

/// Simple Rotation (return new root)
/// ```no_run
///            left rotate
///    x       =========>           z
///  /  \                          / \
/// t1   z                        x   t4
/// |   / \                      / \   |
///   t23 t4                    t1 t23 |
///     |  |                     |   |
///        |
///            right rotate
///     x      ==========>           z
///   /  \                         /   \
///  z    t4                      t1    x
/// /  \   |                      |    /  \
///t1 t23                         |  t23  t4
/// |  |                              |    |
/// |
/// ```
///
macro_rules! rotate {
    ($tree: expr, $x: expr, $rotation: expr) => { {
        let tree = &mut *$tree;
        let x = $x.clone();
        let rotation = $rotation;

        let z = child!(x, rotation.rev());
        let t23 = child!(z, rotation);

        conn_child!(x, t23, rotation.rev());
        subtree_shift!(tree, x, z);
        conn_child!(z, x, rotation);

        tree.rotate_cleanup(x, z.clone());

        z
    } };
}

从模式上讲，当根节点 x 比较高的子树 y 的方向（左或右）与 y 较高子树的方向一致，只需要做一次单旋。

但如果不是这样呢，也就是两个较高子树的方向相反，就需要两次旋转，先在较高子树上旋转，使得两个较高子树的方向一致，然后再在根节点上旋转。

双旋

假设根节点 x 较高的子树 z 是 x 的右子树，而 z 的较高子树 y 是 z 的左子树：

先以 z 为根，向右旋转，结果是 y 代替了 z ，而 z 成了 y 的右孩子，于是根为 x 的树变成了都是右子树较高；
以 x 为根，向左旋转，旋转完成

/// Double Rotation (return new root)
/// ```no_run
///             rotate [right]-left         rotate right-[left]
///    x        =========>         x        =========>       y
///  /   \                        /  \                      / \
/// t1    z                      t1   y                    x   z
/// |   /  \                     |   / \                  / \ / \
///    y   t4                      t2   z                t1 t2t3t4
///   / \   |                       |  / \                |  | | |
///  t2 t3                            t3 t4
///   |  |                            |   |
/// ```
macro_rules! double_rotate {
    ($tree: expr, $x: expr, $snd_rotation: expr) => {
    {
        let tree = &mut *$tree;
        let x = $x.clone();
        let snd_rotation = $snd_rotation;

        let z = child!(x, snd_rotation.rev());
        rotate!(tree, z, snd_rotation.rev());
        rotate!(tree, x, snd_rotation)
    }
    };
}

简单测试

其中 balance_validation 是每个特例定制的平衡校验方法

#[cfg(test)]
macro_rules! test_dict {
    ($dict: expr) => {
        let get_one = || {
            rand::random::<u64>()
        };

        for _ in 0..20 {
            let mut dict = $dict;
            let batch_num = 1000;
            let mut elems = vec![];
            let mut keys = std::collections::HashSet::new();

            /* Verify Create */

            let mut i = 0;

            while i < batch_num {
                let k = get_one();
                let v = k + 1000;

                if keys.contains(&k) {
                    continue;
                }

                keys.insert(k);
                elems.push((k, v));

                assert!(dict.insert(k, v).is_none(), "insert res invalid");
                assert_eq!(dict.get(&k), Some(&v), "insert query failed");

                // println!("{i}. insert: ");

                i += 1;
            }

            dict.balance_validation();

            /* Verify Update */

            for i in 0..batch_num {
                let (k, v) = elems[i];

                assert_eq!(dict.get(&k), Some(&v));

                let newv = k + 500;

                assert_eq!(dict.insert(k, newv), Some(v));
                elems[i] = (k, newv);

                assert_eq!(dict.get(&k), Some(&newv));
            }


            /* Verify Remove */

            use rand::{prelude::SliceRandom, thread_rng};

            elems.shuffle(&mut thread_rng());

            for i in 0..batch_num {
                let (k, v) = elems[i];

                assert_eq!(dict.get(&k), Some(&v), "[dict remove] Assure get Some");
                assert_eq!(dict.remove(&k), Some(v), "[dict remove] Assert remove failed");
                assert_eq!(dict.get(&k), None, "[dict remove] Assure get None");

                // sample to save time
                if i % 10 == 0 {
                    dict.balance_validation();
                }
            }

        }
    };
}

后续

接下来介绍具体的自平衡二叉搜索树：

AVL树；
Red-black树（简称 RB Tree）：
1. 原始红黑树
2. 左偏红黑树 （Left-leaning Red-black Tree， LLRB）
3. AA树
替罪羊树（（Lazy）Scapegoat Tree）；
伸缩树（Splay Tree）；
树堆 (Treap)