红黑树的一种变体——AA树
简介Arne Andersson(也是AA树名字由来)在1993年发明了这种数据结构(原paper在这儿,内含Pascal实现),简化了$\color{red}{\text{红}}\color{black}{\text{黑}}$树繁琐的调整,同时效率也有保证颜色限制每个点要么是红色要么是黑色根节点为黑色如果一个节点是红色,那么它的子节点一定是黑色对于任意节点,从其到叶节点的任意路径上黑色节点的数量
一种对区间查找树的递归转循环方法
最近在写BVH树的时候由于并行计算对递归的不友好,故只能找一种非递归方式替代我很肯定这个东西有它自己的名字，而且估计五十年前就已经被发现了，但我没找到相应资料(Upd:翻了我三年前的B乎收藏夹,好像是叫morris遍历?🤔,22.05.09)概述思路很简单.每次要么走第一个子节点(对于二叉树就是左节点),要么走祖先节点中最近且仍有子节点未访问的节点的这个未访问的节点,这是可以通过预处理出来的对比除