数据查找 二叉查找树

查找一般分为有序查找和无序查找，这边在讲有序查找

例二分查找

        二分查找就是在有序数组中，通过mid=(low+high)/2来判定中间值，将中间值与待查找的值进行比较，如果待查找的值大于中间值，那么就将范围缩小，查找右边；如果待查找的值小于中间值，那么查找左边；如果待查找的值等于中间值，查找成功。

int BinarySearch(int R[],int n, int K){
//在数组R中对半查找K，R中关键词递增有序
    int low = 1, high = n, mid;
    while(low <= high){ //在Rlow…Rhigh之间查找K
        mid=(low+high)/2;
        if(K<R[mid]) high=mid-1; //在左半部分查找
        else if(K>R[mid]) low=mid+1; //在右半部分查找
        else return mid; //查找成功
    }
    return -1; //查找失败
}

          在该算法中确定比较值是非常重要的一件事，不同的比较值的确定可以决定不同的时间复杂度。所以还可以拓展出类似斐波那契查找，插值查找之类的算法。

二叉查找树

例1.查找

        其实二叉查找树在这边更像是一种结构，就是结点的左孩子一定小于结点，结点右孩子一定大于结点。查找到数据之后往往还要对数据进行处理，在处理过后还要保持原有结构，是比较困难的地方。

BSTnode* Search2(BSTnode* root, int K){ 
    BSTnode* p = root;
    while (p != NULL) {
        if (K < p->key) p = p->left;
        else if (K > p->key) p = p->right;
        else return p;
    }
    return NULL;
}

例2.插入

就是找到对应的位置，然后建立新的结点。

void Insert(BSTnode* &root, int K){
    if (root == NULL) root = new BSTnode(K); 
    else if (K < root->key) Insert(root->left, K);
    else if (K > root->key) Insert(root->right, K);
}

例3.删除

        这边的删除是在二叉树中一定有值等于k的结点的情况下，否则要修改一些代码。

void remove(BSTnode* &root, int K) {
    if(root==NULL) return;
    if(K<root->key) remove(root->left, K); //在左子树删K
    else if(K>root->key) remove(root->right, K); //在右子树删K
    else if(root->left!=NULL && root->right!=NULL){
        BSTnode *s=root->right;
        while(s->left!=NULL) s=s->left;
        root->key=s->key; //s为t右子树中根序列第一个结点
        remove(root->right, s->key);
    }
    else{ 
        BSTnode* oldroot=root;
        root=(root->left!=NULL)? root->left:root->right;
        delete oldroot;
    }
}

例4.高度平衡树

        高度平衡树是二叉查找树中的一种，它的左右孩子的高度差不会大于1，它通过变形、旋转，让树的结构变得相对“矮胖”，方便后续处理缩小时间。但是这种结构就会对数据操作的过程提出很多额外的要求。

        下面是关于旋转的一些基本操作。这边的代码都比较抽象，适合配合图形理解。

        以LL为例，就是新插入的结点，在A结点的左孩子的左子树上（A结点是从下往上数第一个不平衡的点），插入之后导致不再平衡。于是A结点的左孩子（设为B结点）的右孩子单独拎出来，把右孩子变成A结点的左孩子，然后将这个拎出的B结点作为新的结点，它的右孩子连接到A结点上。

struct AVLnode {
    int key; //关键词
    int height; //以该结点为根的子树高度
    AVLnode *left, *right;
    AVLnode(int K){ key=K; height=0; left=right=NULL; }
};
int Height(AVLnode *t){ return(t==NULL)?-1:t->height; }
int max(int a, int b){ return (a>b)? a:b; }
void UpdateHeight(AVLnode *t){
    t->height = max(Height(t->left),Height(t->right))+1;
}

void LL(AVLnode* &A) {
    AVLnode *B = A->left;
    A->left = B->right;
    B->right = A;
    UpdateHeight(A);
    UpdateHeight(B);
    A = B;
}

void RR(AVLnode* &A) {
    AVLnode *B = A->right;
    A->right = B->left;
    B->left = A;
    UpdateHeight(A);
    UpdateHeight(B);
    A = B;
}

void RL(AVLnode* &A){
    LL(A->right);
    RR(A);
}

void LR(AVLnode* &A) {
    RR(A->left);
    LL(A);
}

AVL树插入算法的实现

void ReBalance(AVLnode* &t) {
    if(t==NULL) return;
    if(Height(t->left) - Height(t->right)==2){ 
        if(Height(t->left->left) >= Height(t->left->right)) 
            LL(t);
        else
            LR(t);
    }else if(Height(t->right) - Height(t->left)==2){
        if(Height(t->right->right) >= Height(t->right->left)) 
            RR(t);
        else
            RL(t);
    }
    UpdateHeight(t);
}

void Insert(AVLnode* &root, int K) {
    if(root==NULL) root=new AVLnode(K);
    else if(K < root->key) //在左子树插入
        Insert(root->left, K);
    else if(K > root->key) //在右子树插入
        Insert(root->right, K);
    ReBalance(root);
}

AVL树删除算法的实现

void remove(AVLnode* &root, int K) {
    if(root==NULL) return;
    if(K<root->key) remove(root->left, K); //在左子树删K
    else if(K>root->key) remove(root->right, K); //在右子树删K
    else if(root->left!=NULL && root->right!=NULL){
        AVLnode *s=root->right;
        while(s->left!=NULL) s=s->left;
        root->key=s->key; //s为t右子树中根序列第一个结点
        remove(root->right, s->key);
    }else{ 
        AVLnode* oldroot=root;
        root=(root->left!=NULL)? root->left:root->right;
        delete oldroot;
    }
    ReBalance(root);
}

所以其实比起怎么插入、删除，更重要的是怎么保持原来的结构