1. 二分查找针对有序数据，但是需要维护这个有序数组，插入、删除等操作需要对数组进行O(n)的数组复制操作。

2. 二叉查找树，类似二分法，但是左右节点不平衡，例如数据全挂在左节点，就是一个数组遍历的查找了，不稳定。

3. 平衡二叉树，优化了二叉查找树，保证左右平衡（深度值差不超过1），充分发挥二分查找的优势。

4. 红黑树是实现平衡二叉树的算法。对于需要经常查找但是不怎么需要修改的数据，可以采用快速排序和二分查找代替红黑树。

5. 四叉树搜索，用来规划2D平面，刚好坐标划分为四象限，对于每一块象限又可以划分四象限，根据需求划分到最小快。在游戏项目中的用法有：平面的有效碰撞检测搜索范围、地形的有效展示范围、在地图上查找某方块上的人及二维平面的寻路网格构建。

6. 八叉树搜索，规划3D空间，思想类似四叉树。用在游戏中包括渲染裁切、碰撞检测。
   

class InsertSort
{
    public bool Sort(int[] datas)
    {
        if (datas.Length < 1) return false;

        for (int i = 1; i < datas.Length; i++)//默认0为已经有序
        {
            int temp = datas[i];//当前需要插入的元素
            for (int j = 0; j < i; j++)//在有序段中寻找位置
            {
                if (temp < datas[j])//寻找到
                {
                    for (int k = i; k > j; k--)
                    {
                        datas[k] = datas[k - 1];//向后面腾出位置
                    }
                    datas[j] = temp;//坐上宝座
                    break;
                }
            }
        }

        return true;
    }
}

插入排序就是将数组分为了左右两个集合，一个是有序的，一个是无序的，从无序中每次取一个元素，插入到有序的集合中，并保持有序。算法的效率是O(n²)，不适合大量元素的排序。

测试代码：

static void TestInsertSort()
{
    int[] datas = { 5, 6, 9, 1, 100,3, 7, 0, 2, 4 };
    InsertSort insertSort = new InsertSort();
    insertSort.Sort(datas);
    foreach (var data in datas)
    {
        Console.Write(data + " ");//0 1 2 3 4 5 6 7 9 100
    }
}

对于平衡二叉树的删除方法是一样需要照顾平衡二叉书的平衡的，删除结点会导致bf的值改变，对于不平衡的需要平衡一下。

static bool DeleteElement(ref Node node, int data, ref bool lower)
{
    bool L = false, R = false;
    if (node == null) return false;
    if (node.data == data)
    {
        Node p, s;
        p = node.cRight;
        s = p;
        lower = true;
        if (node.cRight == null)
        {
            p = node;
            node = node.cLeft;//右边为空，直接把左边替换上去
            lower = true;

            return true;
        }
        else
        {
            while (s != null)
            {
                p = s;//找到的最左结点
                s = s.cLeft;
            }

            node.data = p.data;//替换数据，引用保留
            DeleteElement(ref node.cRight, data, ref lower);//删除那个最小结点
            R = true;//往右走
        }
    }
    else if (data < node.data)
    {
        DeleteElement(ref node.cLeft, data, ref lower);
        L = true;
    }
    else
    {
        DeleteElement(ref node.cRight, data, ref lower);
        R = true;
    }

    if (lower)
    {
        if (L)
        {
            switch (node.bf)
            {
                case LH:
                    node.bf = EH;
                    lower = true;
                    break;
                case RH://本来右边高了，又删了个左边，所以要右平衡一下
                    RightBalance(ref node);
                    lower = false;
                    break;
                case EH:
                    node.bf = RH;
                    lower = false;
                    break;
            }
        }
        else
        {
            switch (node.bf)
            {
                case EH:
                    node.bf = LH;
                    lower = false;
                    break;
                case RH:
                    node.bf = EH;
                    lower = true;
                    break;
                case LH:
                    LeftBalance(ref node);
                    lower = false;
                    break;
            }
        }
    }

    return true;
}

采用递归的方式，同样的有一个标志位lower来去判断是否需要平衡的检查。删除结点的操作是一样的，发现小的数据往左边，发现大的往右边，当相等的时候就是要删除的数据了。

同样分两种情况，右边为空，则直接将左边结点替换根。如果右边不为为空，则找到右边的最小(左)结点，替换调根的数值但保留根的左右结点，再删除最小结点。

平衡判断也是看情况的，比如说本来右边高的1，然后把左边删了，那就不平衡了，需要右平衡调整一下。

//右平衡,右边高了
static void RightBalance(ref Node node)
{
    Node R, r1;
    R = node.cRight;
    switch (R.bf)
    {
        case RH:
            //右孩子和它一样的平衡因子，直接右旋转
            node.bf = EH;
            R.bf = EH;
            L_Rotate(ref node);
            break;
        case EH:
            node.bf = RH;
            R.bf = LH;
            L_Rotate(ref node);
            break;
        case LH:
            r1 = R.cLeft;
            switch (r1.bf)
            {
                case EH:
                    node.bf = EH;
                    R.bf = EH;
                    break;
                case RH:
                    R.bf = EH;
                    node.bf = LH;
                    break;
                case LH:
                    R.bf = RH;
                    node.bf = EH;
                    break;
            }
            r1.bf = EH;
            R_Rotate(ref node.cRight);
            L_Rotate(ref node);
            break;
    }
}

看情况，旋转之后的bf状态值会有所改变，所以要具体分析到每一种情况之下。

LH的情况比较多样这里就不详细分析了，不过要讲它为啥要先左旋其右结点再右旋自己。看图：

这种情况就是右平衡的时候，其子树的bf方向是不一致的，需要反向调整到一致，不然就不是一个排序树了。

在进行平衡二叉树的构建构成中，每当发现不平衡的结点就要及时的做平衡。根据不同的情况对最小不平衡子树进行左右旋转操作。例如：（左旋转）

右边多的进行左旋转，把1拉下来，看起来想往左边转吧！

//左旋转
static void L_Rotate(ref Node node)//传入的是1
{
    Node temp;
    temp = node.cRight;
    node.cRight = temp.cLeft;//2的左结点设为给1的右节点
    temp.cLeft = node;//2的左边设为1
    node = temp;//原1的位置改为2，这解释，啧啧
}

node.cRight = temp.cLeft;-》如果说原来2是有左结点的话设为x，x<2，又2是1的右结点，所有1<x，又1的原右结点被破坏了，所以可以用1的右节点来承接x结点。如果不这样做的话，你试试，2有左右结点，然后一转，嘿嘿，三个结点了真是奇怪。

//右旋转
static void R_Rotate(ref Node node)
{
    Node temp;
    temp = node.cLeft;
    node.cLeft = temp.cRight;//原前驱，变左结点
    temp.cRight = node;
    node = temp;
}

右旋转和左旋转差不多，不同的是操作左右结点的不同。