K-й наименьший элемент в BST (схема) - PullRequest
Новая
       25

K-й наименьший элемент в BST (схема)

0 голосов
/ 06 ноября 2019

Пожалуйста, не обращайте внимания на мой ломаный английский, так как я не являюсь носителем языка. Я ищу лучший способ найти kth наименьший элемент в BST, я думал о способах, таких как добавление дерева в список и обход этого списка, но это занимает слишком много времени O (n) Я такжерассмотрите возможность удаления элементов из дерева, затем найдите самые маленькие, но это также займет больше времени. Каков наилучший алгоритм для решения этой проблемы? Поскольку схема является функциональным языком программирования, решение должно быть рекурсивным. Я пытался найти ответ, но в большинстве ответов на C или Java использовался какой-то итерационный формат. Спасибо за вашу помощь. Моя функция должна выглядеть следующим образом (Определить (kth-smallle T k) ...)

Ответы [ 2 ]

0 голосов
/ 06 ноября 2019

Если размер левого поддерева больше, чем k, мы смотрим в левое поддерево, если оно меньше, мы смотрим на правое поддерево с новым k: k - size-of-left-поддерево - 1 , в противном случае (в равном случае) мы возвращаем значение в текущем узле. Это выполняется за O (LG N) времени. 

#lang racket

(struct no-info ())
(define NONE (no-info))

; [BST X] is one of:
; - (node NONE NONE NONE 0)
; - (node BST  BST  X    Number)

(struct node [left right val size])
(define leaf (node NONE NONE NONE 0))

; examples
(define lt (node (node (node leaf leaf 10 1) (node leaf leaf 24 1) 15 3) leaf 29 4))
(define rt (node (node leaf leaf 77 1) (node leaf (node leaf leaf 99 1) 95 2) 89 4))
(define t (node lt rt 63 9))

;           63
;          /  \
;        29    89
;       /     /  \
;      15    77  95
;    /   \         \ 
;  10     24       99

; node val: 10 15 24 29 63 77 89 95 99
; rank:     1  2  3  4  5  6  7  8  9

; kth-smallest : BST -> X
; the value of the `k`th smallest node in `t`
(define (kth-smallest t k)
  (define (kth-smallest-h t k)
    (cond [(equal? (node-size t) 1) (node-val t)]
          [else (let ([s (node-size (node-left t))])
                  (cond [(> s k) (kth-smallest-h (node-left t) k)]
                        [(< s k) (kth-smallest-h (node-right t) (sub1 (- k s)))]
                        [else (node-val t)]))]))
  (if (or (<= k 0) (> k (node-size t)))
      (error "k out of range")
      (kth-smallest-h t (sub1 k))))


(map (λ (x) (kth-smallest t x)) '(1 2 3 4 5 6 7 8 9))
; => '(10 15 24 29 63 77 89 95 99)
0 голосов
/ 06 ноября 2019

Если BST упорядочен и сбалансирован, то есть не самый левый лист является самым низким значением. Тогда n-е наименьшее значение будет n-м значением, которое вы перебираете в обходе дерева заказов.

Таким образом, нахождение наименьшего значения kth в сбалансированном дереве находится между O (log n) и O (2n). O (N) это тогда.

Моя реализация создаст помощника, который принимает продолжение, а также k и дерево. Продолжением по умолчанию может быть (lambda (v) #f), и поэтому, если вам нужно 30-е наименьшее в дереве из 10 узлов, оно вызовет это, и вы получите #f обратно. В тот момент, когда вы найдете самый глубокий узел, и он k равен нулю, вместо вызова продолжения, которое он оценивает по значению текущего узла.

Если бы вы удалили наименьшее значение k раз, у вас было бы O (k * log n) ~ O (n log n)> O (n)

Удачи

...