algorithm - 如何为 BST 实现纯尾递归插入？

Question

BST 的所有实现insert都是非尾递归的。

是否可以为 BST编写尾递归插入？

如果可能，怎么做？

Answer 1

有可能：例如，通过以continuation-passing styleinsert编写函数。

例如在球拍

#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

只需添加到解决方案中，您还可以执行以下操作（我在 F# 中实现）：

let Insert element bst=
    //find where the element need to be inserted
    let mutable next = bst.Root
    let rec insert n r =
        match n,r with
        |_ when n < r.Data && r.LeftNode.IsNone -> r
        |_ when n > r.Data && r.RightNode.IsNone -> r
        |_ when n = r.Data -> r
        |_ -> if n < r.Data then 
                  next <- r.LeftNode.Value
              else 
                  next <- r.RightNode.Value
              insert n next
    let n = insert element bst.Root

    //if duplicate is found return false
    if n.Data = element then
        false
    else //otherwise create new node
        let node: BSTNode<'a> ={
            Data = element
            LeftNode = None
            RightNode = None
        }
        //insert into proper postion (left or right accordingly)
        if n.Data > node.Data then
            n.LeftNode <- Some(node)
            true
        else 
            n.RightNode <- Some(node)
            true

递归方法是尾递归，没有堆栈堆积。基本递归方法找到你要插入的地方。然后，如果要插入的内容尚未在树内，则通过简单的比较将其插入。

Answer 3

看看这段代码是否适合你。

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 4

这不是尾递归吗？

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);
}