概述

最近研究ceph中的crush算法，发现其tree型bucket所使用的一种以前没见过的结构，画了画发现是中序遍历的样子，论文原文是这样介绍的：

The bucket’s binary tree nodes are labeled with binary values using a simple, fixed strategy designed to avoid label changes when the tree grows or shrinks. The leftmost leaf in the tree is always labeled “1.” Each time the tree is expanded, the old root becomes the new root’s left child, and the new root node is labeled with the old root’s label shifted one bit to the left (1, 10, 100, etc.). The labels for the right side of the tree mirror those on the left side except with a “1” prepended to each value. A labeled binary tree with six leaves is shown in Figure 4. This strategy ensures that as new items are added to (or removed from) the bucket and the tree grows (or shrinks), the path taken through the binary tree for any existing leaf item only changes by adding (or removing) additional nodes at the root, at the beginning of the placement decision tree. Once an object is placed in a particular subtree, its final mapping will depend only on the weights and node labels within that subtree and will not change as long as that subtree’s items remain fixed....

大概作用就是保证已有节点的位置不变，树扩大时可以直接成倍扩容等。

我看了代码发现具体实现上还是不尽完美，于是在这里稍微整理下这种用法。

中序遍历的结构特点

可以发现很多性质：

叶子都是奇数，奇数都是叶子

这点非常好用，假设我们用它来实现线段树，那么我们关注的就是叶子，而这条性质可以通过2*i+1快速定位到叶子节点，zkw线段树是先找好起点再定位，但是zkw线段树不能随意的扩容。

每层的节点lowbit值相同

lowbit是树状数组里提到的概念，就是取数字的最后一位1，例如6=110，lowbit(6)=10=2。

很容易发现这种树形结构的底层lowbit为1，上一层为2，然后是4......//也就是第一层是1的倍数，第二层是2的倍数.....

标准的平衡树

这种树结构看起来就是非常标准的平衡二叉树，左小右大，高度平衡。

//中序遍历的结果

具体操作

我们假定树的大小是size，则size一定是2^n-1，我们规定一个点的高度h(x)=lowbit(x)

树根

中序遍历的完全二叉树，树根一定是(size+1)/2,即root=2^(n-1)

反之，若树根是root，则size=root*2-1

树的大小

其实很容易发现树根的值就是叶子的个数，而树根又是2的次幂，所以只要找到第一个大于等于需要叶子树的2的次幂作根即可

子节点

观察总结后发现:

左儿子=x-h(x)/2右儿子=x+h(x)/2那么定位到子节点就很容易了：lson(x)=x-(h(x)>>1)rson(x)=x+(h(x)>>1)

左？右？

由上一条结论很容易知道，右儿子节点比左儿子节点多个h(father)=h(x)<<1

那就很容易判定了：is_left=!(x&(h(x)<<1))

父节点

由上两条已经很清楚了：

lson_father=x+h(x)rson_father=x-h(x)

兄弟节点

顺便可以得到兄弟节点：

l_sibling=x+(h(x)<<1)r_sibling=x-(h(x)<<1)也就是 x^(h(x)<<1)而且father其实就是左右儿子之和的一半，即 father(x)=(x+sibling(x))>>1

树的增长

当节点数增加，叶子数量不够了，则原地翻倍增长，即root<<=1，轻松翻倍

于是访问这棵树的方法就基本全了。

代码

下面是普通的线段树解决区间最值的代码：

#include
    
     #define low(x)  (x&-x)#define hi(x)    (low(x)<<1)#define is_r(x) (x&hi(x))#define sib(x)    (x^hi(x))#define fa(x)    ((x|hi(x))^low(x))#define pos(x)    ((x<<1)|1)using namespace std;using ll=long long; const int maxn=500500;int n,m,a[maxn],root,x,y;void up(int x, int y) {  for(x = pos(x), a[x] = y; x != root && a[x] < a[sib(x)]; x = fa(x), a[x] = y);}int ask(int x, int y) {  int re = a[0];  for(int l = pos(x)-2, r = pos(y)+2; sib(l) != r; l = fa(l),r = fa(r))    re = min(re, min(is_r(l) ? a[0] : a[sib(l)], is_r(r) ? a[sib(r)] : a[0]));  return re;}void init() {  freopen("in.txt", "r", stdin);  scanf("%d%d",&n, &m);    memset(a, 0x7f, sizeof(a));  for(root = 1; root - 2 < n; root <<= 1);  for(int i = 1; i <= n; i++){    scanf("%d", &x);    up(i, x);  }}void work() {  for(int i = 1; i <= m; i++){    scanf("%d%d",&x, &y);    cout << ask(x,y) << ' ';  }}int main(){  init();  work();}
    

补充

一个节点的管辖范围

只要不断的迭代自己的左右儿子就能得到自己最左的叶子和最右的叶子，即:

l_leaf=x-h(x)+1r_leaf=x+h(x)-1

应用

根据上条性质，容易联想到一般的线段树中，递归时需要传递目前树的管辖范围，然而本树不需要。

这种树的好性质在于知道一个节点的编号，它的具体位置、父节点、兄弟节点、左右子节点、管辖范围等都可以直接算出来，而且很快，几乎是位运算和1次加法。

下面放上带lazy的线段树写法：

#include
    
     #define print(x...) printf(x) using namespace std;const int maxn=4000005;int a[maxn],root,n,m,x,y,z,b[maxn];int height(int x){    return x&-x;}bool is_left(int x){    return !(x&(height(x)<<1));}int father(int x){    return is_left(x)?x+height(x):x-height(x);}int lson(int x){    return x-(height(x)>>1);}int rson(int x){    return x+(height(x)>>1);}int sibling(int x){    return is_left(x)?x+(height(x)<<1):x-(height(x)<<1);}int ll(int x){    return x-height(x)+1;}int rr(int x){    return x+height(x)-1;}int pos(int x){    return (x<<1)+1;}void init(int x){    root=1;    while(root
     
      <<=1;    memset(a,0x7f,sizeof(a));}void up(int x){    x=father(x);    while(x!=root){        a[x]=min(a[lson(x)],a[rson(x)]);        x=father(x);    }    a[x]=min(a[lson(x)],a[rson(x)]);}void down(int x){    if(!b[x])return;    int ls=lson(x),rs=rson(x);    b[ls]+=b[x]; b[rs]+=b[x];    a[ls]-=b[x]; a[rs]-=b[x];    b[x]=0;}void change(int s,int x,int y,int z){    if(ll(s)>=x && rr(s)<=y){        a[s]-=z;        b[s]+=z;        return;    }    if(ll(s)>y || rr(s)
      
       =x && rr(s)<=y)return a[s];    if(ll(s)>y || rr(s)
       
        =x){            change(root,pos(y),pos(z),x);        }else{            printf("%d\n%d",-1,i);            return 0;        }    }}
       
      
     
    

总结

这种基于中序遍历的完全二叉树天然支持叶子定位和空间动态伸缩，写起来也很方便,初始化极为便利，基本不需要任何操作，计算树根的值即可。实际上这种树时无限大的，我们每次都是取它“左下角”的一块来使用。相比于层次遍历结构的二叉树，该种类对处理叶子纵向增长更轻松方便，比如说用这种结构实现个堆就会比较麻烦，至少不如层次型的方便。不过仍有很多适用的地方。