假设有这样一棵树。

Figure 6. BFS Layout

计算Pos的公式是：$Pos[d] = Pos[D[d]] + T[d] + (i \; AND \; T[d]) \times B[d]$

按深度维护的参数表

1. $d=2$，这个时候就是2,3这两个节点。他们在“上半树”的再切割中，成为了bottom tree的root。在第二轮递归切割里，top tree只有{1}，所以$T[2]=1$, 每一个bottom tree只有自己（2,3），所以$B[2]=1$，这个top tree的深度（节点1到root（也是节点1））$D[2]=1$
2. $d=3$，我们来到了第三层，也就是{4,5,6,7}这四个节点。他们在第一轮切割中，就成了bottom树的树根，还记得我们的切割规则是：当成为小树树根的时候就停止，所以这一层的4个节点不参与第二轮切割，top tree是高度为2的头顶小树：{1,2,3}，所以$T[3]=3$, 而每一个bottom tree的大小，又是3（4,8,9；5,10,11；…）所以$B[3]=3$，top根的深度：$D[3]=1$
3. $d=4$，我们来到了第四层，也就是{8,9,10,11,...,15}这8个节点。第一轮切割，他们成为了小树的底，他们在第二轮切割中，成为了以他们自己为小树的根，这个时候停止切割。top就是他们的父节点（比如4），$T[4]=1$, $B[4]=1$，top根的深度是$D[4]=3$

计算vEB layout的数组index

• 节点2：$d=2, i=2$, (d是深度，i是在BFS layout里面的index)
  • $Pos[2]=Pos[1]+T[2]+(2 \; and \; 1) \times B[2]=1+1+0\times1=2$ 那么它在vEB数组里面的位置就是2
  • 同理可得：$3: Pos[2]=3$
• 节点4：$d=3, i=4$ (深度是3，它在BFS layout里面位于4的位置)
  • $Pos[3]=Pos[1]+T[3]+(4 \; and \; T[3]) \times B[3]=1+3+0 \times 3 = 4$
  • 同理可得：$5: Pos[3]=7$
• 节点9：$d=4, i=9$
  • $Pos[4]=Pos[D[4]]+T[4]+(9 \; and \; T[4]) \times B[4]=4+1+1=6$
  • 同理可得：$8: Pos[4]=5$

所以理论上一份vEB layout应该长这样（在数组中）：

记号与不变量：

目标高度的上界，取$H \approx log n$, 在embedded完全树里，一个深度为$d(v)$的位置，其容量是：$s(v)=2^{H-d(v)+1}-1$。把真实子树大小$|T_v|$ 与容量比值定义为：

我们设计一串上界密度阈值 $0 < \tau_1 < \tau_2 < ... < \tau_H=1$ （注意这些$\tau_i$是等差的），并且维持根满足 $\rho(root) \le \tau_1$. 这样的设计就可以强制满足$H=logn + O(1)$的性质。

插入步骤：

1. 先按照普通Binary Search Tree的规则自顶向下找到插入的位置，生成新节点$v$.

举例：重建

光说还是很抽象，我们还是举一个例子：

假设我们现在就有一个$H=3$的宿主完全二叉树。（最多三层，容量有1+2+4=7个节点）

每一个深度的容量 $s(v)=2^{H-d(v)+1}-1$：

1. 深度1：s=7
2. 深度2：s=3
3. 深度3：s=1

然后我们设定上界阈值：$\tau_1=0.8, \tau_2=0.9, \tau_3=1$.

假设我们现在直接暴力插入（就是退化为链表那种）

// 插入10
10			// rho(根)=1/7=0.14 < 0.8
    
 
// 插入20
  10
    \
    20      // rho(根)=2/7=0.28 < 0.8;  rho(node_20) = 1/3 = 0.66 < 0.8  合法
    
// 插入30
  10
    \
    20
      \
      30    // rho(根)=3/7 < 0.8; rho(node_20) = 2/3=0.67 < 0.8; rho(node_30)=1/1=1 <= tau_3
 
// 插入40
  10
    \
    20
      \
      30
        \
        40   ← 新插入，深度4 超高

这个时候40已经超出了高度3，让这棵树的高度变成了4.

• $\rho(d=3)=\frac{2}{1}=2$
• $\rho(d=2)=\frac{3}{3}=1$, 超出了$\tau_2=0.9$
• $\rho(d=1)=\frac{4}{7} < 0.8$, 没超出$\tau_1$

因为没超出的就是d=1，所以我们要针对$d=1$层进行重建：

1. 此刻的中序序列是：{10,20,30,40}, 中位数我们选择20
2. 左右各自一半填回：

    20
   /  \
 10   30
         \
         40

举例：插入50

那假设现在还要再插入50呢？

    20
   /  \
 10   30
         \
         40
           \
           50   ← 新插入，深度4

• $\rho(d=3)=\frac{2}{1}=2$
• $\rho(d=2)=\frac{3}{3}=1$, 超出了$\tau_2=0.9$, 实际的元素有3个，理论上它应该存放的容量是 $s(v) = 2^{3-2+1}-1=3$
• $\rho(d=1)=\frac{5}{7}=0.71$, 没超出$\tau_1$

这个时候，没出问题的就依然是根 $d=1$，所以我们针对根进行重建：

[10,20,30,40,50]就变成了：

     30
    /  \
  20    40
 /        \
10        50

举例：再插入60

再插入60的时候，连$\rho(d=1) \approx 0.86 > 0.8$了，连祖先都满足不了阈值，只能对整棵树重建，提升树的高度。

Suppose we have a tree like this.

Figure 6. BFS Layout

