在做java web云盘的时候，遇到了一个诡异的错误。用户注册时，需要用ajax判断该邮箱是否被注册。一开始没有发现问题，有一次测试注册的时候，却发现邮箱验证出现了异常，浏览器F12打断点，ajax请求直接进了error，后台打断点也没有进入。返回的error是一大串html代码，完全让我摸不着头脑。

开始检查dataype，data，url，没有错误啊。还是不行，开始去网上搜偏方子，试了很多方法，都是错误，只不过报错不一样了。。。于是很纳闷，老子写过那么多ajax了，什么样的请求没遇见过？验证邮箱这种请求，就给一个参，返回一个true or false ，哪里有理由出错？之后继续调试，发现必须要随便登录过一个账号，然后再返回注册，这个ajax才能正常请求。瞪了快半个晚上还是没有没看出来原因，就先放一边了。

今天在测试Android的请求时候，再次写了一下这个请求，本来想扔在浏览器敲回车，看看返回的是不是我想要的数据格式，结果跳转到了登录页面？恍然大悟，后台做了拦截器，拦截了所有controller，除了登录的controller请求，如果没有session（没登录），就跳转到登录页面。所以必须要登录之后才能注册的原因是这个，我把邮箱验证也给拦截掉了。修改下代码，问题解决。

红黑树（red black tree）是AVL树的一个变种，如果还不是十分了解AVL树，建议先读一下之前写的平衡二叉树的文章。 平衡二叉树（AVL树）的实现

红黑树是具有下列着色性质的二叉查找树：
1.每一个节点或者着成红色，或者着成黑色；
2.根是黑色的；
3.如果一个节点是红色的，那么它的子节点必须是黑色的；
4.从一个节点到一个NULL指针的每一条路径必须包含相同数目的黑色节点。

自底向上插入的过程

图二是对图一插入25的结果，父节点为黑色，无冲突，不需要调整。

在继续讲解之前，必须要确认一下各节点的叫法

以下是两种冲突情况

1.红父红叔

有一种特殊情况，如图四调整后的就是我们的红黑树，也就是说G是根节点，那么此时的调整方法是将G染成黑色即可。

我们对图二插入54的结果如下，当前节点由54变为了50。

2.红父黑叔

剩下两种镜像情况

现在对图五的红黑树进行再次调整，调整结果见图八，图中已经标注了X、P、G、U，不理解的再看看上面两张图。其余情况不再举例了。

红黑树的插入操作不是很复杂，这里强烈建议你自己写一些数字然后按照上面的插入过程一个个走一遍，这样印象会非常深刻，也能更加深入的了解这个过程，你一定会感叹，红黑树真是巧妙。例如：10，5，6，16，1，11，12，21，15，17，14 按顺序插入的最终结果如图九所示。

自底向上删除的过程

总体上来看分为两大步

第一步，将红黑树当一棵普通的二叉查找树，将节点删除

case 1：被删除的节点是叶子节点，直接删除节点。
case 2：被删除的节点只有一个孩子，不管是左孩子还是右孩子，删掉节点后，用孩子代替删除的节点
case 3：被删除的节点有两个孩子，先查找到这个节点的后继节点，（比它大的最小节点），用后继节点的值替代想要删除节点的值（想要删除的节点颜色不需要改变），然后删除掉后继节点。这样又巧妙地将问题转化为删除后继节点的情况了。因为删除后继节点，一共只有两种情况，要么为叶子节点，要么为只有一个有孩子的节点，不可能出现其它情况。这两种情况也就是case 1和case 2。

第二步，通过旋转和染色等一系列操作，使之重新成为一棵红黑树

下面开始详细分析。由第一步，不难明白，其实只要讨论删除的节点是叶子节点或只有一个孩子就可以。

case 2 比较简单，只有一种情况，当然要是细分的话，也可以分为两种镜像情况。这种情况是想要删除的节点为黑色，而且唯一的孩子是红色，当然，孩子的位置是无所谓的。为什么唯一的孩子是红色呢，因为如果是黑色，肯定会违反性质4。那为什么想要删除的节点不能为红色呢？那么我们假设想要删除的节点为红色，当然它也只有一个孩子，假如这个孩子是红色的，不管是左孩子还是右孩子，肯定都违反了红节点不能有红色儿子的要求（性质3）。假如这个孩子是黑色的，不管是左孩子还是右孩子，肯定违反了性质4。所以想要删除的节点不可能是红色。调整方法，简单明了，孩子替换父亲，并且染成黑色即可。见图十,D是我们想要删除的节点，P代表它的父节点，没有颜色说明什么颜色都可以，和D垂直，说明D是P的左孩子还是右孩子没有关系。

case 1 分为两大类，第一类，叶子节点是红色，直接删除，结束（见图十一）。额？这也算一个大类，其实是因为下一类情况特别麻烦

第二类，想要删除的叶子节点是黑色。这个可就要分为好多种情况了。

情况1 兄弟节点为黑色，且远侄子节点为红色。见图十二，没有上色说明什么颜色都可以。SL无论黑色红色都属于这种情况。（注意：如果SL是黑色的话，那么它一定是空节点NULL；如果SL是红色的话，那么它肯定和SR一模一样，只有有两个黑色的NULL节点）

对于这种情况，删除掉D后，有一边会少了一个黑色节点，但有一个侄子是红色的，那么我们可以通过旋转和染色重新完成平衡，这个过程在P的内部就可以解决，所以和P的颜色无关。调整过程为将P和S的颜色互换，然后进行一次右旋，最后将SR染成黑色即可。（以第一种情况说明）

情况2 兄弟节点为黑色，近侄子节点为红色，且远侄子节点为黑色（也就只能是NULL节点）。为什么远侄子节点一定是黑色的呢，如果是红色的话，不就是第一种情况了么，所以一定是黑色，如果是黑色的话，一定是NULL节点。如图十三。调整方法是对S进行左旋，然后调换S和SL的颜色，你会发现调整后的样子就是我们上面图十二讨论的情况，只不过SL是黑色的NULL节点罢了，然后再执行一次上面那种情况的调整。

