30006：不透明整数二叉搜索树

题目

实现拥有结点、支持插入、查找和中序遍历的不透明整数二叉搜索树。

解析

插入沿唯一的搜索路径向下走；遇到相等键时不创建新结点。只有走到空孩子时才分配结点，因此分配失败不会改变树。中序遍历先检查树中结点数是否超过输出容量，再写入输出数组，从而不会出现写入一部分后才发现容量不足的情况。

答案

#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <stdlib.h>

typedef struct IntBst IntBst;

typedef enum {
    INT_BST_OK,
    INT_BST_INVALID,
    INT_BST_OUT_OF_MEMORY
} IntBstResult;

typedef struct BstNode BstNode;

struct BstNode {
    int64_t key;
    BstNode *left;
    BstNode *right;
};

struct IntBst {
    BstNode *root;
    size_t size;
};

IntBst *int_bst_create(void) {
    IntBst *tree = malloc(sizeof *tree);
    if (tree == NULL) {
        return NULL;
    }
    tree->root = NULL;
    tree->size = 0;
    return tree;
}

static void destroy_nodes(BstNode *node) {
    if (node == NULL) {
        return;
    }
    destroy_nodes(node->left);
    destroy_nodes(node->right);
    free(node);
}

void int_bst_destroy(IntBst *tree) {
    if (tree == NULL) {
        return;
    }
    destroy_nodes(tree->root);
    free(tree);
}

IntBstResult int_bst_insert(
    IntBst *tree,
    int64_t key,
    bool *out_inserted
) {
    if (tree == NULL || out_inserted == NULL) {
        return INT_BST_INVALID;
    }

    BstNode **link = &tree->root;
    while (*link != NULL) {
        if (key == (*link)->key) {
            *out_inserted = false;
            return INT_BST_OK;
        }
        link = key < (*link)->key
            ? &(*link)->left
            : &(*link)->right;
    }

    if (tree->size == SIZE_MAX) {
        return INT_BST_INVALID;
    }
    BstNode *node = malloc(sizeof *node);
    if (node == NULL) {
        return INT_BST_OUT_OF_MEMORY;
    }
    node->key = key;
    node->left = NULL;
    node->right = NULL;
    *link = node;
    ++tree->size;
    *out_inserted = true;
    return INT_BST_OK;
}

bool int_bst_contains(const IntBst *tree, int64_t key) {
    if (tree == NULL) {
        return false;
    }
    const BstNode *node = tree->root;
    while (node != NULL) {
        if (key == node->key) {
            return true;
        }
        node = key < node->key ? node->left : node->right;
    }
    return false;
}

static void write_inorder(
    const BstNode *node,
    int64_t *out_keys,
    size_t *cursor
) {
    if (node == NULL) {
        return;
    }
    write_inorder(node->left, out_keys, cursor);
    out_keys[(*cursor)++] = node->key;
    write_inorder(node->right, out_keys, cursor);
}

bool int_bst_inorder(
    const IntBst *tree,
    int64_t *out_keys,
    size_t capacity,
    size_t *out_count
) {
    if (tree == NULL || out_count == NULL ||
        capacity < tree->size ||
        (tree->size > 0 && out_keys == NULL)) {
        return false;
    }
    size_t cursor = 0;
    write_inorder(tree->root, out_keys, &cursor);
    *out_count = cursor;
    return true;
}

查找和插入均为 $O(h)$，中序遍历为 $O(n)$；未平衡树的高度 $h$ 最坏可达 $n$。