AA树
红黑树的编程相当复杂,AA树是一颗带有条件的红黑树,相当情况下简化了红黑树的编程.
- AA树规定只有右孩子才能是红色节点.
- 我们不再记录颜色,而是用level和每个节点存在一起.level实际上相当与红黑树的black-height.
- 红节点的level与其父节点相同
- 黑节点的level比其父节点低1
- 树叶节点level为1
我们把颜色转化为层次来看,可以发现左儿子必然比它的父节点恰好低1,右儿子可能比父节点低0或1.
水平链接出现在一个节点与相等层次的儿子之间的连接,由上面那些性质我们可以发现,水平链接一般都是向右的.
23
我们在编程的时候,插入点的时候通通把level设为1,也就是说与父节点都是水平链接,这样会出现两种不允许的情况:
- 水平左链接,这违反了AA树自身的条件.
- 连续右链接,这相当于违反了红黑树中红节点的孩子不能也是红的.
对于上面两种情况,我们可以相应采用skew方法以及split方法处理.
24
上图可知skew与split分别对应右旋转与左旋转(红黑树术语),并且注意R的层次在split中增加1.
需要注意的是,skew方法结束后很经常会引起连续右链接,还需要通过split方法处理,所以一般我们先用skew再用split.
插入的过程就是不断skew以及split了,删除操作相对稍复杂一些.
由于我们采用递归删除,所以在最后一层,如果不是叶子节点的话就没问题,把右孩子赋给自身就可以,如果是叶子节点的话就会出现异常.但是考虑到递归属性,我们仍然把右孩子赋给自身即nullNode.然后递归回去的时候进行检验,如果右孩子或者左孩子比自身低2层,说明出现问题了,需要修复.
修复的过程还是比较麻烦的,如果有右子树,右子树也要降低一层.修复可能会引起大量的连锁反应,举个例子:
25
如果我们要删除1,那么递归到2时候发现左节点低2层,开始修复.把2和5都降低一层,那么首先会出现左链接,5-3,修复完以后出现新的左链接5-4.另外考虑如果删除在右边,那么左节点也有可能水平,所以我们调用三次skew.接着有很多的连续右连接,我们只需要调用两次split就可以重新处理好了.
编码相对红黑树来说简单太多:
package com.fredal.structure;
public class AATree<AnyType extends Comparable<? super AnyType>>
{
//内部节点类
private static class AANode<AnyType>
{
AANode( AnyType theElement, AANode<AnyType> lt, AANode<AnyType> rt )
{
element = theElement;
left = lt;
right = rt;
level = 1;
}
AnyType element;
AANode<AnyType> left;
AANode<AnyType> right;
int level; // 层次
}
private AANode<AnyType> root;
private AANode<AnyType> nullNode;
private AANode<AnyType> deletedNode;
private AANode<AnyType> lastNode;
public AATree( )
{
nullNode = new AANode<AnyType>( null, null, null );
nullNode.left = nullNode.right = nullNode;
nullNode.level = 0;
root = nullNode;
}
public void insert( AnyType x )
{
root = insert( x, root );
}
public void remove( AnyType x )
{
deletedNode = nullNode;
root = remove( x, root );
}
//最小值
public AnyType findMin( )
{
if( isEmpty( ) )
return null;
AANode<AnyType> ptr = root;
while( ptr.left != nullNode )
ptr = ptr.left;
return ptr.element;
}
//最大值
public AnyType findMax( )
{
if( isEmpty( ) )
return null;
AANode<AnyType> ptr = root;
while( ptr.right != nullNode )
ptr = ptr.right;
return ptr.element;
}
//寻找值并返回
public AnyType find( AnyType x )
{
AANode<AnyType> current = root;
nullNode.element = x;
for( ; ; )
{
if( x.compareTo( current.element ) < 0 )
current = current.left;
else if( x.compareTo( current.element ) > 0 )
current = current.right;
else if( current != nullNode )
return current.element;
else
return null;
}
}
//情空
public void makeEmpty( )
{
root = nullNode;
}
//判空
public boolean isEmpty( )
{
return root == nullNode;
}
//插入
private AANode<AnyType> insert( AnyType x, AANode<AnyType> t )
{
if( t == nullNode )
t = new AANode<AnyType>( x, nullNode, nullNode );//初始化
else if( x.compareTo( t.element ) < 0 )
t.left = insert( x, t.left );
else if( x.compareTo( t.element ) > 0 )
t.right = insert( x, t.right );
else
;//重复值
t = skew( t );//先skew 再split
t = split( t );
return t;
}
//删除
private AANode<AnyType> remove( AnyType x, AANode<AnyType> t )
{
if( t != nullNode )
{
// 往下搜索并设置lastnode和deletenode
lastNode = t;
if( x.compareTo( t.element ) < 0 )
t.left = remove( x, t.left );
else
{
deletedNode = t;//要删除的值
t.right = remove( x, t.right );//找右子树最小值
}
//在底层 直接删除
if( t==lastNode)
{
if( deletedNode == nullNode || x.compareTo( deletedNode.element ) != 0 )
throw new RuntimeException( x.toString( ) );
deletedNode.element = t.element;
t = t.right;//必定有右孩子
}
//不在底层 需要重新平衡
else
if( t.left.level < t.level - 1 || t.right.level < t.level - 1 )//低两层 因为有nullNode
{
if( t.right.level > --t.level )//右子树降一层
t.right.level = t.level;
t = skew( t );//三次skew
t.right = skew( t.right );
t.right.right = skew( t.right.right );
t = split( t );//两次split
t.right = split( t.right );
}
}
return t;
}
private static <AnyType> AANode<AnyType> skew( AANode<AnyType> t )
{
if( t.left.level == t.level )
t = rotateWithLeftChild( t );
return t;
}
private static <AnyType> AANode<AnyType> split( AANode<AnyType> t )
{
if( t.right.right.level == t.level )
{
t = rotateWithRightChild( t );
t.level++;
}
return t;
}
private static <AnyType> AANode<AnyType> rotateWithLeftChild( AANode<AnyType> k2 )
{
AANode<AnyType> k1 = k2.left;
k2.left = k1.right;
k1.right = k2;
return k1;
}
private static <AnyType> AANode<AnyType> rotateWithRightChild( AANode<AnyType> k1 )
{
AANode<AnyType> k2 = k1.right;
k1.right = k2.left;
k2.left = k1;
return k2;
}
public static void main( String [ ] args )
{
AATree<Integer> tree=new AATree<Integer>();
final int NUM=40000;
System.out.println("如果程序不输出就成功了....");
for(int i=37;i!=0;i=(i+37)%NUM)
tree.insert(i);//伪随机
for(int i=1;i<NUM;i+=2)
tree.remove(i);//删除所有奇数
if( tree.findMin( ) != 2 || tree.findMax( ) != NUM - 2 )
System.out.println( "最大值最小值寻找错误!" );
for( int i = 2; i < NUM; i += 2 )
if( tree.find(i)!=i )
System.out.println( "偶数缺失" + i );
for( int i = 1; i < NUM; i += 2 )
if( tree.find(i)!=null)
System.out.println( "奇数多余" + i );
}
}
treap树
treap树是一种二叉查找树,但是十分简单.顾名思义我们可以知道,它是堆和树的合体,在树中维护了一个"优先级",而优先级具有堆性质.
采用随机数的方式为"优先级"赋值,并且满足堆性质,而同时节点本身的值满足二叉查找树性质.
26
插入:对于插入,就像二叉查找树一样插入就好,但由于我们的优先级是随机数的,所以可能不会满足堆性质.所以需要靠旋转来实现.
对于AVL树玩的溜的话,下面两种情况不成问题,不赘述了.
27
28
删除:这里可以采取普通二叉查找树的方式删除,即右子树找最小或者左子树找最大,赋值时候不带优先级即可.
我们讲另外一种通过旋转的方式实现:
叶子节点和单孩子不赘述,如果是双孩子,就想办法通过旋转来达到单孩子即可.
29
这里删除我们仍然采用递归,所以删除的时候不是直接判断是否双孩子还是单孩子的,而是通过递归的性质来删除,注意代码里小技巧.
实现(随机数产生器使用自己之前写的,参考随机数)
package com.fredal.structure;
public class TreapTree<T extends Comparable<? super T>> {
//内部节点类
static class TreapNode<T>{
T element;
TreapNode<T> left;
TreapNode<T> right;
int priority;//优先级
private static Random random=new Random();//随机数产生器
TreapNode(T element, TreapNode<T> left, TreapNode<T> right) {
this.element = element;
this.left = left;
this.right = right;
this.priority = random.RandomInt();//随机产生
}
TreapNode(T element){
this(element, null, null);
}
}
private TreapNode<T> root;
private TreapNode<T> nullNode;
public TreapTree(){
nullNode=new TreapNode<T>(null);
nullNode.left=nullNode.right=nullNode;
nullNode.priority=Integer.MAX_VALUE;//设为无限大
root=nullNode;
}
public void insert(T x){
root=insert(x,root);
}
//插入操作
private TreapNode<T> insert(T x, TreapNode<T> t) {
if(t==nullNode)
return new TreapNode<T>(x, nullNode, nullNode);
int res=x.compareTo(t.element);
if(res<0){
t.left=insert(x, t.left);
if(t.left.priority<t.priority)//左左旋转
t=rotateL(t);
}else if(res>0){
t.right=insert(x, t.right);
if(t.right.priority<t.priority)
t=rotateR(t);
}
return t;
}
// 右右单旋转
private static TreapNode rotateR(TreapNode k1) {
TreapNode k2 = k1.right;
k1.right = k2.left;
k2.left = k1;
return k2;
}
// 左左单旋转
private static TreapNode rotateL(TreapNode k2) {
TreapNode k1 = k2.left;
k2.left = k1.right;
k1.right = k2;
return k1;
}
public void remove(T x){
root=remove(x,root);
}
private TreapNode<T> remove(T x, TreapNode<T> t) {
if(t!=nullNode){
int res=x.compareTo(t.element);
if(res<0)
t.left=remove(x, t.left);
else if(res>0)
t.right=remove(x, t.right);
else{
//找到了
if(t.left.priority<t.right.priority)
t=rotateL(t);//左左旋转
else
t=rotateR(t);//右右旋转
if(t!=nullNode)
t=remove(x, t);//继续递归
else
t.left=nullNode;//旋转后刚好等于删除节点
}
}
return t;
}
//最小值
public T findMin(){
if(isEmpty())
throw new RuntimeException("空树");
TreapNode<T> ptr=root;
while(ptr.left!=nullNode)
ptr=ptr.left;
return ptr.element;
}
//最大值
public T findMax(){
if(isEmpty())
throw new RuntimeException("空树");
TreapNode<T> ptr=root;
while(ptr.right!=nullNode)
ptr=ptr.right;
return ptr.element;
}
//是否存在
public boolean contains(T x){
TreapNode<T> current=root;
nullNode.element=x;
for(;;){
int res=x.compareTo(current.element);
if(res<0)
current=current.left;
else if(res>0)
current=current.right;
else
return current!=nullNode;
}
}
//情空
public void makeEmpty(){
root=nullNode;
}
//判空
public boolean isEmpty(){
return root==nullNode;
}
//打印
public void printTree(){
if(isEmpty())
System.out.println("这是空树");
else
printTree(root);
}
private void printTree(TreapNode<T> t) {
if(t!=nullNode){
printTree(t.left);
System.out.println(t.element.toString());
printTree(t.right);
}
}
public static void main(String[] args) {
TreapTree<Integer> tree=new TreapTree<Integer>();
tree.insert(6);
tree.insert(10);
tree.insert(8);
tree.insert(12);
tree.insert(14);
tree.insert(16);
tree.printTree();
tree.makeEmpty();
final int NUM=40000;
System.out.println("下面如果程序不输出就成功了....");
for(int i=37;i!=0;i=(i+37)%NUM)
tree.insert(i);//伪随机
for(int i=1;i<NUM;i+=2)
tree.remove(i);//删除所有奇数
if( tree.findMin( ) != 2 || tree.findMax( ) != NUM - 2 )
System.out.println( "最大值最小值寻找错误!" );
for( int i = 2; i < NUM; i += 2 )
if( !tree.contains(i))
System.out.println( "偶数缺失" + i );
for( int i = 1; i < NUM; i += 2 )
if( tree.contains(i))
System.out.println( "奇数多余" + i );
}
}
k-d树
如果要筛选出年龄30到35岁之间并且年薪在20万到50万的人士,这种问题叫做二维范围查找.当然相应地还有k维.
我们可以使2-d树(k-d树)来解决问题,它的性质如下.
在奇数层上的分支按照第一个关键字进行二叉排序.在偶数层上按照第二个关键字进行排序.
性质非常简单,编码也非常简单.注意如果关键字重复了,我们默认把它放到右子树,如果重复太多显然是比较坏的情况.
k-d树最坏情况是O(N),不像二叉查找树那样有红黑树等等最坏情况(O log N)的变种,因为旋转在这行不通.
k近邻搜索是关于k-d树的经典的例子,首先通过二叉树搜索（比较待查询节点和分裂节点的分裂维的值，小于等于就进入左子树分支，等于就进入右子树分支直到叶子结点），顺着“搜索路径”很快能找到最近邻的近似点，也就是与待查询点处于同一个子空间的叶子结点；然后再回溯搜索路径，并判断搜索路径上的结点的其他子结点空间中是否可能有距离查询点更近的数据点，如果有可能，则需要跳到其他子结点空间中去搜索（将其他子结点加入到搜索路径）。重复这个过程直到搜索路径为空。我们在这不做代码演示.
给出k-d树,应该说2-d数基本的插入以及筛选范围的代码实例
package com.fredal.structure;
//2-d树
public class KDTree<T extends Comparable<? super T>> {
private static class KDNode<T>{
T[] data;//数组形式
KDNode<T> left;
KDNode<T> right;
KDNode(T item[]){
data=(T[]) new Comparable[2];
data[0]=item[0];
data[1]=item[1];
left=right=null;
}
}
private KDNode<T> root;//根节点
public KDTree(){
root=null;
}
public void insert(T[] x){
root=insert(x,root,0);
}
//插入
private KDNode<T> insert(T[] x, KDNode<T> t, int level) {
if(t==null)
t=new KDNode<T>(x);
else if(x[level].compareTo(t.data[level])<0)
t.left=insert(x, t.left, 1-level);//每层关键字更替
else//相同的话都归到右子树
t.right=insert(x, t.right, 1-level);
return t;
}
public void printRange(T[] low,T[] high){
printRange(low,high,root,0);
}
//筛选方法
private void printRange(T[] low, T[] high, KDNode<T> t, int level) {
if(t!=null){
if(low[0].compareTo(t.data[0])<=0&&
low[1].compareTo(t.data[1])<=0&&
high[0].compareTo(t.data[0])>=0&&
high[1].compareTo(t.data[1])>=0)
System.out.println(t.data[0]+","+t.data[1]);//输出
if(low[level].compareTo(t.data[level])<=0)
printRange(low, high, t.left, 1-level);//下界 下一层
if(high[level].compareTo(t.data[level])>=0)
printRange(low, high, t.right, 1-level);//上界 下一层
}
}
public static void main(String[] args) {
KDTree<Integer> t=new KDTree<Integer>();
for(int i=300;i<370;i++){
Integer[] it=new Integer[2];
it[0]=i;
it[1]=2500-i;
t.insert(it);
}
Integer[] low={300,2100};
Integer[] high={350,2200};
t.printRange(low, high);
}
}
B树
在大规模存储数据的时候,往往树深度过深而导致性能不佳,那么显然需要想办法减少深度,一个自然的想法即是一个节点有多个孩子,类似多叉树这样.
B树是为了磁盘或其它存储设备而设计的一种多叉（下面你会看到，相对于二叉，B树每个内结点有多个分支，即多叉）平衡查找树,我们这里暂且不讨论B+,B*等.
我们可以用阶段定义B树,也可以用度定义B树,以度为例子,一颗度为m的B树:
- 每个非根的内结点至多有m个子女，每个非根的结点必须至少含有m-1个关键字，如果树是非空的，则根结点至少包含一个关键字；
- 每个结点可包含至多2m-1个关键字。所以一个内结点至多可有2m个子女。如果一个结点恰好有2m-1个关键字，我们就说这个结点是满的
插入:插入相对来说比较简单
- 利用前述的B-树的查找算法查找关键字的插入位置。若找到，则说明该关键字已经存在，直接返回。否则查找操作必失败于某个最低层的非终端结点上。
- 判断该结点是否还有空位置。即判断该结点的关键字总数是否满足n<=m-1。若满足，则说明该结点还有空位置，直接把关键字k插入到该结点的合适位置上。若不满足，说明该结点己没有空位置，需要把结点分裂成两个。
分裂的方法是：生成一新结点。把原结点上的关键字和k按升序排序后，从中间位置把关键字（不包括中间位置的关键字）分成两部分。左部分所含关键字放在旧结点中，右部分所含关键字放在新结点中，中间位置的关键字连同新结点的存储位置插入到父结点中。如果父结点的关键字个数也超过（m-1），则要再分裂，再往上插。直至这个过程传到根结点为止。
30
31
32
33
删除:在B-树上删除关键字k的过程分两步完成：
- 利用B-树的查找算法找出该关键字所在的结点。然后根据 k所在结点是否为叶子结点有不同的处理方法。
- 若该结点为非叶结点，且被删关键字为该结点中第i个关键字key[i]，则可从指针son[i]所指的子树中找出最小关键字Y，代替key[i]的位置，然后在叶结点中删去Y。
因此，把在非叶结点删除关键字k的问题就变成了删除叶子结点中的关键字的问题了。在B-树叶结点上删除一个关键字的方法是
首先将要删除的关键字 k直接从该叶子结点中删除。然后根据不同情况分别作相应的处理，共有三种可能情况：
- 如果被删关键字所在结点的原关键字个数不贫困，说明删去该关键字后该结点仍满足B-树的定义。只需从该结点中直接删去关键字即可。
- 如果被删关键字所在结点的关键字个数没脱贫，说明删去该关键字后该结点将不满足B-树的定义，需要调整。
调整过程为：如果其左右兄弟结点中有“多余”的关键字,即与该结点相邻的右（左）兄弟结点中的关键字数目多余。则可将右（左）兄弟结点中最小（大）关键字上移至双亲结点。而将双亲结点中小（大）于该上移关键字的关键字下移至被删关键字所在结点中,相当于一次旋转。 - 如果左右兄弟结点中没有“多余”的关键字，即与该结点相邻的右（左）兄弟结点中的关键字数目均贫困1。这种情况比较复杂。需把要删除关键字的结点与其左（或右）兄弟结点以及双亲结点中分割二者的关键字合并成一个结点,即在删除关键字后，该结点中剩余的关键字加指针，加上双亲结点中的关键字Ki（是双亲结点指向该删除关键字结点的左（右）兄弟结点的指针）所指的兄弟结点中去。如果因此使双亲结点中关键字个数贫困了，则对此双亲结点做同样处理。以致于可能直到对根结点做这样的处理而使整个树减少一层。
总之，设所删关键字为非终端结点中的Ki，则可以指针Ai所指子树中的最小关键字Y代替Ki，然后在相应结点中删除Y。对任意关键字的删除都可以转化为对最下层关键字的删除。
34
35
36
37
实现:
package com.fredal.structure;
import java.util.Stack;
public class BTree {
private int T;//度
private Node root;//根
//内部节点类
public class Node {
int n;//个数
int key[] = new int[2*T-1];
Node child[] = new Node[2*T];
boolean leaf = true;
//试匹配
public int Find(int k){
for (int i = 0 ; i < this.n ; i++) {
if (this.key[i] == k) {
return i;
}
}
return -1;
};
}
public BTree(int _T) {
T = _T;
root = new Node();
root.n = 0;
root.leaf = true;//刚开始都是树叶
}
//搜索
private Node Search (Node x,int key) {
int i = 0;
if (x == null) return x;
for (i = 0 ; i < x.n ; i++) {
if (key < x.key[i])
break;
if (key == x.key[i])//找到了1
return x;
}
if (x.leaf)
return null;//没东西查了
else
return Search(x.child[i],key);//找子节点去
}
//插入
public void Insert (final int key) {
Node r = root;
if (r.n == 2*T - 1 ) {//满了
Node s = new Node();
root = s;//root上升
s.leaf = false;//变成不是叶子
s.n = 0;
s.child[0] = r;
Split(s,0,r);//分裂
_Insert(s,key);//直接插入
} else {
_Insert(r,key);//直接插入
}
}
//分裂(合并) x-父节点 pos-是第几个孩子 y-要分裂的节点
private void Split (Node x , int pos , Node y) {
Node z = new Node();
z.leaf = y.leaf;
z.n = T - 1;//更新大小
for (int j = 0 ; j < T - 1 ; j++) {
z.key[j] = y.key[j+T];//赋值 对半分
}
if (! y.leaf) {//不是叶子节点 重新分配子节点
for (int j = 0 ; j < T ; j++)
z.child[j] = y.child[j+T];//子节点也分对半
}
y.n = T-1;//更新大小
for (int j = x.n ; j >= pos+1 ; j--)
x.child[j+1] = x.child[j];//挪位
x.child[pos+1] = z;//插入
for (int j = x.n-1 ; j >= pos ; j--)//挪位
x.key[j+1] = x.key[j];
x.key[pos] = y.key[T-1];//插入
x.n = x.n + 1;
}
//根不满时候插入
final private void _Insert (Node x , int k) {
if (x.leaf) {//叶子节点 直接插入
int i = 0;
for (i = x.n-1 ; i >= 0 && k < x.key[i] ; i--)
x.key[i+1] = x.key[i];
x.key[i+1] = k;
x.n = x.n + 1;
} else {
int i = 0;
for (i = x.n-1 ; i >= 0 && k < x.key[i] ; i--){};//找合适的孩子节点插
i++;
Node tmp = x.child[i];
if (tmp.n == 2*T -1) {//孩子节点满了
Split(x,i,tmp);//分裂与合并
if ( k > x.key[i])//再找一遍
i++;
}
_Insert(x.child[i], k);//插入子节点
}
}
public void Show () {
Show(root);
}
//打印
private void Show (Node x) {
assert(x == null);
System.out.print(x.leaf +":" );
for ( int i = 0 ; i < x.n ; i++) {
System.out.print(x.key[i]+ " ");
}
System.out.println();
if (!x.leaf) {
for (int i = 0 ;i < x.n + 1; i++) {
Show(x.child[i]);//输出子节点
}
}
}
public void Remove (int key) {
Node x = Search(root, key);
if (x == null) {
return;
}
Remove(root,key);
}
//删除
private void Remove (Node x , int key) {
int pos = x.Find(key);//先试匹配
if (pos != -1) {//找到了 说明当前就包含要删除的
if (x.leaf) {//删除的是叶子节点
int i = 0 ;
for (i = 0 ; i < x.n && x.key[i] != key ; i++){};//找到删除位置
for ( ; i < x.n ; i++) {
if (i != 2*T - 2){
x.key[i] = x.key[i+1];
}
}
x.n--;
return;
}
if (!x.leaf){//删除的不是叶子节点
Node pred = x.child[pos];//当前节点元素的右节点
int predKey = 0;
if (pred.n >= T) {//不贫困
for (;;) {
if (pred.leaf) {//是叶子
predKey = pred.key[pred.n - 1];
break;
} else {//继续往下 循环直到叶子
pred = pred.child[pred.n];
}
}
Remove (pred, predKey);//叶子 直接删除
x.key[pos] = predKey;//移到父节点去
return;
}
//自己贫困了 看看兄弟节点
Node nextNode = x.child[pos+1];
if (nextNode.n >= T) {//兄弟节点不贫困
int nextKey = nextNode.key[0];
if (!nextNode.leaf){//不是叶子
nextNode = nextNode.child[0];
for (;;) {
if (nextNode.leaf) {//是叶子
nextKey = nextNode.key[nextNode.n-1];
break;
} else {
nextNode = nextNode.child[nextNode.n];//往下降直到叶子
}
}
}
Remove(nextNode, nextKey);//删除
x.key[pos] = nextKey;//移到父节点
return;
}
//都贫困
int temp = pred.n + 1;
pred.key[pred.n++] = x.key[pos];//先从父节点借一个
for (int i = 0, j = pred.n ; i < nextNode.n ; i++) {//和兄弟合并
pred.key[j++] = nextNode.key[i];
pred.n++;
}
for (int i = 0 ; i < nextNode.n+1 ; i++){//子节点也合并
pred.child[temp++] = nextNode.child[i];
}
x.child[pos] = pred;//更新
for (int i = pos ; i < x.n ; i++) {//父节点关键字更新
if (i != 2*T - 2) {
x.key[i] = x.key[i+1];
}
}
for (int i = pos+1 ; i < x.n+1 ; i++) {//父节点孩子节点更新
if (i != 2*T - 1) {
x.child[i] = x.child[i+1];
}
}
x.n--;//个数递减
if (x.n == 0) {
if (x == root) {
root = x.child[0];
}
x = x.child[0];
}
Remove(pred,key);//删除
return;
}
} else {//没找到 当前不包含删除的
for (pos = 0 ; pos < x.n ; pos++) {
if (x.key[pos] > key)//寻找包含目标的孩子节点
break;
}
Node tmp = x.child[pos];//找到的这个节点
if (tmp.n >= T) {//不贫困 就删除(不一定就找到了,可能只是包含)
Remove (tmp,key);
return;
}
if (true) {
Node nb = null;
int devider = -1;
if (pos != x.n && x.child[pos+1].n >= T) {//右孩子不贫困
devider = x.key[pos];
nb = x.child[pos+1];
x.key[pos] = nb.key[0];//父节点借用孩子节点
tmp.key[tmp.n++] = devider;//借用父节点,相当于一次旋转
tmp.child[tmp.n] = nb.child[0];//借用兄弟节点
for (int i = 1 ; i < nb.n ; i++) {//重新挪位置
nb.key[i-1] = nb.key[i];
}
for (int i = 1 ; i <= nb.n ; i++) {
nb.child[i-1] = nb.child[i];
}
nb.n--;
Remove(tmp,key);//删除
return;
} else if (pos != 0 && x.child[pos-1].n >= T){//左孩子不贫困,和上面类似
devider = x.key[pos-1];
nb = x.child[pos-1];
x.key[pos-1] = nb.key[nb.n-1];
Node child = nb.child[nb.n];
nb.n--;
for(int i = tmp.n ; i > 0 ; i--) {
tmp.key[i] = tmp.key[i-1];
}
tmp.key[0] = devider;
for(int i = tmp.n + 1 ; i > 0 ; i--) {
tmp.child[i] = tmp.child[i-1];
}
tmp.child[0] = child;
tmp.n++;
Remove(tmp,key);
return;
} else {//都贫困 合并
Node lt = null;//左孩子
Node rt = null;//右孩子
boolean last = false;
if (pos != x.n) {
devider = x.key[pos];
lt = x.child[pos];
rt = x.child[pos+1];
} else {
devider = x.key[pos-1];
rt = x.child[pos];
lt = x.child[pos-1];
last = true;
pos--;
}
for (int i = pos; i < x.n-1 ; i++){
x.key[i] = x.key[i+1];
}
for(int i = pos+1 ; i < x.n ; i++) {
x.child[i] = x.child[i+1];
}
x.n--;
lt.key[lt.n++] = devider;
for (int i = 0, j = lt.n; i < rt.n+1 ; i++,j++) {
if (i < rt.n) {
lt.key[j] = rt.key[i];
}
lt.child[j] = rt.child[i];
}
lt.n += rt.n;
if (x.n == 0) {
if (x == root) {
root = x.child[0];
}
x = x.child[0];
}
Remove(lt,key);
return;
}
}
}
}
public void Task (int a, int b){
Stack<Integer> st = new Stack<Integer>();
FindKeys(a,b,root,st);
while (st.isEmpty() == false) {
this.Remove(root,st.pop());
}
}
private void FindKeys (int a, int b, Node x, Stack<Integer> st){
int i = 0;
for (i = 0 ; i < x.n && x.key[i] < b; i++) {
if ( x.key[i] > a ) {
st.push(x.key[i]);
}
}
if (!x.leaf) {
for (int j = 0 ; j < i+1 ; j++) {
FindKeys(a,b,x.child[j],st);
}
}
}
public boolean Contain(int k) {
if (this.Search(root, k) != null) {
return true;
} else {
return false;
}
}
public static void main(String[] args) {
BTree t=new BTree(3);
t.Insert(3);
t.Insert(14);
t.Insert(7);
t.Insert(1);
t.Insert(8);
t.Insert(5);
t.Insert(11);
t.Insert(17);
t.Insert(13);
t.Insert(6);
t.Insert(23);
t.Insert(12);
t.Insert(20);
t.Insert(9);
t.Insert(87);
t.Insert(34);
t.Show();
System.out.println("-----");
t.Remove(7);
t.Remove(6);
t.Remove(1);
t.Remove(11);
t.Show();
}
}