情况3 兄弟节点为黑色且兄弟节点的孩子是NULL，父节点为红色。见图十四，调整方法是删除D后，将P变成黑色，反正P的父亲肯定是黑色，不会产生冲突，然后将S染成红色，这样，路径上的黑色节点数就和原来一样了。

情况4 兄弟节点为黑色且兄弟节点的孩子是NULL， 父节点为黑色，和上面那种情况很像。见图十五。我们删了一个黑色节点，剩下的也全是黑节点，这种情况下，再怎么调整也无法保持黑色路径上的黑色节点数和原来一样了。只能先暂时像情况3一样操作，然后把P当做起点，再次向上调整。

情况5 待删除节点的兄弟节点为红色。见图十六，调整方法是将兄弟节点和父节点颜色调换，然后执行一次旋转。调整后待删除节点的兄弟节点就又变成了黑色，观察下上面说的四种情况，它们的兄弟节点都是黑色，所以调整后又回到了上述四种情况之一，具体是哪一种情况，就要看调整后兄弟节点的孩子情况了。

至此，删除节点所有情况全部分析完毕。

代码实现

写完插入节点后，觉得只要细心就可以完成，所以删除操作偷懒没有写....插入是ojbk的。

红黑树的定义

const int red = 0;
const int black = 1;

class RBTree {
public:
    int color;            //颜色
    int key;            //键值
    RBTree *parent;        //父节点
    RBTree *left;        //左孩子
    RBTree *right;        //右孩子

    RBTree()
    {
        color = red;
        key = -999;
        parent = NULL;
        left = NULL;
        right = NULL;
    }
};

判断此节点是否是父节点的哪一个孩子

/*
判断此节点是否是父节点的左孩子
    1 左孩子
    0 右孩子
    -1 当前节点是根节点
*/
int isLeft(RBTree *p)
{
    if (p->parent == NULL)
    {
        return -1;
    }
    if (p == p->parent->left)
    {
        return 1;
    }
    return 0;
}

/*
红父红叔冲突，调整节点颜色
*/
void adjustColor(RBTree*& p)
{
    //祖父染成红色
    p->parent->parent->color = red;
    //祖父的两个孩子染成黑色
    if (p->parent->parent->left != NULL)
    {
        p->parent->parent->left->color = black;
    }
    if (p->parent->parent->right != NULL)
    {
        p->parent->parent->right->color = black;
    }

}

/*左旋转*/
RBTree* SingleRotateWithLeft(RBTree*& X)
{
    RBTree *P = X->parent;
    RBTree *G = P->parent;
    RBTree *U = G->right;

    RBTree* parent = G->parent;
    //查询祖父在祖父父亲的位置
    int pos = isLeft(G);
    //
    G->left = P->right;
    P->right->parent = G;
    G->parent = P;
    G->color = red;
    P->right = G;
    P->parent = parent;
    P->color = black;

    
    if (pos == 1)
    {
        parent->left = P;
    }
    else if (pos == 0)
    {
        parent->right = P;
    }
    return P;
}

/*右旋转*/
RBTree* SingleRotateWithRight(RBTree*& X)
{
    RBTree* P = X->parent;
    RBTree* G = P->parent;
    RBTree* U = G->left;
    RBTree* parent = G->parent;
    //查询祖父在祖父父亲的位置
    int pos = isLeft(G);
    G->right = P->left;
    P->left->parent = G;
    G->parent = P;
    G->color = red;
    P->color = black;
    P->left = G;
    P->parent = parent;
    
    if (pos == 1)
    {
        parent->left = P;
    }
    else if (pos == 0)
    {
        parent->right = P;
    }
    return P;
}

/*左-右双旋转*/
RBTree* DoubleRotateWithLeft(RBTree *&X)
{
    RBTree* P = X->parent;
    RBTree* G = P->parent;
    RBTree* U = G->right;
    RBTree* parent = G->parent;
    //查询祖父在祖父父亲的位置
    int pos = isLeft(G);
    P->right = X->left;
    if(X->left)
        X->left->parent = P;
    G->left = X->right;
    if(X->right)
    X->right->parent = G;
    X->left = P;
    X->right = G;
    P->parent = X;
    G->parent = X;
    X->parent = parent;
    
    if (pos==1)
    {
        parent->left = X;
    }
    else if(pos==0)
    {
        parent->right = X;
    }
    //染色
    X->color = black;
    G->color = red;

    return X;
}

/*右-左双旋转*/
RBTree* DoubleRotateWithRight(RBTree * &X)
{
    RBTree* P = X->parent;
    RBTree* G = P->parent;
    RBTree* U = G->left;
    RBTree* parent = G->parent;
    //查询祖父在祖父父亲的位置
    int pos = isLeft(G);
    G->right = X->left;
    if(X->left)
        X->left->parent = G;
    P->left = X->right;
    if(X->right)
        X->right->parent = P;
    X->left = G;
    X->right = P;
    G->parent = X;
    P->parent = X;
X->parent = parent;
    
    if (pos == 1)
    {
        parent->left = X;
    }
    else if (pos == 0)
    {
        parent->right = X;
    }
    //染色
    X->color = black;
    G->color = red;

    return X;
}

/*
调整红黑树
*/
void adjustRBTree(RBTree*& root,RBTree*& p)
{
    //父亲空指针，不需要判定
    if (p->parent == NULL)
    {
        //重新设置根节点
        root = p;
        return;
    }
    //祖父空指针，不需要判定
    if (p->parent->parent == NULL)
    {
        return;
    }
    //没有冲突，结束
    if (p->color==black||p->parent->color == black)
    {
        return;
    }
    //判断当前节点的父亲是祖父的左孩子还是右孩子
    int fPos = isLeft(p->parent);
    //红父红叔冲突
    if ((fPos==1 && (p->parent->parent->right != NULL && p->parent->parent->right->color == red))
        || (fPos==0 && (p->parent->parent->left != NULL && p->parent->parent->left->color == red))) {
        //调整颜色即可，不需要旋转
        adjustColor(p);
        //祖宗是根节点，调整它的颜色就可以了
        if (p->parent->parent->parent == NULL)
        {
            p->parent->parent->color = black;
        }
        //将祖父节点设置为当前节点，继续调整
        else
        {
            adjustRBTree(root,p->parent->parent);
        }
    }
    //红父黑叔冲突
    else
    {
        //判断当前节点是父节点哪一个孩子
        int pos = isLeft(p);
        RBTree* result;
        //左左
        if (fPos==1&&pos==1)
    {
            result = SingleRotateWithLeft(p);
        }
        //右右
        else if (fPos==0 && pos==0)
        {
        result = SingleRotateWithRight(p);
        }
        //左右
        else if (fPos==1 && pos==0)
        {
            result = DoubleRotateWithLeft(p);
        }
        //右左
        else
        {
            result = DoubleRotateWithRight(p);
        }
adjustRBTree(root,result);
    }
}

