algorithm - BST の純粋な末尾再帰挿入を実装する方法は?

Question

BST のすべての実装insertは非末尾再帰です。

BSTの末尾再帰挿入を作成することは可能ですか?

可能であれば、どのように？

Answer 1

それは可能です: たとえば、insert関数を継続渡しスタイルで書くことによって。

例えばラケットで

#lang racket

(struct bst-node (left right value) #:transparent)

(define (insert tree new-value)
  (insert-cps tree new-value (lambda (x) x)))

(define (insert-cps tree new-value cont)
  (cond
    [(empty? tree) (cont (bst-node empty empty new-value))]
    [else (match-let ([(bst-node l r v) tree])
            (cond
              [(= v new-value) (cont (bst-node l r v))]
              [(< new-value v) (insert-cps l new-value (lambda (t) (cont (bst-node t r v))))]
              [else (insert-cps r new-value (lambda (t) (cont (bst-node l t v))))]))]))

(insert (insert (insert empty 10) 15) 2)

Answer 2

このコードが機能するかどうかを確認してください。

public class TailInsertion {

    class Node {
        int dat;
        Node left;
        Node right;

        Node(int dat) {
            this.dat = dat;
        }
    }

    public void insert(Node root, Node parent, int dat) {

        if (root == null) {
            if (parent == null) {
                return;
            } else {
                if (parent.dat <= dat) {
                    parent.right = new Node(dat);
                    return;
                } else {
                    parent.left = new Node(dat);
                    return;
                }
            }
        }

        Node node = null;
        if (root.dat <= dat) {
            node = root.right;
        } else {
            node = root.left;
        }

        insert(node, root, dat);
    }
}

Answer 3

このテールは再帰的ではありませんか？

void insert(Tree *t, int val) {
    if (t == NULL || val == t->Value) {
        return;
    }
    Tree *next = NULL;
    if (val < t->Value)
        next = t->Left;
    else
        next = t->Right;
    insert(next, val);
}