CODEWITHSUNDEEP
rotationschemebinary-tree
John Friedrich
John Friedrich

Reputation: 343

"Rotation of Binary Search Trees" in Scheme

Can anyone help me with my base cases for the rotation of a binary search tree left and right? I tried writing the right rotation function as:

 (define (right-rotate T)

      (make-tree (car (left T)) 
                 (left (left T)) 
                 (make-tree(value T) (right (left T)) (right T))))

but this gives me a call to an empty list somewhere. Does this code look correct for a right rotation? Also, what could my base cases be here?

Upvotes: 1

Views: 494

Answers (1)

GoZoner
GoZoner

Reputation: 70165

You really need to provide more information, such as what is your representation of a 'tree' and how is a tree missing its 'left' or 'right' child defined and handled.

(define (make-tree value left right)
  `(TREE ,value ,left ,right))
(define value cadr)
(define right caddr)
(define left  cadddr)

;; How is an 'empty' tree denoted?
(define empty 'EMPTY)
(define (is-empty? tree)
  (eq? tree empty))

(define (make-leaf value)
  (make-tree value empty empty))

;; Now you have the basis for a solution; here is a start.

(define (right-rotate tree)
  (if (is-empty? tree)
      empty
      (let ((l (left tree)))
        (if (is-empty? l)
            <something>
            (make-tree (value l)
                       (left  l)
                       (make-tree (value tree) (right l) (right tree)))))))

Upvotes: 1

Related Questions