/*
*插入节点
*/
void insert(RBTree*& root, int val)
{
    if (root == NULL)
    {
        root = new RBTree();
        root->key = val;
        root->color = black;
            return;    }

    RBTree *t = root;
    //将要插入的节点
    RBTree *p = new RBTree();
    p->key = val;
    //先将节点插入叶子节点里
    while (true) {
        if (val > t->key)
        {
        if (t->right == NULL)
            {
                t->right = p;
                p->parent = t;
                break;
            }
            else
            {
                t = t->right;
            }
        }
        else if (val < t->key)
        {
            if (t->left == NULL)
            {
                t->left = p;
                p->parent = t;
                break;
            }
            else {
            t = t->left;
            }

        }
        else
        {
            return;
        }
    }

    //开始调整红黑树
    adjustRBTree(root,p);

}

附上cpp代码 点击下载

我们常看到的查找树都是二叉树，如二叉查找树，AVL树、伸展树等，但还有一种常用的查找树不是二叉树。这种树叫B-树，是一种多叉树。

 阶为M的B-树是一棵具有下列结构特性的树

• 树的根或者是一片树叶，或者其儿子数在2和M之间。（根可以是叶子节点，不是的话，儿子数就要在2-M之间）
  
• 除根外，所有非树叶节点的儿子树在┌M/2┐和M之间。
• 所有的树叶都在相同的深度上。

这是一棵4阶的树，可以仔细观察下。之后的插入操作都会以这棵树为demo。

应符合以下条件

• 不管什么结点，都至多有

  M  -1个关键字，

  M  棵子树（假如可以有子树的话）  ；

• 根结点如果不是叶子结点的话，那么至少有两棵子树，即至少1个关键词 ； 
• 除根以外的所有结点（包括树叶），至少有┌M/2┐-1个关键字；（┌M/2┐是取上整，└M/2┘是取下整） 
• 根据上面也不难想到  非叶子结点的关键字个数=指向儿子的指针个数-1；

有两种比较流行的B-树，一种是实际数据只存储在树叶上，还有一种是允许存储在内部节点上，如二叉查找树中所做的那样。在这里我使用的是第二种，内部节点也可以存储值。

B-树有两个比较关键的操作，插入及删除，比较麻烦。

插入的过程

    前三个节点插入比较简单，按顺序插入即可，此时根节点也是叶子节点。插入的时候先不管是否会超出m阶树的上限要求，因为定义时我们也会额外开辟一些空间。

    第四个值15，首先查找到已经有这个值了，那么便不进行插入。插入第五个值48，发现这个节点已经有4个关键字了，已经超过了要求。那么需要进行分裂。分裂操作是插入操作过程中一个最重要的操作，因为这是处理“冲突”（即结点中的数据元素大于B树规则中要求的最大个数）的一个通用的处理方式，这种方式必须要对所有的情况都适用，而分裂是解决这一问题一种方法。分裂需要父节点腾出一个key和一个child的位置，然后在需要分裂的节点里取出中间元素放进父节点腾出的key里。需要分裂的节点被一分为二，分别作为父亲的儿子。

第六个节点16插进去没有问题，下一个插入节点4，发现需要分裂。将中间元素16放进父节点。

继续插入30,17，43，插入43后需要继分裂

插,20,9无问题，25的时候需要再次分裂

42移动到父节点之后，父节点的关键字数量也超过了限制，那么父节点也需要进行一次分裂，将中间元素抽出来当做新的父节点，如下图

插入7，继续分裂

插入21，无问题，插入22，进行分裂。

分裂完之后，发现它的父节点需要继续分裂

最终所有节点插入完成。也就是这篇文章第一张图片的那棵树。

删除的过程

删除分两种情况。第一种删除的是叶子节点，如果删除之后，关键字数量还能满足要求，则结束，否则调用合并函数，合并函数是先尝试向兄弟节点借一个关键字，如果兄弟也不够了的话，就合并。
第二种是删除内部节点，找到子树中最大的一个关键字替换它（一定是叶子节点），然后对那个叶子节点执行删除，回到第一种情况。
文字不是非常理解没关系，下面上图。

这是一个5阶的B树，我们先删除0，去掉0之后，叶子节点仍然满足要求，删除结束。

我们接着删除12，我们要从这个节点的子树里找到一个关键字代替它，有两种方法，用比12小的最大关键字或比12大的最小关键字代替12(也就是前驱或者后继)，然后删掉那个儿子中的关键字，如下图。

在这两种方法里，代码实现的是第一种方式。第一种，删除11后，发现叶子节点只有一个10（图见上图中的第一种），关键字个数少于2个，此时应该合并，合并同样也有两种方式，和前一个兄弟节点合并或者后一个兄弟节点合并。

代码实现的是第一种，和前一个兄弟合并。接着我们删除9，尝试向前一个兄弟借个关键字，发现要是它借了，它也就不满足了，这时候我们就需要合并节点了，如下图。

现在我们来皮一下，直接删除根节点21。按照之前说到的，先找到比它小的最大关键字，一定在叶子节点里面，最大为20，替换根节点21后，然后删除叶子节点中的20。

发现叶子节点不满足条件了，向兄弟借一个关键字后变成下图。

接着删除17，兄弟无法帮助你，只能再次合并，结果如下。

