Как вы проверяете бинарное дерево поиска?

Question

Как вы проверяете бинарное дерево поиска?

Использование dplyr:

test %>%
    group_by(idnum) %>%
    summarize(start=min(start),end=max(end)) %>%
    do(data.frame(idnum=.$idnum, month=seq(.$start,.$end,by="1 month")))

Обратите внимание, что здесь я не создаю последовательность между start и end для каждой строки, вместо этого это последовательность между min(start) и max(end) для каждого idnum. Если вы хотите первый:

test %>%
    rowwise() %>%
    do(data.frame(idnum=.$idnum, month=seq(.$start,.$end,by="1 month")))

59

binary-search-tree algorithm data-structures

задан Dukeling 17 June 2014 в 11:43

4 ответа

Другие вопросы по тегам:

binary-search-tree algorithm data-structures

Похожие вопросы:

score 15 · Answer 1

"Проверка" дерева двоичного поиска означает, что Вы проверяете, что она действительно имеет все меньшие объекты на левых и больших объектах справа. По существу это - проверка, чтобы видеть, является ли двоичное дерево двоичным файлом поиск дерево.

score 114 · Answer 2

На самом деле это ошибка, которую все делают в интервью.

С левой стороны нужно проверить (minLimitof node, node.value)

С правой стороны нужно проверить с (node.value, MaxLimit узла)

IsValidBST(root,-infinity,infinity);

bool IsValidBST(BinaryNode node, int MIN, int MAX) 
{
     if(node == null)
         return true;
     if(node.element > MIN 
         && node.element < MAX
         && IsValidBST(node.left,MIN,node.element)
         && IsValidBST(node.right,node.element,MAX))
         return true;
     else 
         return false;
}

Другое решение (если пробел не является ограничением): Выполните обход дерева по порядку и сохраните значения узлов в массиве. Если массив находится в отсортированном порядке, в противном случае он является действительным BST.

score 5 · Answer 3

Вот мое решение в Clojure:

(defstruct BST :val :left :right)

(defn in-order [bst]
  (when-let [{:keys [val, left, right]} bst]
    (lazy-seq
      (concat (in-order left) (list val) (in-order right)))))

(defn is-strictly-sorted? [col]
  (every?
    (fn [[a b]] (< a  b))
    (partition 2 1 col)))

(defn is-valid-BST [bst]
  (is-strictly-sorted? (in-order bst)))

score 1 · Answer 4

"Лучше сначала определить инвариант. Здесь инвариант таков -- любые два последовательных элемента BST в упорядоченном обходе должны быть в строго возрастающем порядке их появления (не могут быть равны, всегда возрастают в упорядоченном обходе). Поэтому решением может быть простой обход в порядке возрастания с запоминанием последнего посещенного узла и сравнением текущего узла с последним посещенным узлом на '<' (или '>')."

.