The formula for computing Pos is: $Pos[d] = Pos[D[d]] + T[d] + (i \; AND \; T[d]) \times B[d]$

The per-depth parameter table

1. $d=2$: these are nodes 2 and 3. In the second split of the “top half-tree”, they become the roots of bottom trees. In the second round of recursive splitting, the top tree is just {1}, so $T[2]=1$; each bottom tree contains only the node itself (2 or 3), so $B[2]=1$; the depth of this top tree (from node 1 to the root, which is also node 1) is $D[2]=1$
2. $d=3$: we’ve reached the third level, i.e., the four nodes {4,5,6,7}. They already became the roots of bottom trees in the first round of splitting. Remember that our splitting rule is: stop once a node becomes the root of a small tree, so the 4 nodes on this level do not take part in the second round of splitting. The top tree is the small tree of height 2 above them, {1,2,3}, so $T[3]=3$; each bottom tree again has size 3 (4,8,9; 5,10,11; …), so $B[3]=3$; the depth of the top tree’s root: $D[3]=1$
3. $d=4$: we’ve reached the fourth level, i.e., the 8 nodes {8,9,10,11,...,15}. In the first round of splitting, they end up at the bottom of the small trees; in the second round of splitting, each of them becomes the root of a small tree consisting of just itself, at which point the splitting stops. The top is their parent node (e.g., 4), so $T[4]=1$, $B[4]=1$, and the depth of the top root is $D[4]=3$

Computing the array index in the vEB layout

• Node 2: $d=2, i=2$ (d is the depth, i is the index in the BFS layout)
  • $Pos[2]=Pos[1]+T[2]+(2 \; and \; 1) \times B[2]=1+1+0\times1=2$, so its position in the vEB array is 2
  • Similarly: $3: Pos[2]=3$
• Node 4: $d=3, i=4$ (the depth is 3, and it is at position 4 in the BFS layout)
  • $Pos[3]=Pos[1]+T[3]+(4 \; and \; T[3]) \times B[3]=1+3+0 \times 3 = 4$
  • Similarly: $5: Pos[3]=7$
• Node 9: $d=4, i=9$
  • $Pos[4]=Pos[D[4]]+T[4]+(9 \; and \; T[4]) \times B[4]=4+1+1=6$
  • Similarly: $8: Pos[4]=5$

So in theory, a vEB layout should look like this (in the array):

Notation and invariants:

For the upper bound on the target height, take $H \approx log n$. In the embedded complete tree, a position at depth $d(v)$ has capacity $s(v)=2^{H-d(v)+1}-1$. The ratio of the actual subtree size $|T_v|$ to the capacity is defined as:

We define a sequence of upper density thresholds $0 < \tau_1 < \tau_2 < ... < \tau_H=1$ (note that these $\tau_i$ form an arithmetic progression) and maintain that the root satisfies $\rho(root) \le \tau_1$. This design enforces the property $H=logn + O(1)$.

Insertion steps:

1. First, following the usual Binary Search Tree rules, find the insertion position top-down and create the new node $v$.

Example: rebuilding

Talk alone is still too abstract, so let’s go through an example:

Suppose we have a host complete binary tree with $H=3$ (at most three levels, with a capacity of 1+2+4=7 nodes).

The capacity at each depth, $s(v)=2^{H-d(v)+1}-1$:

1. Depth 1: s=7
2. Depth 2: s=3
3. Depth 3: s=1

Then we set the upper thresholds: $\tau_1=0.8, \tau_2=0.9, \tau_3=1$.

Suppose we now just insert naively (the kind that degenerates into a linked list)

// Insert 10
10			// rho(root)=1/7=0.14 < 0.8
    
 
// Insert 20
  10
    \
    20      // rho(root)=2/7=0.28 < 0.8;  rho(node_20) = 1/3 = 0.66 < 0.8  valid
    
// Insert 30
  10
    \
    20
      \
      30    // rho(root)=3/7 < 0.8; rho(node_20) = 2/3=0.67 < 0.8; rho(node_30)=1/1=1 <= tau_3
 
// Insert 40
  10
    \
    20
      \
      30
        \
        40   ← newly inserted, depth 4, exceeds the height

At this point, 40 has gone beyond height 3, making the tree’s height 4.

• $\rho(d=3)=\frac{2}{1}=2$
• $\rho(d=2)=\frac{3}{3}=1$, exceeding $\tau_2=0.9$
• $\rho(d=1)=\frac{4}{7} < 0.8$, not exceeding $\tau_1$

Since the one that doesn’t exceed its threshold is d=1, we rebuild at level $d=1$:

1. The in-order sequence at this point is {10,20,30,40}; we choose 20 as the median
2. Fill the left and right halves back in:

    20
   /  \
 10   30
         \
         40

Example: inserting 50

Now suppose we want to insert 50 as well?

    20
   /  \
 10   30
         \
         40
           \
           50   ← newly inserted, depth 4

• $\rho(d=3)=\frac{2}{1}=2$
• $\rho(d=2)=\frac{3}{3}=1$, exceeding $\tau_2=0.9$; there are actually 3 elements, and the capacity it should theoretically hold is $s(v) = 2^{3-2+1}-1=3$
• $\rho(d=1)=\frac{5}{7}=0.71$, not exceeding $\tau_1$

At this point, the one without a problem is still the root, $d=1$, so we rebuild at the root:

[10,20,30,40,50] becomes:

     30
    /  \
  20    40
 /        \
10        50

Example: inserting 60 next

When we then insert 60, even $\rho(d=1) \approx 0.86 > 0.8$; not even the ancestor can satisfy the threshold, so the only option is to rebuild the entire tree and increase its height.