KD树需像二叉搜索树（BST）一样平衡吗？为何BST插入失衡数据会栈溢出？

嘿，这个问题我太熟悉了！咱们一步步拆解来看：

首先说BST栈溢出的核心原因 #

你写的BST插入是递归实现的对吧？当你插入完全有序的数据（比如1,2,3,4,...,10000）时，BST会直接退化成一条单链表——每个新节点都只能挂在最后一个节点的右子树上（或者左子树，如果是降序的话）。这时候递归调用的深度就等于节点的总数，当节点数足够大时，程序的调用栈就装不下这么多层的递归了，直接触发栈溢出错误。

举个直观的例子：插入第10000个节点时，递归函数会被调用10000次，每一次调用都会在栈上保存函数的上下文信息，而栈的空间是有限的（一般默认只有几MB），很快就会被耗尽。

你的BST插入代码（补全未写完的部分）大概是这样：

```cpp
void insert(node *&_node, int _val) { 
    //bst insert function, will change raw pointers to smart pointers later 
    if (_node == NULL) { 
        _node = new node; 
        _node->val = _val;
        _node->left = nullptr;
        _node->right = nullptr;
    } else if (_node->val > _val) 
        insert(_node->left, _val); 
    else if (_node->val < _val) 
        insert(_node->right, _val); 
}

再看KD树为什么不会有这个问题 #

至于KD树嘛，它的插入逻辑天生就带着“防退化”的buff——KD树是按维度轮流切分的。比如二维KD树，第一次插入按x轴比较大小，第二次换y轴，第三次又回到x轴，循环往复。哪怕你输入的数据在某一个维度上是完全有序的，换维度切分后，树会自动保持一定的平衡性，递归深度始终是O(log₂n)的级别，比如10000个节点也就14层左右，这么浅的调用栈完全不会触发溢出。

简单说，KD树的多维度交替切分，从根源上避免了树退化成单链表的可能，自然不会出现递归深度爆炸的情况。

怎么解决BST的栈溢出问题？ #

给你几个实用的方案：

• 改成迭代插入：不用递归，用循环实现插入逻辑，完全避开调用栈的限制，代码示例如下：

  void insertIterative(node *&root, int _val) {
      node **curr = &root;
      while (*curr != nullptr) {
          if ((*curr)->val > _val) {
              curr = &((*curr)->left);
          } else if ((*curr)->val < _val) {
              curr = &((*curr)->right);
          } else {
              return; // 不允许重复值的话直接返回
          }
      }
      *curr = new node{_val, nullptr, nullptr}; // 假设node结构体有val、left、right
  }
  

• 换成自平衡二叉树：比如AVL树或者红黑树，它们会在插入/删除后自动调整树的结构，保证树始终是平衡的，递归深度维持在O(logn)，自然不会栈溢出。
• 调整栈大小：这个是下下策，因为不同系统的栈大小限制不同，而且治标不治本，没法从根本上解决BST退化的问题。

内容的提问来源于stack exchange，提问作者User9123