节点大小平衡树

SBT的旋转(Rotations)与其他许多高级BST相同。它是下面提到的Maintain操作的基础。

Left-Rotate (t)

1 k ← right[t]

2 right[t] ← left[k]

3 left[k] ← t

4 s[k] ← s[t]

5 s[t] ← s[left[t]] + s[right[t]] + 1

6 t ← k

Right-Rotate(t)

1 k ← left[t]

2 left[t] ← right[k]

3 right[k] ← t

4 s[k] ← s[t]

5 s[t] ← s[left[t]] + s[right[t]] + 1

6 t ← k

SBT的高度是O(logn)，Maintain是O(1)，所有主要操作都是O(logn)。

Size Balanced Tree(SBT)是一种通过大小(Size)域来保持平衡的二叉搜索树，它也因此得名。它总是满足:

对于SBT的每一个结点 t:

性质(a) s[right[t] ]≥s[left[left[t]]], s[right[left[t]]]

性质(b) s[left[t] ]≥s[right[right[t]]], s[left[right[t]]]

即每棵子树的大小不小于其兄弟的子树大小。

SBT的查找操作与普通BST完全相同。下面的过程将返回指向目标节点的指针。

Search(t,k)

1 if x=NIL or k=key[t]

2 then return x

3 if k<key[x]

4 then return Search(left[x],k)

5 else return Search(right[x],k)

由于SBT本身已经维护了size，因此这两项可用Select操作完成。

SBT的后继操作与普通BST完全相同。

SBT的前趋操作与普通BST完全相同。它与上面的后继操作对称。

SBT的插入操作仅仅比普通BST的多出了一个Maintain操作，以及对s的简单维护(这在普通BST的动态顺序统计操作中也是必须的)。下面这个过程将一个节点v插入SBT中。

Insert (t,v)

1 If t=0 then

2 t ← v

3 Else

4 s[t] ← s[t]+1

5 If v<key[t] then

6 Insert(left[t],v)

7 Else

8 Insert(right[t],v)

9 Maintain(t,v≥key[t])

与普通维护size域的BST删除相同(无需Maintain)。

下面这个过程将返回一个指向以x为根的子树中包含第i小关键字的节点的指针。

Select(x,i)

1 r ← size[left[x]] + 1

2 if(i=r)

3 then return x

4 else if i<r

5 then return Select(left[x],r)

6 else return Select(right[x],i-r)

SBT的rank操作与普通BST完全相同。

//节点最多的时候是满二叉树，如果认为第一层的高度为0，那么节点数最多应该是2^(h+1) -1

//把h理解成层数才是2^h-1，下面写的最多有错误

高度为 h 的 AVL 树，节点数 N 最多2^h − 1; 最少N(h)=N(h− 1) +N(h− 2) + 1。

最少节点数n 如以斐波那契数列可以用数学归纳法证明:

即:

N(0) = 1 (表示 AVL Tree 高度为0的节点总数)

N(1) = 2(表示 AVL Tree 高度为1的节点总数)

N(2) = 4(表示 AVL Tree 高度为2的节点总数)

N(h)=N(h− 1) +N(h− 2) + 1 (表示 AVL Tree 高度为h的节点总数)

节点的平衡因子是它的左子树的高度减去它的右子树的高度。带有平衡因子 1、0 或 -1 的节点被认为是平衡的。带有平衡因子 -2 或 2 的节点被认为是不平衡的，并需要重新平衡这个树。平衡因子可以直接存储在每个节点中，或从可能存储在节点中的子树高度计算出来。