二叉搜索树
入门BST 把"大小关系"编码进树形结构里。
// 算法讲解
二叉搜索树
按输入顺序插入，能直观看到 BST 如何把大小关系编码成左右分支。
待机
速度 中
待机 ⌨1struct Node {
2 int value;
3 Node* left;
4 Node* right;
5 Node(int v) : value(v), left(nullptr), right(nullptr) {}
6};
7
8Node* insert(Node* root, int value) {
9 if (root == nullptr) return new Node(value);
10 if (value < root->value) root->left = insert(root->left, value);
11 else if (value > root->value) root->right = insert(root->right, value);
12 return root;
13}
复杂度分析
时间 平均 O(log n), 最坏 O(n)
空间 O(n)
最优 平衡时 O(log n)
最坏 退化时 O(n)
算法讲解
二叉搜索树要求任意节点左子树值都小于它，右子树值都大于它，因此中序遍历会得到有序序列。
查找、插入和删除都沿着比较方向一路向下，所以平均情况下效率较高。
但如果插入顺序很差，BST 会退化成链表，复杂度随之恶化到 O(n)。
这正是平衡树出现的原因：它们试图在动态更新后仍保持树高可控。