二叉排序树

都是查找，二叉查找树与hash相比有什么特点？

• 二叉查找树在比较平衡的情况下，插入、删除、查找操作时间复杂度才是 O(logn)
• 散列hash表扩容耗时多, 发生冲突时，性能不稳定，而二叉排序树插入、删除、查找稳定在O(longn)

• 二叉查找树可以有序输出
• hash不支持查找最大值、最小值，不支持范围性查找，扩容、缩容时间复杂度高，堆内存高

版本一：自己写的

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

typedef struct Node {
    int value;
    int size; //该节点左右子树节点的数量和 
    struct Node *left, *right; //左右指针 
} Node;

Node __NIL; //虚拟节点 
#define NIL (&__NIL)

__attribute__((constructor))
void init_NIL() {
    NIL->value = 0;
    NIL->size = -1;
    NIL->left = NIL->right = NIL; //自环 
}

Node *getNewNode(int key) {
    Node *p = (Node *)malloc(sizeof(Node));
    p->value = key;
    p->size = 0;
    p->right = p->left = NIL;
    return p;
}

void update_size(Node *root) { //跟新root挂的节点个数 
    root->size = root->left->size + root->right->size + 2;
    return ;
}

Node *insert(Node *root, int target) {
    if (root == NIL) return getNewNode(target);
    if (root->value == target) return root;
    
    if (root->value > target) { //说明target在左子树 
        root->left = insert(root->left, target);
    } else { //否则在右子树 
        root->right = insert(root->right, target);
    }
    
    /*
    root->size = 0;
    if (root->left) root->size += root->left->size;
    if (root->right) root->size += root->right->size;
    */
    
    update_size(root); //跟新其所挂节点个数 
    
    return root;
}

void clear(Node *root) {
    if (root == NIL) return ;
    clear(root->left);
    clear(root->right);
    free(root);
    return ;
}

int search(Node *root, int target) {
    if (root == NIL) return 0;
    if (root->value == target) return 1;
    if (root->value > target) {
        return search(root->left, target);
    }
    return search(root->right, target);
}

Node *perdecessor(Node *root) {
    Node *p = root->left;//得到左子树 
    while (p != NIL && p->right != NIL) { //找到前驱节点 
        p = p->right;
    }
    /*
    Node *p = root->right; //得到右子树 
    while (p != NIL && p->left != NIL) p = p->left;
    */
    return p;
}

Node *erase(Node *root, int target) {
    if (root == NIL) return root;
    if (root->value > target) {
        root->left = erase(root->left, target);
    } else if (root->value < target) {
        root->right = erase(root->right, target);
    } else {
//        if (root->left == NIL && root->right == NIL) { //删除出度为0的节点 
//            free(root);
//            return NIL;
//        } else 
        if (root->left == NIL || root->right == NIL) { 
            Node *temp = root->left != NIL ? root->left : root->right;
            free(root);
            return temp;
        } else {
            Node *temp = perdecessor(root); //找到前驱节点 或者也可以是后继节点 
            root->value = temp->value;
            root->left = erase(root->left, temp->value); //删除前驱节点 
        }
    }
    update_size(root);
    return root;
}

void in_order(Node *root) {
    if (root == NIL) return ;
    in_order(root->right);
    //printf("value = %d, size = %d\n", root->value, root->size);
    printf("%d ", root->value);
    in_order(root->left);
    return ;
}

int find_k(Node *root, int k) {
    //按照我写的出度为0的节点个数root->size = 0 
    //船长写的root->szie = 1; 因为NIL为一个虚拟节点 
    if (root->right->size >= k) {
        return find_k(root->right, k);
    }
    if (root->right->size + 1 == k) {
        return find_k(root->right, k);
    }
    if (root->right->size + 2 == k) {
        return root->value;
    }
    return find_k(root->left, k - root->right->size - 2);
}

