跳转至

HEMY MOTES

树表查找

树表查找¶

概述¶

树表查找是基于树形结构的查找方法，通过树的组织方式实现对数级别的查找效率，同时支持动态插入、删除和范围查询。

常见树表结构¶

树结构	特点	查找复杂度	适用场景
二叉搜索树	左<根<右	O(n)最坏	基础结构
AVL树	严格平衡	O(log n)	查找密集
红黑树	近似平衡	O(log n)	通用场景
B树	多路平衡	O(log n)	磁盘存储
B+树	叶子链表	O(log n)	数据库索引

二叉搜索树查找¶

基本实现¶

C
typedef struct BSTNode {
    int key;
    int value;
    struct BSTNode *left;
    struct BSTNode *right;
} BSTNode;

BSTNode* bstSearch(BSTNode *root, int key) {
    if (!root || root->key == key) {
        return root;
    }
    
    if (key < root->key) {
        return bstSearch(root->left, key);
    }
    return bstSearch(root->right, key);
}

BSTNode* bstSearchIterative(BSTNode *root, int key) {
    while (root && root->key != key) {
        root = (key < root->key) ? root->left : root->right;
    }
    return root;
}

插入操作¶

C
BSTNode* bstInsert(BSTNode *root, int key, int value) {
    if (!root) {
        BSTNode *node = (BSTNode*)malloc(sizeof(BSTNode));
        node->key = key;
        node->value = value;
        node->left = node->right = NULL;
        return node;
    }
    
    if (key < root->key) {
        root->left = bstInsert(root->left, key, value);
    } else if (key > root->key) {
        root->right = bstInsert(root->right, key, value);
    } else {
        root->value = value;
    }
    
    return root;
}

删除操作¶

C
BSTNode* findMin(BSTNode *node) {
    while (node && node->left) {
        node = node->left;
    }
    return node;
}

BSTNode* bstDelete(BSTNode *root, int key) {
    if (!root) return NULL;
    
    if (key < root->key) {
        root->left = bstDelete(root->left, key);
    } else if (key > root->key) {
        root->right = bstDelete(root->right, key);
    } else {
        if (!root->left) {
            BSTNode *temp = root->right;
            free(root);
            return temp;
        }
        if (!root->right) {
            BSTNode *temp = root->left;
            free(root);
            return temp;
        }
        
        BSTNode *minNode = findMin(root->right);
        root->key = minNode->key;
        root->value = minNode->value;
        root->right = bstDelete(root->right, minNode->key);
    }
    
    return root;
}

AVL树查找¶

节点定义¶

C
typedef struct AVLNode {
    int key;
    int value;
    struct AVLNode *left;
    struct AVLNode *right;
    int height;
} AVLNode;

int height(AVLNode *node) {
    return node ? node->height : 0;
}

int getBalance(AVLNode *node) {
    return node ? height(node->left) - height(node->right) : 0;
}

int max(int a, int b) {
    return a > b ? a : b;
}

void updateHeight(AVLNode *node) {
    if (node) {
        node->height = 1 + max(height(node->left), height(node->right));
    }
}

旋转操作¶

C
AVLNode* rightRotate(AVLNode *y) {
    AVLNode *x = y->left;
    AVLNode *T2 = x->right;
    
    x->right = y;
    y->left = T2;
    
    updateHeight(y);
    updateHeight(x);
    
    return x;
}

AVLNode* leftRotate(AVLNode *x) {
    AVLNode *y = x->right;
    AVLNode *T2 = y->left;
    
    y->left = x;
    x->right = T2;
    
    updateHeight(x);
    updateHeight(y);
    
    return y;
}

AVL插入与平衡¶