父节点借出一个后，自己也不够了，需要对父节点再次进行合并，结果如下。

至此，删除操作的各种情况就都讲完了。在编写代码的时候，有一种特殊情况需要注意，对下面这种情况进行删除2的时候，正常合并结果如下。

因为根节点的关键字最少可以为1，所以一直没有对根进行合并，也没人能和根合并。。。遇到这种把根都删到没有关键字的时候，就需要重新设置根为原来根的第一个儿子了，代码里有体现。

代码实现

static const int m = 4;    //m阶
class BTree {
public:
    int keynum;
    int key[m + 1];                //关键字数组，多开辟一个，从1开始  0号未用， key[m]是临时空间
    BTree * parent;                //父节点指针
    BTree child[m + 1];            //孩子结点指针数组，多开辟一个  child[m]是临时空间

    //这里还涉及一个问题，如何判断一个节点是否是叶子节点，叶子节点的child[0]必定为空
    //非叶子节点的child[0]不为空
    BTree() {
        keynum = 0;
        for (int& k : key)
            k = -999;
        parent = NULL;
        for (BTree n : child) n = NULL;
    }
};

/这个结构体是查询节点返回的结果
如果，isquery是true，表明找到了这个节点，即node
如果，isquery是false，表明没有这个节点，失败于某个终端结点上，即node
如果找到了这个节点，p是在关键字中的位置，如果没有找到，返回的是应该插入的位置，例如叶子节点 1 3 5 ，寻找 4，返回的是3，方便插入。（都从1开始计数）/
struct Result {
    BTree *node;
    bool isquery;
    int p;
};

/*非递归查询节点*/
Result* findBTree(BTree* root, int k)
{
    Result* result = new Result();
    if (root == NULL)
    {
        return NULL;
    }
    BTree *r = root;
    int index = 1;
    int nowKey = r->key[index];
    while (r != NULL)
    {
        index = 1;
        while (index <= r->keynum)    //遍历所有关键字
        {
            if (r->key[index] == k)
            {
                //找到该节点
                result->isquery = true;
                result->p = index;        //该关键字在节点的位置
                result->node = r;
                return result;
            }
            if (k > r->key[index])
            {
                /*如果相等，则说明，r里面的最后一个关键字都没有k大*/
                if (index == r->keynum)
                {
                    /*r已经是叶子节点了*/
                    if (r->child[index] == NULL)
                    {
                        //没有该节点
                        result->isquery = false;
                        result->node = r;
                        result->p = index + 1;
                        return result;

                    }
                    /*还有儿子，遍历儿子*/
                    r = r->child[index];
                    break;
                }
                /*还没到最后一个关键字，继续遍历这个r*/
                index++;
                nowKey = r->key[index];
                continue;
            }
            /*比上一个大，比这一个小，应该遍历它的儿子，如果有儿子的话*/
            if (k < r->key[index])
            {
                /*是叶子节点，没儿子，无查找的节点*/
                if (r->child[index - 1] == NULL)
                {
                    result->isquery = false;
                    result->node = r;
                    result->p = index;
                    return result;
                }
                r = r->child[index - 1];
                break;
            }
        }

    }
}

/*递归查询节点*/
Result * findTree2(BTree* root, int val)
{
    Result *result = new Result;
    if (!root) {
        return NULL;
    }

    //如果比第一个关键字小，检索第一个儿子
    if (val < root->key[0] && root->child[0])
    {
        return findNode(root->child[0], val);
    }
    //如果比最后一个关键字大，检索最后一个儿子
    if (val > root->key[root->keynum - 1] && root->child[root->keynum])
    {
        return findNode(root->child[root->keynum], val);
    }
    //单独判读最后一个key
    if (val == root->key[root->keynum - 1])
    {
        result->node = root;
        result->isquery = true;
        result->p = root->keynum - 1;
        return result;
    }
    //在最边上两个关键字中间
    for (int i = 0; i < root->keynum - 1; i++) {
        if (val == root->key[i])
        {
            result->node = root;
            result->isquery = true;
            result->p = i;
            return result;
        }
        else if (val > root->key[i] && val < root->key[i + 1]) {
            return findNode(root->child[i + 1], val);
        }
    }
    //没有这个值，返回父节点，也就是某个最低层的非终端结点上
    result->node = root->parent;
    result->isquery = false;
    return result;
}

/*插入节点*/
void insertBTree(BTree* &root, int val)
{
    /*考虑B-树为空的情况*/
    if (root == NULL)
    {
        root = new BTree();
        root->key[1] = val;
        root->keynum = 1;
        return;
    }
    /*查找这个节点*/
    Result *r = findBTree(root, val);
    BTree* p = r->node;
    if (r->isquery)
    {
        //查找到了这个节点,无需插入
        return;
    }
    else
    {
        p->keynum++;                //不管怎么样，先往叶子节点里面插入
        for (int index = p->keynum; index > r->p; index--)
        {
            p->key[index] = p->key[index - 1];    //关键之往后挪一格
            p->child[index] = p->child[index - 1];    //儿子也是一样，既然叶子节点儿子都为空，那这一行就无所谓了。
        }
        p->key[r->p] = val;
        p->child[r->p] = NULL;

        /*需要分裂*/
        if (p->keynum == m)
        {
            splitBTree(p);
        }
    }
    return;
}

