C++ 二叉搜索树详解
一、二叉搜索树的概念
二叉搜索树（Binary Search Tree，简称 BST），又称二叉排序树。它要么是一棵空树，要么满足以下性质：
- 若左子树不为空，则左子树上所有结点的值都小于等于根结点的值。
- 若右子树不为空，则右子树上所有结点的值都大于等于根结点的值。
- 左右子树也分别为二叉搜索树。
关于相等值的处理，具体取决于使用场景。例如 std::map/std::set 不支持插入相等键，而 std::multimap/std::multiset 支持。后续我们会看到这些容器底层正是基于二叉搜索树的变形。
二、性能分析
二叉搜索树的效率高度依赖于树的形态：
- 最优情况：树接近完全二叉树，高度为
log2 N，操作复杂度为O(logN)。 - 最差情况：树退化为单支树（类似链表），高度为
N，操作复杂度降为O(N)。
虽然二分查找也能达到 O(logN) 的查找效率，但它有两个明显缺陷：
- 需要存储在支持随机访问的结构中，且数据必须有序。
- 插入和删除效率低，因为涉及大量数据移动。
相比之下，平衡二叉搜索树（如 AVL 树、红黑树）能更好地解决动态数据的存储与搜索问题。
三、核心操作实现
1. 插入操作
插入逻辑遵循 BST 的性质：
- 如果树为空，直接创建新结点作为根节点。
- 如果树不空，从根开始比较。若插入值大于当前结点，向右走；小于则向左走。
- 找到空位置后插入新结点。
- 若支持重复值，需保持逻辑一致性（统一往左或往右），否则会导致结构混乱。
#pragma once
#include <iostream>
using namespace std;
template<class K>
struct BSTNode {
K _key;
BSTNode<K>* _left;
BSTNode<K>* _right;
BSTNode(const K& key) :_key(key), _left(nullptr), _right(nullptr) {}
};
template<class K>
class BSTree {
typedef BSTNode<K> Node;
public:
{
(_root == ) {
_root = (key);
;
}
Node* parent = ;
Node* cur = _root;
(cur) {
(cur->_key < key) {
parent = cur;
cur = cur->_right;
} (cur->_key > key) {
parent = cur;
cur = cur->_left;
} {
;
}
}
cur = (key);
(parent->_key < key) {
parent->_right = cur;
} {
parent->_left = cur;
}
;
}
{
_InOrder(_root);
cout << endl;
}
:
_InOrder(Node* root) {
(root == ) ;
_InOrder(root->_left);
cout << root->_key << ;
_InOrder(root->_right);
}
Node* _root = ;
};