C
AVLNode* avlInsert(AVLNode *root, int key, int value) {
    if (!root) {
        AVLNode *node = (AVLNode*)malloc(sizeof(AVLNode));
        node->key = key;
        node->value = value;
        node->left = node->right = NULL;
        node->height = 1;
        return node;
    }
    
    if (key < root->key) {
        root->left = avlInsert(root->left, key, value);
    } else if (key > root->key) {
        root->right = avlInsert(root->right, key, value);
    } else {
        root->value = value;
        return root;
    }
    
    updateHeight(root);
    
    int balance = getBalance(root);
    
    if (balance > 1 && key < root->left->key) {
        return rightRotate(root);
    }
    
    if (balance < -1 && key > root->right->key) {
        return leftRotate(root);
    }
    
    if (balance > 1 && key > root->left->key) {
        root->left = leftRotate(root->left);
        return rightRotate(root);
    }
    
    if (balance < -1 && key < root->right->key) {
        root->right = rightRotate(root->right);
        return leftRotate(root);
    }
    
    return root;
}

红黑树查找¶

节点定义¶

C
typedef enum { RED, BLACK } Color;

typedef struct RBNode {
    int key;
    int value;
    struct RBNode *left;
    struct RBNode *right;
    struct RBNode *parent;
    Color color;
} RBNode;

typedef struct {
    RBNode *root;
    RBNode *nil;
} RBTree;

红黑树查找¶

C
RBNode* rbSearch(RBTree *tree, int key) {
    RBNode *curr = tree->root;
    
    while (curr != tree->nil) {
        if (key == curr->key) {
            return curr;
        } else if (key < curr->key) {
            curr = curr->left;
        } else {
            curr = curr->right;
        }
    }
    
    return tree->nil;
}

B树查找¶

节点定义¶

C
#define M 5

typedef struct BTreeNode {
    int keys[M - 1];
    int values[M - 1];
    struct BTreeNode *children[M];
    int keyCount;
    int isLeaf;
} BTreeNode;

B树查找¶

C
int findKeyIndex(BTreeNode *node, int key) {
    int idx = 0;
    while (idx < node->keyCount && key > node->keys[idx]) {
        idx++;
    }
    return idx;
}

BTreeNode* bTreeSearch(BTreeNode *root, int key, int *value) {
    if (!root) return NULL;
    
    int idx = findKeyIndex(root, key);
    
    if (idx < root->keyCount && root->keys[idx] == key) {
        *value = root->values[idx];
        return root;
    }
    
    if (root->isLeaf) {
        return NULL;
    }
    
    return bTreeSearch(root->children[idx], key, value);
}

B+树查找¶

节点定义¶

C
typedef struct BPlusTreeNode {
    int keys[M - 1];
    struct BPlusTreeNode *children[M];
    struct BPlusTreeNode *next;
    int keyCount;
    int isLeaf;
} BPlusTreeNode;

typedef struct {
    BPlusTreeNode *root;
    BPlusTreeNode *firstLeaf;
} BPlusTree;

B+树查找¶

C
BPlusTreeNode* findLeaf(BPlusTreeNode *root, int key) {
    if (!root) return NULL;
    
    BPlusTreeNode *curr = root;
    
    while (!curr->isLeaf) {
        int idx = 0;
        while (idx < curr->keyCount && key >= curr->keys[idx]) {
            idx++;
        }
        curr = curr->children[idx];
    }
    
    return curr;
}

int bPlusTreeSearch(BPlusTree *tree, int key) {
    BPlusTreeNode *leaf = findLeaf(tree->root, key);
    
    if (!leaf) return -1;
    
    for (int i = 0; i < leaf->keyCount; i++) {
        if (leaf->keys[i] == key) {
            return leaf->keys[i];
        }
    }
    
    return -1;
}

范围查询¶

C
void bPlusTreeRangeQuery(BPlusTree *tree, int low, int high, int *result, int *count) {
    BPlusTreeNode *leaf = findLeaf(tree->root, low);
    *count = 0;
    
    while (leaf) {
        for (int i = 0; i < leaf->keyCount; i++) {
            if (leaf->keys[i] >= low && leaf->keys[i] <= high) {
                result[(*count)++] = leaf->keys[i];
            } else if (leaf->keys[i] > high) {
                return;
            }
        }
        leaf = leaf->next;
    }
}