/*分裂*/
void splitBTree(BTree*  T)
{
    BTree* t1, *t2;
    int index, index_1;
    /*已经传递到根节点了，根也需要分裂*/
    if (T->parent == NULL)
    {
        t1 = new BTree();
        t2 = new BTree();
        t1->keynum = m / 2;
        t2->keynum = m - m / 2 - 1;
        t1->parent = T;
        t2->parent = T;

        /*初始化t1*/
        for (index = 0; index <= m / 2; index++)
        {
            t1->key[index] = T->key[index];

            /*不是叶子节点，就还需要重新分配子树*/
            if (T->child[index] != NULL)
            {
                t1->child[index] = T->child[index];
                T->child[index]->parent = t1;        //还需要更新子树的父节点
            }
        }

        /*初始化t2*/
        t2->child[0] = T->child[m / 2 + 1];
        for (index = m / 2 + 2; index <= m; index++)
        {
            t2->key[index - m / 2 - 1] = T->key[index];

            if (T->child[index] != NULL)
            {
                t2->child[index - m / 2 - 1] = T->child[index];
                T->child[index]->parent = t2;
            }

        }
        T->keynum = 1;
        T->child[0] = t1;
        T->child[1] = t2;
        T->key[1] = T->key[m / 2 + 1];
        for (index = 2; index <= m; index++)
        {
            T->child[index] = NULL;
            T->key[index] = -999;
        }
        return;
    }
    else
    {
        /*查询这个节点在父节点中的位置，（从0开始）*/
        index = whichSon(T);
        for (index_1 = T->parent->keynum; index_1 > index; index_1--)
        {
            T->parent->key[index_1 + 1] = T->parent->key[index_1];
            T->parent->child[index_1 + 1] = T->parent->child[index_1];
        }
        T->parent->keynum++;
        T->parent->key[index + 1] = T->key[m / 2 + 1];
        /*t2为新的节点*/
        t2 = T->parent->child[index + 1] = new BTree();
        t2->keynum = m - (m / 2 + 1);
        t2->parent = T->parent;
        /*因为没有key[0]，所以要单独初始化child[0]，不用for一起初始化*/
        t2->child[0] = T->child[m / 2 + 1];
        /*初始化t2*/
        for (index = m / 2 + 2; index <= m; index++)
        {
            t2->child[index - m / 2 - 1] = T->child[index];
            t2->key[index - m / 2 - 1] = T->key[index];
        }

        T->keynum = m / 2;
        for (index = (m / 2) + 1; index <= m; ++index)  //初始化T
        {
            T->child[index] = NULL;
            T->key[index] = -999;
        }
        /*父亲也需要分裂，递归*/
        if (T->parent->keynum == m)
        {
            splitBTree(T->parent);
        }
        return;
    }
    
}

/*查询T是父节点的第几个孩子(从0开始计数)  失败返回-1*/
int whichSon(BTree* T)
{
    int index = -1;
    if (T == NULL)
        return -1;
    for (index = 0; index <= T->parent->keynum; index++)
    {
        if (T == T->parent->child[index])
            return index;
    }
    return -1;
}

/*寻找当前节点所有儿子中最大的关键字*/
Result* findMax(BTree* T)
{
    if (T == NULL) return NULL;
    BTree *p = T;
    while (p->child[p->keynum] != NULL)
        p = p->child[p->keynum];
    Result *r = new Result();
    r->isquery = true;
    r->node = p;
    r->p = p->keynum;
    return r;
}

void borrowBNode(BTree* &root, BTree *T)
{
    int mynum, bronum, index;
    BTree* b;
    BTree* f = T->parent;
    /*考虑父节点不存在的情况，理论上是不会出现这种情况*/
    if (f == NULL)
    {                                            
        return;
    }
    /*找到当前节点是父节点的第几个儿子（从0开始 */
    mynum = whichSon(T);
    if (mynum == 0)
        bronum = 1;
    else
        bronum = mynum - 1;
    b = f->child[bronum];

    /*如果兄弟帮不了你，即它给你一个关键字，它就不满足条件了*/
    if (b->keynum == (m + 1) / 2 - 1)
    {
        /*和兄弟合并*/
        /*如果我是第一个节点*/
        if (bronum > mynum)
        {
            /*交换T和b的值，再进行合并，保证b是T父节点的前一个儿子*/
            BTree *tmp = T;
            T = b;
            b = tmp;
            int tmpp = bronum;
            bronum = mynum;
            mynum = tmpp;
        }

        /*现在b一定是在T前面，T合并到b里*/
        b->keynum++;
        b->key[b->keynum] = f->key[mynum];
        b->child[b->keynum] = T->child[0];
        for (index = 1; index <= T->keynum; index++)
        {
            b->keynum++;     
            b->key[b->keynum] = T->key[index];
            b->child[b->keynum] = T->child[index];
        }
        /*调整父节点*/
        for (index = mynum; index <= f->keynum; index++)
        {
            f->key[index] = f->key[index + 1];
            f->child[index] = f->child[index + 1];
        }
        f->keynum--;
        f->key[0] = -999;
        /*父节点不是根节点，且不满足条件，也需要调用合并函数*/
        if (f->keynum <= (m + 1) / 2 - 2 && f->parent != NULL)
        {
            borrowBNode(root, f);
        }
        /*根节点已经删的没有关键字了，重新设置根节点*/
        if (root->keynum == 0)
        {
            if (root->child[0] != NULL)
                root = root->child[0];
        }
    }
    /*如果兄弟可以帮你*/
    else
    {
        /*如果我是第一个节点*/
        if (bronum > mynum)
        {
            T->keynum++;
            T->key[T->keynum] = f->key[bronum];
            T->child[T->keynum] = b->child[0];
            f->key[bronum] = b->key[1];
            b->child[0] = b->child[1];
            for (index = 1; index <= b->keynum; index++)
            {
                b->child[index] = b->child[index + 1];
                b->key[index] = b->key[index + 1];
            }
            b->keynum--;
        }
        /*如果我不是第一个节点*/
        else
        {
            T->child[1] = T->child[0];
            for (index = 1; index <= T->keynum; index++)
            {
                T->key[index + 1] = T->key[index];
                T->child[index + 1] = T->child[index];
            }
            T->child[0] = b->child[b->keynum];
            T->key[1] = f->key[mynum];
            f->key[mynum] = b->key[b->keynum];
            T->keynum++;
            b->child[b->keynum] = NULL;
            b->key[b->keynum] = -999;
            b->keynum--;

        }

    }
}

