方案:从BST中删除最大值 [英] Scheme: Remove the maximum from a BST

问题描述

大家下午好

我有一个非常奇怪的问题，很抱歉，如果我在论坛的错误部分中发帖了.

I have very odd question and I'm sorry If I have posted in a wrong part of the forum.

我正在尝试从用方案编写的BST中理解 remove-max 函数(下面提供)，但是我很难理解其中的想法.我知道Scheme语法，但是此函数有很多工作要做，因此我有点困惑.

I'm trying to understand remove-max function (provided bellow) from a BST written in scheme, but I have a hard time grasping the ideas in it. I know the Scheme syntax, however there is a lot of going on in this function and thus I am a bit confused.

(define removemax-BST 
 (lambda (T) 
  (cond ((null? (caddr t)) (cons (cadr t) (car t))
   (else (let ((r (removemax-BST (caddr t))))
    (cons (list (car t) (cadr t) (car r)) (cdr r))))
     )))

是否有一个善良的灵魂可以为我一步一步地解释此功能，就像您正在向婴儿解释一样?我确实想了解，但是我的大脑无法完全掌握它.

Is there a kind soul that can do a step by step explanation of this function for me as if you were explaining to a baby? I genuinely want to understand but my brain cannot fully grasp it.

谢谢.

推荐答案

您的函数没有任何意义.它具有印刷错误，不处理空树以及算法错误，因此会产生无效的树.它对抽象的使用不善，这使得代码非常难以阅读.

Your function does not make any sense. It has typographical errors and doesn't handle empty trees as well as algorithmic errors such that it will produce invalid trees. It has poor use of abstractions which makes the code very difficult to read.

通过查看，我推断出该模型可能是:

From looking at it I have deduced that the model probably is:

(define (node-empty? tree)
  (null? tree))

(define (node-left tree)
  (car tree))

(define (node-value tree)
  (cadr tree))

(define (node-right tree)
  (caddr tree))

(define (node left value right)
  (list left value right))

似乎它也跟随正确的节点，所以我猜想它从有序二叉树中删除了最大节点.这是正确的版本:

It also seems like it follows the right node so I guess it removes tha maximum node from an ordered binary tree. Here is a correct version:

(define (remove-max-bst tree)
  (cond
    ((node-empty? tree) tree)
    ((node-empty? (node-right tree))
     (node-left tree))
    (else
     (node (node-left tree)
           (node-value tree)
           (remove-max-bst (node-right tree))))))

我们可以测试这是否正确:

We can test if this is correct:

;; remove from an empty node (removed nothing)
(remove-max-bst '())                      ; ==> ()
;; remove the only value
(remove-max-bst '(() 5 ()))               ; ==> ()
;; remove the highest value
(remove-max-bst '(() 5 (() 7 ())))        ; ==> (() 5 ())
;; same, with a left child
(remove-max-bst '(() 5 ((() 6 ()) 7 ()))) ; ==> (() 5 (() 6 ()))

这篇关于方案:从BST中删除最大值的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！