Finding an element in B+ tree using Scheme

Question

I need to traverse the B+ tree. If i hit a list i need to deal with it and recursively keep going till i get an element. Then i compare it to the number given. If the number is more than the greatest number in that list i can ignore that branch (list). Same for when it's less. I just need to traverse the tree and find the element. It should work no matter the tree given

This is what i did

(define ones (list '() 2 '() 4 '() 6 '() 7 '() 8 '()))
(define sixties (list '() 52 '() 54 '() 66 '() 67 '() 68 '()))
(define tens (list ones 10 '() 30 '() 50 sixties 70 '() 90 '()))
(define ninehundreds (list '() 930 '() 940 '() 960 '() 970 '() 988 '()))
(define tree (list tens 100 '() 300 '() 500 '() 700 '() 900 ninehundreds ))

(define (walk tree num)
   (if list? (car tree)
       (walk-list (car tree)))

  (if (not list? (car tree)))
       walk-list( cdr tree)
)

(define (walk-list lst)
  (if (list? (car lst)) (walk-list (car lst)))
  (if (not (list? (car lst))) (car lst))
)
(walk tree 0)

I have an issue with the two ifs in both defined functions. Also i kept getting back #t at one point

edit: I believe I fixed my understanding with the syntax errors. But now I get this message on the if statement in walk-list

mcar: contract violation
  expected: mpair?
  given: ()

(define (walk tree num)
   (if (list? (car tree))
       (walk-list (car tree))
       (car tree))
)

(define (walk-list lst)
  (if  (list? (car lst))
    (walk-list (car lst))
    (car lst))
)

Answer 1

Try it at the REPL:

> (list? '())
#t

whereas

> (pair? '())
#f

You can't call car on '(). This will cause the error you're shown.

Answer 2

I need to traverse the b+ tree. If i hit a list i need to deal with it and recursively keep going till i get an element. Then i compare it to the number given. If the number is more than the greatest number in that list i can ignore that branch(list). Same for its less. I just need to traverse the tree and find the element. It should work no matter the tree given

(define ones (list '() 2 '() 4 '() 6 '() 7 '() 8 '()))
(define sixties (list '() 52 '() 54 '() 66 '() 67 '() 68 '()))
(define tens (list ones 10 '() 30 '() 50 sixties 70 '() 90 '()))
(define ninehundreds (list '() 930 '() 940 '() 960 '() 970 '() 988 '()))
(define tree (list tens 100 '() 300 '() 500 '() 700 '() 900 ninehundreds ))

How to get started: write a data definition with some simple examples:

; a Tree is one of:
;  (1) '(), or
;  (2) a List ('() KNum <'() KNum> ... '()), or
;  (3) a List (NonEmptyTree INum <Tree INum> ... Tree)
; (where "<a b> ..." means two list elements a b occur zero or more times)
; KNums and INums are Numbers; the KNums are sorted, and each INum is > all KNums preceding it.
;
; examples of Trees:
;   (1): '()
;   (2): (list '() 1 '())
;   (2): (list '() 1 '() 2 '())
;   (3): (list (list '() 1 '()) 10 '())
;   (3): (list (list (list '() 1 '()) 10 '()) 10 '())
;   (3): (list (list '() 1 '()) 10 (list '() 10 '()) 20 (list '() 21 '()))

Choose a good name for a function, write a first check-expect and function stub, with signature and purpose:

(check-expect is available in Racket's Student Languages; data definition/stub/signature/purpose are part of a Systematic Program Design process, for which there are Design Recipes)

(check-expect (tree-search '() 1)  #f )

(define (tree-search tree num) ;; Tree KNum -> List or #f
  ;; produce first list within |tree| with first element |num|, or #f if not found
  #f)

Write check-expects for Tree case (1) and use them to write the code.

(check-expect (tree-search-1 '() 1)  #f )
(check-error  (tree-search-1 (list '() 1 '()) 1) )  ;; (tree must be ())

(define (tree-search-1 tree num) ;; Tree(1) KNum -> List or #f
  ;; produce first list within |tree| with first element |num|, or #f if not found
  (cond
    [(null? tree) #f ]  ;; tree is ()
    [else (error) ]))

Now do the same for Tree case (2): note that each check- shows how to write the cond clause.

(check-expect (tree-search-2 '() 1)                     #f )
(check-error  (tree-search-2 (list 'x) 1) )
(check-expect (tree-search-2 (list '() 1 '())       1)  (list 1 '()) )
(check-expect (tree-search-2 (list '() 2 '())       1)  #f )
(check-expect (tree-search-2 (list '() 1 '())       2)  #f )
(check-expect (tree-search-2 (list '() 1 '() 2 '()) 2)  (list 2 '()) )

(define (tree-search-2 tree num) ;; Tree(1|2) KNum -> List or #f
  ;; produce first list within |tree| with first element |num|, or #f if not found
  ;; |tree| is () or (() KNum <() KNum> ... ())
  (cond
    [(null? tree) #f ]                        ;; tree is ()
    [(not (null? (car tree))) (error) ]       ;; tree is (x ...)
    [(= (cadr tree) num) (cdr tree) ]         ;; tree is (() num ...)
    [(> (cadr tree) num) #f ]                 ;; tree is (() >num ...)
    [(null? (cdddr tree)) #f ]                ;; end of list: not found
    [else (tree-search-2 (cddr tree) num) ])) ;; search (<() KNum> ... )

Now one can continue to write more check-expects and write the full tree-search for all 3 Tree cases.

It can call tree-search-2, and it may also be convenient for it to call a "tree-search-rest" function to handle the "<Tree INum> ... Tree" part of Tree(3).

.
.
.

Finally, a few tests using the example tree from the question:

(check-expect (tree-search tree 8)    (list 8 '()) )
(check-expect (tree-search tree 67)   (list 67 '() 68 '()) )
(check-expect (tree-search tree 988)  (list 988 '()) )
(check-expect (tree-search tree 5)    #f )
(check-expect (tree-search tree 10)   #f )