/*删除节点*/
void deleteBTree(BTree* &root, int val)
{
    int index;
    if (root == NULL)
        return ;
    Result* r = findBTree(root, val);
    /*没查询到这个节点*/
    if (!r->isquery)
        return ;
    BTree* p = r->node;
    /*如果是叶子节点*/
    if (r->node->child[0] == NULL)
    {
        for (index = r->p; index <= p->keynum; index++)
        {
            p->key[index] = p->key[index + 1];
        }
        p->key[p->keynum] = -999;
        p->keynum--;
        /*叶子节点关键字数量不够。既是树叶同时又是根的话就不需要合并了，只需要关键字数大于1就行了*/
        if (p->keynum <= (m + 1) / 2 - 2 && p->parent != NULL)
        {
            /*借兄弟节点*/
            borrowBNode(root, p);
        }
        return ;
    }
    /*如果是内部节点*/
    else
    {
        /*找到儿子里的最大节点，替换要删除的节点*/
        Result *re = findMax(p->child[r->p - 1]);
        BTree *q = re->node;
        p->key[r->p] = q->key[re->p];
        q->key[re->p] = -999;
        q->keynum--;
        /*如果叶子节点关键字数量不够*/
        if (q->keynum <= (m + 1) / 2 - 2)
        {
            /*借兄弟节点*/
            borrowBNode(root, q);
        }
        return ;
    }
}

        在写首页的展示文章功能的时候，当然是少不了分页的。文章需要展示标签，一篇文章可能有多个标签，是一对多的关系。某一篇文章有四条数据，如图

        测试一页展示两篇文章的时候，惊奇的发现，那一页只显示了一篇文章"使用正则获取..."，而且四个标签只显示了两个，再看下上面查询的结果，似乎明白了，下一页是同样也是只有一篇文章，标签是剩下的两个。

        因为一篇文章有多个标签，所以limit不能写死，如下，要不然谁知道你一页会有几篇文章呢，反正一页的标签数是肯定一样的了。

select
    a.*,t.*
    from article a,tag t,article_tag a_t 
    where a.articleId=a_t.articleId and t.tagId=a_t.tagId
    order by pubdate desc
    limit 5,2

        这时候想到的办法是是limit需要一个公式，动态的来分页，上面语句里的5和2都应该是动态变化的，比如一页十篇文章。但问题也随之而来，我如何知道第一页应该是哪十个？这个可以根据group by (articleId) 来保证一篇文章只显示一次，但又该如何知道一篇文章有几个标签，用count?那一篇文章就要查一次，效率实在低下，这个思路就先放一放了。

        那我们就一次查询完所有文章，然后前台分批次去取数据，但想一下，如果上万条文章怎么办，这一次查询要多久....而且查了那么多数据，我根本看不到那里，白查!不可取。

        那我只能先查文章主表，查出十条记录，然后在到关系表中查到相关的标签，一条文章就要查询一次标签。效率也比较低下。项目跑起来效果的确是这样，刷新一次需要等待肉眼可见的时间，体验很差。。。但就先凑活着，我相信这绝对不是好方案，sql会有相关的知识，而我不知道罢了。

        果然两三天后，一不小心浏览到group_concat，能将多行数据整合到一行上面，配合group by 的话，这不就是我想要的吗？立刻尝试编写sql语句

select   
    a.*,group_concat(t.tagName)
    from article a,tag t,article_tag a_t
    where a.articleId=a_t.articleId and t.tagId=a_t.tagId
    group by articleId
    order by pubdate desc

        视图多了一个长文本字段，查看一下，会发现已经把所有想要的添加进来了，并且默认使用逗号进行分割，总算找到你了，知识的广度很重要。

        下面就只要修改下mapper的XML文件，大功告成了。刷新下主页，获取文章的速度明显变快。

  <resultMap id="ArticleTagMap2" type="net.peihuan.entity.Article" extends="ResultMapWithBLOBs">
    <result column="group_concat(t.tagName)" property="grouptags" jdbcType="LONGVARCHAR" />
  </resultMap>
  <!-- 查询所有文章基本信息及他们的标签 -->
  <select id="selectAllArticlesWithTags" parameterType="map" resultMap="ArticleTagMap2">
    select
    a.*,group_concat(t.tagName) from
    article a,tag t,article_tag a_t
    where a.articleId=a_t.articleId
    and t.tagId=a_t.tagId
    group by articleId
    order by pubdate desc
    limit #{beginIndex},#{offset}
  </select>

        发现mybatics自带分页功能，可以了解一下。

我的博客

        我想绝大多数写代码的都想有一个属于自己的域名，属于自己的网站，我也一样，只不过一直没有机会实现。但自从某日浏览了一个博客，嗯，这也太好看了吧？怎么做的？教练，我想学这个...恰巧这段时间刚好在学web开发，天时地利人和。

        看了下喜欢的那个博客，down下来是hexo的主题，看着一堆没见过的后缀名，和屏幕对脸懵逼，啥玩意啊，不会用。不会前端，只会简单改改html文件，于是便使用wget命令直接把整个网站拿了下来变成了静态的。前台剩下也就没什么了。

        后台使用的java开发，IDE用的idea，稍微有点jsp、servlet的底子，会写个简单的注册登录。但想用框架，花了一天时间按网上的教程搭了个ssm框架，写了个简单的demo，算是完成了。剩下的无非就是对数据库的增删改查了，富文本编辑器一开始用的百度的，但一直乱码，百度貌似也不维护了，最后换了wangeditor，非常轻量简洁，很喜欢。

        功能基本完成的差不多之后，觉得URL里面是jsp非常丑，其实前台全部使用的ajax异步获取的数据，遂全部将后缀改成html。还有一些小问题还需要慢慢解决！如有人发现了一些bug，请告知我，不胜感激。

个人

        95后，即将毕业于某小县城末流二本。

        不抽烟、不喝酒、不近女色（假的）、

        喜欢技术，热衷于制造bug！

        喜欢唱歌，可惜五音不全、喜欢跳舞，可惜肢体不协调、

        喜欢画画，又奈何是个灵魂画手、

        喜欢吹笛子，奈何连声都吹不响、

        喜欢虾jb逛，不对，喜欢旅游，但是又穷、

        能玩的起来的也就是睡睡觉、打打王者了

        攒钱，有很多想去的地方、

        搞艺术是不可能搞艺术的了，这辈子都搞不起来了，超级羡慕会唱歌跳舞画画之类的，现在只能靠搬搬代码这样子才
        能维持得了生活，github里面的老哥个个都是人才，说话又好听，我超喜欢这里的。

