c - 将数百万个元素插入二叉搜索树 BST

Question

我已经尝试解决这个问题将近 3 天了，但还没有成功。我正在尝试将大小为(500 万)无符号整数的许多元素插入到二叉树中。

当我限制插入的元素总数为10K时，这段代码可以正常工作，但是当我将元素总数设置为500万时，它就不起作用了。 我在我的电脑上运行这段代码，它有:

• Windows 7 - 32
• 内存 4 GB

任何帮助将不胜感激。提前致谢 :) 这是我的代码:

#include<stdlib.h>
#include<stdio.h>

typedef int ElementType;

typedef struct TreeNode {
  ElementType element;
  struct TreeNode *left, *right;
} TreeNode;

TreeNode *createTree(){
    //Create the root of tree
    TreeNode *tempNode;
    tempNode = malloc(sizeof(TreeNode));
    tempNode->element = 0;
    tempNode->left = NULL;
    tempNode->right = NULL;
    return tempNode;
}

TreeNode *createNode(ElementType X){
    //Create a new leaf node and return the pointer
    TreeNode *tempNode;
    tempNode = malloc(sizeof(TreeNode));
    tempNode->element = X;
    tempNode->left = NULL;
    tempNode->right = NULL;
    return tempNode;
}

TreeNode *insertElement(TreeNode *node, ElementType X){
    //insert element to Tree
    if(node==NULL){
        return createNode(X);
    }
    else{
        if(X < node->element){
                node->left = insertElement(node->left, X);
                return node; // add this.
}
    else if(X > node->element){
                 node->right =  insertElement(node->right, X);
                 return node; // add t

        else if(X == node->element){
            printf("Oops! the element is already present in the tree.");
        }
    }
}

TreeNode *displayTree(TreeNode *node){
    //display the full tree
    if(node==NULL){
        return;
    }
    displayTree(node->left);
    printf("| %d ", node->element); 
    displayTree(node->right);
}

main(){
    //pointer to root of tree #2
    TreeNode *TreePtr;
    TreeNode *TreeRoot;
    TreeNode *TreeChild;

    //Create the root of tree
    TreePtr = createTree();

    TreeRoot = TreePtr;

    TreeRoot->element = 32;
    
  for ( int i=0; i < 5000000; i ++)
    insertElement(TreeRoot, i);
   
    displayTree(TreeRoot);
}

任何帮助将不胜感激。提前致谢:)

Answer 1

假设您的代码中没有其他错误，总是插入 8 会将树退化为列表，我认为，您的堆栈将在远低于 500 万的某个递归级别溢出。

为了通常避免退化树，我建议您使用 AVL 树的插入/删除语义。 这样做的好处是，您的数据结构可以保持原样，但您只需调整插入和删除过程。

编辑:在您的评论中，您现在声明您并不总是插入 8，而是插入 i。这意味着，您将预先排序的元素插入到二叉树中，这也会将其退化为列表，因此会出现与始终插入“8”相同的问题。

看起来像:

1
 \
  2
   \
    3
     \
      4
       \
       ...

按顺序插入元素后。 AVL-Tree 不会遇到这个问题: https://en.wikipedia.org/wiki/AVL_tree