int main() {
    srand(time(0));
    #define n 20
    Node *root = NIL;
    for (int i = 1; i <= n * 2; i++) {
        int value = rand() % 100;
        printf("%d ", value);
        root = insert(root, value);
    }
    printf("\n");
    in_order(root);
    printf("\n");
    for (int i = 1; i <= n * 2; i++) {
        int target = rand() % 100;
    //    scanf("%d", &target);
        if (search(root, target)) {
            printf("%d              存在\n", target);
            root = erase(root, target);
        } else printf("%d          不存在\n", target);
    }
    
    in_order(root), printf("\n");
    printf("%d\n", root->value);
    
    for (int i = 1; i <= n; i++) {
        int max_i = find_k(root, i);
        printf("%d %d\n", i, max_i);

    }
    clear(root);
    #undef n
    return 0;
}

版本二：标准版

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

typedef struct Node {
    int value, size;
    struct Node *left, *right;
} Node;


Node __NIL;
#define NIL (&__NIL)

__attribute__((constructor))
void init_NIL() {
    NIL->value = 0;
    NIL->size = 0;
    NIL->left = NIL->right = NIL;
}

Node *getNewNode(int key) {
    Node *p = (Node *)malloc(sizeof(Node));
    p->value = key;
    p->size = 1; //船长写的root->szie = 1; 因为NIL为一个虚拟节点 
    p->left = p->right = NIL;
    return p;
}

void update_size(Node *root) {
    root->size = root->left->size + root->right->size + 1;
    return ;
}

Node *insert(Node *root, int target) { //插入操作 
    if(root == NIL) return getNewNode(target);
    if(root->value == target) return root;
    if(root->value > target) {
        root->left = insert(root->left, target);
    } else {
        root->right = insert(root->right, target);
    }
    update_size(root);
    return root;
}

void clear(Node *root) {
    if(root == NIL) return ;
    clear(root->left);
    clear(root->right);
    free(root);
    return ;
}

int search(Node *root, int target) { //查找操作 O(logn) 
    if(root == NIL) return 0;
    if(root->value == target) return 1;
    if(root->value > target) {
        return search(root->left, target);
    }
    return search(root->right, target);
}

Node *predecessor(Node *root) {
    Node *p = root->left;
    while(p != NIL && p->right != NIL) {
        p = p->right;
    }
    return p;
}

Node *erase(Node *root, int target) { //删除操作 
    if(root == NIL) return root;
    if(root->value > target) {
        root->left = erase(root->left, target);
    } else if(root->value < target){
        root->right = erase(root->right, target);
    } else {
        if(root->right == NIL || root->left == NIL) {
            Node *tmp = root->left != NIL ? root->left : root->right;
            free(root);
            return tmp;
        } else {
            Node *tmp = predecessor(root);
            root->value = tmp->value;
            root->left = erase(root->left, tmp->value);
        }
    }
    update_size(root);
    return root;
}

void in_order(Node *root) {
    if(root == NIL) return ;
    in_order(root->left);
    printf("%d ", root->value);
    in_order(root->right);
    return ;
}

int find_k(Node *root, int k) {
    if(root->right->size >= k) { //所求值在在右子树 
        return find_k(root->right, k);
    }
    if(root->right->size + 1 == k) { //该节点右子树节点个数加自己 == k说明该节点为第k大值 
        return root->value;
    }
    return find_k(root->left, k - root->right->size - 1); //所求值在在左子树 
}

int main() {
    
    Node *root = NIL;
    int n;
    scanf("%d", &n);
    for(int i = 0; i < n; i++) {
        int num = rand() % 100;
        printf("%d ", num);
        root = insert(root, num);
    }
    printf("\n");
    in_order(root);
    printf("\n");
    
    
    for (int i = 1; i <= n * 2; i++) {
        int target = rand() % 100;
        //    scanf("%d", &target);
        if (search(root, target)) {
            printf("%d              存在\n", target);
            root = erase(root, target);
        } else printf("%d          不存在\n", target);
    }
    
    printf("\n");
    in_order(root);
       printf("\n");
    
    for (int i = 1; i <= n; i++) { //求第K大的值 
        printf("%d\n", find_k(root, i)); 
    }
    

    return 0;
}