在搭建这个博客的时候，前台一开始都使用的jsp，使用了很多<% %>，比较难看，可读性也较差，后来逐渐全部换成了ajax获取数据，这时候觉得已经没必要使用jsp了。

使用jsp后缀也导致URL链接也非常丑（个人感觉），遂把所有jsp后缀改成html。刷新页面发现报错，

<%request.getParameter("xxx")%>

因为不是jsp，所以这种方法也行不通了。
但js里面有一个方法可以获取页面的URL地址

window.location 对象所包含的属性

window.location.search 来获取?之后的所有参数。

window.location.search.substr(1)

使用substr(1)来去掉 ? 

reg = new RegExp("(^|&)" + name + "=([^&])(&|$)", "i");

使用正则，如下图，i表示忽略大小写

var r = window.location.search.substr(1).match(reg);

匹配之后会的r为一个数组，长度为4。第一个是整个匹配的字符串，第二个是group1，第三个是group2,第四个是group3。因为使用了捕获，如果不行使用捕获的话括号里面加个?:就可以了。如(?:^|&)。

那么r[2]就是我们想要的参数，完整函数如下

function getQueryString(name) {
    var reg = new RegExp("(^|&)" + name + "=([^&])(&|$)", "i");
    var r = window.location.search.substr(1).match(reg);
    if (r != null) return decodeURI(r[2]); return null;
}

复习一下平衡二叉树，经常混以为就是最优二叉树，其实是最优二叉树是哈夫曼树，这个以后有机会再说。

平衡二叉搜索树（Self-balancing binary search tree）又被称为AVL树（有别于AVL算法），且具有以下性质：它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树,它须保证树的深度是O(log N)。平衡二叉树的常用实现方法有红黑树、AVL、替罪羊树、Treap、伸展树等。 最小二叉平衡树的节点的公式如下 F(n)=F(n-1)+F(n-2)+1 这个类似于一个递归的数列，可以参考Fibonacci(斐波那契)数列，1是根节点，F(n-1)是左子树的节点数量，F(n-2)是右子树的节点数量。

  这里主要思考的是二叉树的插入节点。查询节点和修改节点的操作都可以以时间O(logN)的复杂度执行，假如删除使用惰删除的话，那么时间也是O(logN)。所谓惰删除就是当删除一个节点时，并不是真正的进行了物理删除，只是设置了一个字段来标记这个节点是否被删除。使用惰删除是有很多好处的，物理删除可能将会像插入节点一样需要进行旋转，当然也可能不需要。但如过后期又想添加之前删除的节点，那么又只能重新插入节点，很大几率要进行旋转操作。如果使用惰删除，那么时间复杂度将大大降低，但是相应的会使用额外的存储空间。

  如果插入一个节点将导致一个树的不平衡，那么会有一个必须重新平衡的节点叫做α。由于任意节点最多有两个孩子，因此高度不平衡时，α两棵子树的高度差为2，这种不平衡可能会出现以下四种情况：

1.对α的左儿子的左子树进行一次插入。
2.对α的左儿子的右子树进行一次插入。
3.对α的右儿子的左子树进行一次插入。
4.对α的右儿子的右子树进行一次插入。

  情况1和4是对称的，情况2和3是对称的，所以实际上只有两种情况，但是编程还是要写四种情况。
  情况1和4是插入发生在“外边”的情况，左-左，右-右，这种情况通过一次单选转就可以完成调整，剩下两种情况是插入发生在“内部”的情况，左-右，右-左，这种情况需要进行双旋转来进行调整。

插入原理

单旋转

  上图是左单旋转，对k2的左儿子k1的左子树进行的一次插入，X、Y、Z分别表示表示k1、k2的儿子，可以看见X明显比Y和Z深，且比Z深2层。为恢复平衡，就应该把X上移一层，Z下移一层，这样就变成了上图中旋转后的样子，k2变成了k1的右孩子，Y变成了k2的左孩子，X和Z不变。

  右旋转类似，对k1的右孩子k2的右孩子进行了一次插入，导致Z的深度比X大2，同样是把X下移一层，Z上移一层，k1就变成了k2的左孩子，Y变成了k1的右孩子。

  个人是这样记忆的，如何找到哪个是k1哪个是k2呢？k1和k2必定有一个是不平衡的，先找到这两个节点，然后不管是左还是右旋转，都让k1小于k2，也就是大的节点是k2，小的节点是k1，k1、k2互换高度，一个上移，一个下移。

双旋转

但是单旋转无法解决另外两种情况

  我们要把Y看成是一个根和两棵子树，B和C中有一个比D深两层（除非它们都是空的），我们不能确定是哪一棵，也不需要确定是哪一棵，上图中画的时候B和C全部画的比D低一层半。整颗子树，我们看成四棵子树A、B、C、D和三个节点！k1、k2、k3。
  为了重新平衡，我们不能让k3继续当根节点，k1页不行，唯一的选择就是k2当做新的根。k1、k3分别作为k2的左右孩子，巧妙的是，A、B、C、D四棵子树依旧是按顺序排列过去的。

右-左双旋转如上，基本差不多。

总结下，遇到双旋转，先找到k1、k2、k3，三个节点最小的是k1，最大的是k2，旋转后，k1是k2左孩子，k3是k2右孩子，A、B、C、D依旧是原顺序排列。

对于插入，最多只需要一次旋转（如果双旋转也只视作一次旋转）

删除原理

AVL树的删除和BST的删除较为类似，首先找到需要删除的节点，找到之后，分为三种情况进行删除。

• 需要删除的节点D是叶子节点，这种情况最简单，删除D之后，判断父节点DP是否需要调整，调整完成之后再调整DPP，DPPP，直到回溯到根节点。
• 需要删除的节点D有一个孩子，将D的值改为孩子的值，然后删除叶子节点，这样就把情况转换成第一种情况了。
• 需要删除的节点D有两个孩子，将D的值改为前驱或者后继的值，然后删除前驱或者后继的值，这样也就把情况装换成第一种情况了。