C++ 实现（AVL树）¶

C++
template<typename K, typename V>
class AVLTree {
private:
    struct Node {
        K key;
        V value;
        Node *left, *right;
        int height;
        
        Node(const K& k, const V& v) 
            : key(k), value(v), left(nullptr), right(nullptr), height(1) {}
    };
    
    Node *root;
    
    int height(Node *node) const {
        return node ? node->height : 0;
    }
    
    int balance(Node *node) const {
        return node ? height(node->left) - height(node->right) : 0;
    }
    
    void updateHeight(Node *node) {
        if (node) {
            node->height = 1 + std::max(height(node->left), height(node->right));
        }
    }
    
    Node* rotateRight(Node *y) {
        Node *x = y->left;
        y->left = x->right;
        x->right = y;
        updateHeight(y);
        updateHeight(x);
        return x;
    }
    
    Node* rotateLeft(Node *x) {
        Node *y = x->right;
        x->right = y->left;
        y->left = x;
        updateHeight(x);
        updateHeight(y);
        return y;
    }
    
    Node* balanceNode(Node *node) {
        updateHeight(node);
        int bf = balance(node);
        
        if (bf > 1) {
            if (balance(node->left) < 0) {
                node->left = rotateLeft(node->left);
            }
            return rotateRight(node);
        }
        
        if (bf < -1) {
            if (balance(node->right) > 0) {
                node->right = rotateRight(node->right);
            }
            return rotateLeft(node);
        }
        
        return node;
    }
    
    Node* insert(Node *node, const K& key, const V& value) {
        if (!node) return new Node(key, value);
        
        if (key < node->key) {
            node->left = insert(node->left, key, value);
        } else if (key > node->key) {
            node->right = insert(node->right, key, value);
        } else {
            node->value = value;
            return node;
        }
        
        return balanceNode(node);
    }
    
    Node* findMin(Node *node) const {
        while (node && node->left) node = node->left;
        return node;
    }
    
public:
    AVLTree() : root(nullptr) {}
    
    V* find(const K& key) {
        Node *curr = root;
        while (curr) {
            if (key == curr->key) return &curr->value;
            curr = (key < curr->key) ? curr->left : curr->right;
        }
        return nullptr;
    }
    
    void insert(const K& key, const V& value) {
        root = insert(root, key, value);
    }
};

时间复杂度分析¶

树结构	查找	插入	删除	空间
BST	O(n)	O(n)	O(n)	O(n)
AVL树	O(log n)	O(log n)	O(log n)	O(n)
红黑树	O(log n)	O(log n)	O(log n)	O(n)
B树	O(log n)	O(log n)	O(log n)	O(n)
B+树	O(log n)	O(log n)	O(log n)	O(n)

各树结构比较¶

特性	BST	AVL	红黑树	B树	B+树
平衡性	无	严格	近似	多路	多路
旋转次数	0	O(log n)	O(1)	-	-
磁盘友好	否	否	否	是	是
范围查询	差	差	差	一般	好
空间利用	低	低	低	高	最高

应用场景¶

BST：教学示例、小数据量场景
AVL树：查找密集型应用、内存数据库
红黑树：C++ STL map/set、Java TreeMap
B树：文件系统、数据库索引
B+树：MySQL InnoDB、PostgreSQL索引

选择指南¶

树表选择建议

内存查找: 红黑树（通用）、AVL树（查找密集）
磁盘存储: B+树（数据库）、B树（文件系统）
范围查询: B+树（叶子链表）
小数据集: 简单BST或数组

参考资料¶

《算法导论》第12-18章
《数据结构与算法分析》- Mark Allen Weiss
B+ Tree Visualization