Переполнение стека в двоичном вставке дерева

Question

PROCEDURE CreateNode (info: CHAR): BST; 
VAR 
    bst : BST; 
BEGIN 
    NEW(bst); 
    bst^.elem := info; 
    bst^.left := NIL; 
    bst^.right := NIL; 
    RETURN bst; 
END CreateNode; 



PROCEDURE Insert (info: CHAR; VAR t: BST); 
BEGIN 
    IF t = NIL THEN 
     t := CreateNode(info); 
    ELSIF Compare(info, t^.elem) = greater THEN 
     Insert(info, t^.right); 
    ELSIF Compare(info, t^.elem) = less THEN 
     Insert(info, t^.left); 
END; 
END Insert; 

Это вызывает переполнение стека, когда выполнено FOR с 1 до очень высокого значения (20k).

Он доходит до относительно низкого числа (~ 900) до переполнения.

Answer 1

Вы искали в переполнении стека? : p Просто шучу.

Проблема, вероятно, является рекурсивным вызовом. Вызов функции использует стек для хранения значений регистра, которые удаляются только там, если вызываемая функция заканчивается, и управление возвращается вызывающей функции. Для рекурсивных вызовов все эти вложенные вызовы остаются в стеке, пока рекурсия не будет нарушена. В конце концов, стек недостаточно велик, и вы получите эту ошибку.

Вы должны исправить это, исключив рекурсию с помощью цикла. Таким образом, у вас просто есть итерации, которые переходят на следующий узел без всех накладных вызовов функций.

Это может быть трудно сделать. Иногда рекурсия кажется очевидным, и вам нужно сделать некоторую работу, чтобы исправить ее в цикле.

В любом случае, он должен иметь ту же логику, что и ваша, то есть пересекать дерево и искать нужное место. Если новое значение меньше или больше любого листа, оно вставляется как новый узел, как лист в родительский, и возвращается в 't'. Если уже есть узел с тем же значением, этот узел возвращается.

Чтобы устранить слишком много дублирования кода, в приведенном ниже фрагменте представлена ​​новая функция TryCreateNode. Он проверяет, является ли p (левым или правым листом родительского узла) nil, и если да, то присваивает ему новый узел. Он возвращает либо p (существующий лист), либо новый узел в качестве выходного параметра и возвращает true, если был создан новый узел. Это возвращаемое значение используется в основной функции для разрыва цикла.

Я не уверен, какой диалект Паскаля вы используете, поэтому я немного догадался. Возможно, вам нужно рассматривать это как псевдокод и сначала исправить синтаксис. ;)

FUNCTION TryCreateNode(Info: CHAR; VAR p: BST; VAR t: BST): Boolean; 
BEGIN 
    TryCreateNode := False; 
    IF p = nil THEN 
    BEGIN 
    p := CreateNode(info); 
    TryCreateNode := True; 
    END; 
    t := p; 
END; 

PROCEDURE Insert (info: CHAR; VAR t: BST); 
BEGIN 
    WHILE t <> nil DO 
    BEGIN 
    IF Compare(info, t^.elem) = greater THEN 
     IF TryCreateNode(info, t^.right, t) THEN 
     BREAK; 
    IF Compare(info, t^.elem) = less THEN 
     IF TryCreateNode(info, t^.left, t) THEN 
     BREAK; 
    END; 

END Insert; 

Answer 2

Учитывая, что это кажется Паскалем, причиной вашей проблемы является, скорее всего, рекурсия. Вполне вероятно, что версия Pascal, которую вы используете, не может оптимизировать эту функцию (или не будет) для рекурсии хвоста.