由此可见，我们只要重点讨论第一种情况就可以了，具体的删除流程如下：

1. 删除节点D
2. 判断删除节点的父节点DP是否满足AVL树的性质，如果不满足，则根据DP的状态进行旋转调整，并重新计算DP的高度，旋转分为四种情况，这里就不再细说。
3. 继续向上调整DPP，检查DPP的平衡是否遭到破坏，之后再继续向上调整DPP，直到调整到根节点为止（即不断执行第三步）。实际上这里可以进行优化，在调整过程中如果经过某一次的调整，树的高度没有发生变化，那么就不必向上回溯调整了。

如何判断是否需要向上回溯调整呢？根据平衡因子。
  如果删除一个节点后，平衡因子为1/-1，说明高度未发生变化，那么就不需要向上调整了；如果删除一个节点后，因子变成0，说明树高度一定发生了变化，那么就需要向上回溯调整。如果平衡因子为2/-2，说明需要调整这棵树需要调整。

这里可以看到AVL树的可视化。

代码实现

  将一个新节点，插入到AVL树中去，递归的插入到相应的子树中后，如果树的高度不变，那么插入完成，如果出现了高度不平衡，那么我们将做适当的双旋转或者单旋转，并更新这些高度。另外一个问题就是二叉树的高度信息的存储，由于真正需要的是实际是子树高度的差，并且它一般很小，（1,0，-1等）

java的完整实现 点这里

下面给出的是C的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

class AvlNode {
public:
    AvlNode *left;
    AvlNode *right;
    int val;
    int height;        //这个节点的高度

    AvlNode() {
        left = NULL;
        right = NULL;
        val = -9999;
        height = 0;
    }
    AvlNode(int v) {
        left = NULL;
        right = NULL;
        val = v;
        height = 0;
    }

};

1
2
3
4
5
6
7
8

/*返回某个节点的高度*/
static int Height(AvlNode* node)
{
    if (node == NULL)
        return 0;
    else
        return node->height;
}

1
2
3
4
5
6
7
8
9
10
11
12

/*左单旋转*/
static AvlNode* SingleRotateWithLeft(AvlNode *k2)
{
    AvlNode *k1 = k2->left;
    k2->left = k1->right;
    k1->right = k2;

    k2->height = max(Height(k2->left), Height(k2->right)) + 1;
    k1->height = max(Height(k1->left), k2->height) + 1;

    return k1;
}

1
2
3
4
5
6
7
8
9
10
11
12

/*右单旋转*/
static AvlNode* SingleRotateWithRight(AvlNode *k1)
{
    AvlNode *k2 = k1->right;
    k1->right = k2->left;
    k2->left = k1;

    k1->height = max(Height(k1->left), Height(k1->right)) + 1;
    k2->height = max(k1->height, Height(k2->right)) + 1;

    return k2;
}

1
2
3
4
5
6
7
8
9

/*左-右双旋转*/
static AvlNode* DoubleRotateWithLeft(AvlNode *k3)
{
    /*k1,k2先右单旋转*/
    k3->left = SingleRotateWithRight(k3->left);

    /*k3,k2再左单旋转*/
    return SingleRotateWithLeft(k3);
}

1
2
3
4
5
6
7
8
9

/*右-左双旋转*/
static AvlNode* DoubleRotateWithRight(AvlNode *k1)
{
    /*k3,k2先左单旋转*/
    k1->right= SingleRotateWithLeft(k1->right);

    /*k1,k2再右单旋转*/
    return SingleRotateWithRight(k1);
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

/*
向AVL树种插入节点
*/
AvlNode* insert(int val, AvlNode *T)
{
    if (T == NULL)
    {
        T = new AvlNode(val);
    }
    /*向左孩子插入*/
    else if (val < T->val)
    {
        T->left = insert(val, T->left);
        if (Height(T->left) - Height(T->right) == 2)
        {
            if (val < T->left->val)
                T = SingleRotateWithLeft(T);
            else
                T = DoubleRotateWithLeft(T);

        }
    }
    /*向右孩子插入*/
    else if (val > T->val)
    {
        T->right = insert(val, T->right);
        if (Height(T->right) - Height(T->left) == 2)
        {
            if (val > T->right->val)
                T = SingleRotateWithRight(T);
            else
                T = DoubleRotateWithRight(T);
        }
    }

    /*计算这个节点新的高度*/
    T->height = max(Height(T->left), Height(T->right)) + 1;
    return T;

}

在想如何获取文章摘要的时候，有若干个想法，
第一，在获取到文章后，直接截取前100个字符，但因为是富文本，存在数据库时有很多html标签，如果前一百个截断了html怎么办？或者去掉所有html标签再截取，但就失去了文本格式；
第二，在数据库中文章表中添加一个摘要字段，如果写文章时候不修改，那么就默认为第一段或者前多少个字，当然也可以手动修改，但是非常不想用这样方法。

之后，在网上看到别人想法，使用第一个<p></p>标签中的文字作为摘要。而且正常第一段文字的确是大部分技术类博客的主要内容。

第一想法就是使用正则，来找到第一个<p>,但是<p>里面可能会有张<img> 这不是我们想要的摘要，所以我们需要过滤掉<img>，边学边用正则，起初脑子里一直盯着^这个字符（取反），比如这样^(<img)，或者(^<img)，当然都是不对的，应当使用前瞻，我要匹配<p>且下一个字符不是<img>的，中间任意，最后以</p>结尾.

(?=exp) 匹配exp前面的位置
(?<=exp) 匹配exp后面的位置
(?!exp) 匹配后面跟的不是exp的位置
(?<!exp) 匹配前面不是exp的位置

直接给出代码

private String getDigest(String content){
        //正则筛选第一个文字<p>
        Pattern datePattern = Pattern.compile("<p>((?!<img).)*?<\\/p>");
        Matcher dateMatcher = datePattern.matcher(content);
        if(dateMatcher.find()) {
            return dateMatcher.group();   //返回第一个<p>
        }else
        {
            return "null";
        }
    }