Permalink
Switch branches/tags
Nothing to show
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
75 lines (60 sloc) 2.21 KB

这个题目把一个有序的列表转为了一个平衡树,这是个很有意思的问题 我自己尝试着实现了该方法,不难,下面给出我自己的方法

(load "lib/tree.scm")
(define (mid-index x)
  (if (even? x)
    (/ x 2)
    (/ (+ 1 x) 2)))

(define (nth-element elements index)
  (define (iter elts current)
    (if (= 1 current)
      (car elts)
      (iter (cdr elts) (- current 1))))
  (iter elements index))

(define (lower-elements elements index)
  (define (iter elts current result)
    (if (= 1 current)
      result
      (iter (cdr elts) (- current 1) (append result (list (car elts))))))
  (iter elements index '()))

(define (higher-elements elements index)
  (define (iter elts current)
    (if (= 1 current)
      (cdr elts)
      (iter (cdr elts) (- current 1))))
  (iter elements index))


(define (list->tree elements length)
  (if (< length 1)
    '()
    (let ((mid (mid-index length)))
      (let ((mid-element (nth-element elements mid))
            (left (lower-elements elements mid))
            (right (higher-elements elements mid)))
        (make-tree mid-element
                   (list->tree left (- mid 1))
                   (list->tree right (- length mid)))))))

(define (make-tree-set elements)
  (list->tree elements (length elements)))

(make-tree-set '(1 2 3 4 5 6 7))
;Value: (4 (2 (1 () ()) (3 () ())) (6 (5 () ()) (7 () ())))
;格式化后更直观些
; (4 (2 (1 () ()) 
;       (3 () ())) 
;    (6 (5 () ()) 
;       (7 () ())))

我自己写完后与书上的方式对比了下, 思路是一致的

a)

partial-tree的工作原理其实就是,先找出中间的元素来做根节点,然后依次递归调用求出左子树与右子树 最后调用make-tree把这三者组合起来

b)

这个问题问的是list->tree的时间复杂度。partial-tree这里其实只是对每个节点访问了一次,make-tree本身是O(1)的 所以list->treeO(n)的,这是直观上的推断。

写成数学表达式是:

T(n) = 2T(n/2) + Θ(1)

通过应用主定理,可以解的

T(n) = Θ(n)

参考: