Печать двоичных деревьев

После написания этого ответа мне было предложено разработать более элегантное решение проблемы печати двоичных деревьев , И какой лучший инструмент для поиска элегантности, чем Clojure?

Общая конструкция

В результате решения я включил создание, объединение и печать того, что я собираюсь назвать разреженными строками . Редкая строка - это просто карта из пар строк /столбцов в подстроки. Эти подстроки не должны содержать символы новой строки или перекрываться друг с другом.

Так, например, эта многострочная строка

 baz
     foo
bar
              qux

может быть представлена ​​этой разреженной строкой:

{[3 -2] "foo"
 [4 -7] "bar"
 [2 -6] "baz"
 [5 7] "qux"}

Несколько замечаний:

  1. Пустое пространство просто заполняется регулярными пробелами и символами новой строки
  2. Первая координата - это строка, вторая координата - столбец
  3. Первая строка и столбец необязательно должны быть равны нулю

Проблема печати двоичного дерева затем сводится к созданию разреженных строк из его левого и правого поддеревьев (а также одного для его значения, которое будет отображаться вверху), а затем смещения и слияния этих разреженных строк вместе.

Единственным дополнительным требованием при использовании разреженных строк для представления деревьев является то, что корень (или центр корня, если корень шире 1 символа) должен быть в [0 0]. Рассмотрим дерево ниже:

    4
   / \
  2   5
 / \
1   3

Внутри памяти это будет

{:value 4
 :left {:value 2
        :left {:value 1}
        :right {:value 3}}
 :right {:value 5}}

В текстовом виде дерево будет представлено как

{[0 0] "4"
 [2 -2] "2"
 [4 -4] "1"
 [3 -3] "/"
 [4 0] "1"
 [3 -1] "\\"
 [1 -1] "/"
 [2 2] "5"
 [1 1] "\\"}

Я буду называть это строкой дерева . Таким образом, когда я объединить несколько строк дерева, чтобы создать большую строку дерева, можно смело использовать [0 0] в качестве точки привязки, с которой сдвиг поддеревьев.

Код

(defn end-col
  "Returns one plus the maximum column occupied by the sparse string entry x."
  [x]
  (let [[[_ col] s] x]
    (+ col (count s))))

(defn min-corner
  "Returns a vector of the minimum non-empty row and column in sparse-string."
  [sparse-string]
  (mapv #(apply min (map % (keys sparse-string)))
        [first second]))

(defn max-corner
  "Returns a vector of one plus the maximum non-empty row and column in
  sparse-string."
  [sparse-string]
  (mapv #(apply max (map % sparse-string))
        [(comp inc first key) end-col]))

(defn fill
  "Returns a string of newlines and spaces to fill the gap between entries x and
  y in a sparse string whose minimum corner is corner."
  [corner x y]
  (let [[_ min-col] corner
        [[prev-row _] _] x
        [[next-row next-col] _] y]
    (apply str (concat (repeat (- next-row prev-row) \newline)
                       (repeat (- next-col
                                  (if (== prev-row next-row)
                                    (end-col x)
                                    min-col))
                               \space)))))

(defn sparse-str
  "Converts sparse-string to a string."
  [sparse-string]
  (let [corner (min-corner sparse-string)]
    (->> sparse-string
         (sort-by key)
         (cons [corner ""])
         (partition 2 1)
         (map (fn [[x y]] (str (fill corner x y) (val y))))
         (apply str))))

(defn shift
  "Creates and returns a sparse string by adding offset to the position of each
  entry in sparse-string."
  [offset sparse-string]
  (into {} (map (fn [[pos s]]
                  [(mapv + pos offset) s])
                sparse-string)))

(defn vert-gap
  "Returns the minimum vertical gap that can be used in combining the left and
  right tree strings."
  [left right]
  (if (and left right)
    (max 1 (quot (- (second (max-corner left))
                    (second (min-corner right)))
                 2))
    1))

(def directions {:left - :right +})

(defn diagonal
  "Returns a diagonal sparse string with the top end located at corner."
  [direction corner length character]
  (let [[first-row first-col] corner]
    (into {} (map (fn [n]
                    [[(+ first-row n)
                      ((directions direction) first-col n)]
                     (str character)])
                  (range length)))))

(defn leg
  "Returns a sparse string from shifting tree-string according to direction,
  vert-gap, and value-height, merged with a diagonal strut."
  [direction tree-string vert-gap value-height]
  (merge (shift [(+ value-height vert-gap)
                 ((directions direction) (inc vert-gap))]
                tree-string)
         (diagonal direction
                   [value-height ((directions direction) 1)]
                   vert-gap
                   ({:left \/ :right \\} direction))))

(defn assemble
  "Assembles a complete tree string from the tree strings of a value, left
  subtree, and right subtree."
  [value left right]
  (if (or left right)
    (let [[value-height _] (max-corner value)
          vert-gap (vert-gap left right)]
      (merge value
             (when left
               (leg :left left vert-gap value-height))
             (when right
               (leg :right right vert-gap value-height))))
    value))

(defn tree-string
  "Creates and returns a tree string from node."
  [node]
  (let [{:keys [value left right]} node
        s (str value)]
    (apply assemble
           {[0 (- (quot (count s) 2))] s}
           (map #(when % (tree-string %))
                [left right]))))

Замечания по внедрению

При печати разреженной строки сначала нужно найти минимально занятую строку и столбец в разреженной строке. Это естественно приводит к функциям end-col, min-corner и max-corner для вычисления ограничивающих полей для разреженных строк.

Теперь, как печатать разреженную строку? Эта проблема в основном сводится к печати пробелов до fill пробелов между разреженными строковыми строками. Как только это будет выполнено, фактическая реализация sparse-str довольно проста.

Кроме того, поскольку я собираюсь комбинировать разреженные строки в дополнение к простому созданию и печати, мне понадобится функция shift контрольная точка существующая разреженная строка.

Теперь нам нужен способ преобразования из этого логического представления дерева в текстовое, что является задачей функции tree-string.

Как вы можете видеть, лучшая часть работы выполняется в этой функции assemble. Первое, что нам нужно сделать, это решить, как долго мы будем создавать стойки, которые соединяют левое и правое поддеревья. Чтобы упростить вещи, мы всегда будем делать их одинаковой длины, а это означает, что длина распорок, рассчитанная с помощью vert-gap, будет равна окончательному расстоянию между нижней частью value и вершины строк дерева left и right.

И, конечно, нам понадобится функция diagonal, чтобы создать сами struts.

Теперь, когда у нас есть все остальные части, это просто вопрос сборки вместе. Функция assemble - это просто помощник, который объединяет leg и diagonal вместе в нечто, которое затем можно объединить с корнем.

Пример

Если вы хотите проверить этот код самостоятельно, вот функция для генерации случайного двоичного дерева:

shift

Итак, это ...

(defn rand-tree
  [weight depth]
  (into {:value (int (Math/pow 2 (rand (dec Integer/SIZE))))}
        (map #(when (and (pos? depth) (< (rand) weight))
                [% (rand-tree weight (dec depth))])
             [:left :right])))

... напечатает что-то вроде этого:

(println (sparse-str (tree-string (rand-tree 3/4 3))))
58 голосов | спросил Sam Estep 18 FebruaryEurope/MoscowbThu, 18 Feb 2016 06:31:08 +0300000000amThu, 18 Feb 2016 06:31:08 +030016 2016, 06:31:08

1 ответ


15

Прежде всего, на мой взгляд, оба алгоритма хороши и интересны, и код действительно хорошо написан, разбит на легко понятные функции! Молодцы!

Единственное дополнение, которое я могу сделать, это угловые случаи (и их возможные исправления) для некоторых вспомогательных функций. Однако учтите, что из основной точки входа я не нашел способа запуска этих угловых случаев, поэтому с точки зрения пользователя программа работает хорошо даже без изменений ниже.

Угловой корпус № 1

(min-corner {})
(sparse-str {})

Оба генерируют исключение из-за min в min-corner, который вызывается с нулевыми аргументами.

Я предлагаю следующее изменение, чтобы обработать этот случай:

(defn min-corner
   "Returns a vector of the minimum non-empty row and column in sparse-string."
   [sparse-string]
   (mapv #(apply min (let [args (map % (keys sparse-string))] (if (empty? args) [0 0] args)))
;  (mapv #(apply min (map % (keys sparse-string)))
         [first second]))

I.e., вызовите min со значением по умолчанию (в этом случае [0 0]), если аргументы пусты.

Угловой корпус # 2

(max-corner {})

Аналогичная проблема, например, для min-corner, аналогичное решение:

(defn max-corner 
   "Returns a vector of one plus the maximum non-empty row and column in
   sparse-string."
   [sparse-string]
   (mapv #(apply max (let [args (map % sparse-string)] (if (empty? args) [0 0] args)))
;  (mapv #(apply max (map % sparse-string))
         [(comp inc first key) end-col]))

Угловой корпус № 3

(sparse-str {[0 0] "aa" [0 1] "b"})

Это вернет aab. Однако b здесь не используется, потому что он должен находиться в позиции [0 1], и вместо этого он находится в позиции [0 2]. Честно говоря, я действительно не знаю, что было бы лучшим решением здесь. Я могу себе представить следующее:

  1. Оставьте это как есть: отображается весь вывод, некоторые из них могут быть не в том месте.
  2. Перезаписать конец первой строки со вторым (т. е. "ab").
  3. Запишите начало второй строки с первой (в данном случае: "aa").
  4. Выбросьте исключение.

Снова, начиная с основной точки входа, невозможно вызвать эту ситуацию, поскольку пользователь не предоставляет никаких позиций. Однако, если вспомогательные функции должны были повторно использоваться в библиотеке, это вопрос, который следует решить.

Угловой корпус # 4

(vert-gap {[0 0] "a"} {[4 10] "a"})

Если правый элемент имеет большую вторую координату, чем левую, результат всегда 1. Я не уверен, что это по дизайну, но если нет, то я бы посоветовал убедиться, что вертикальный разрыв правильно вычисляется и в таких случаях, беря абсолютное значение разницы, а не сама разница:

(defn vert-gap
   "Returns the minimum vertical gap that can be used in combining the left and
   right tree strings."
   [left right]
   (if (and left right)
     (max 1 (quot (Math/abs (- (second (max-corner left))
                     (second (min-corner right)))
                  ) 2))
   1))

Угловой корпус # 5

(diagonal :left [0 0] -2 \a)

В текущей реализации это вернет пустой результат: {}. Теперь, когда семантика подразумевает имя параметра length, это должно быть правильно (возможно, исключение можно было бы выбросить, но это только детали). Однако, было бы неплохо, если signum length мог управлять направлением, в котором растет первая координата? Что-то вроде этого:

(defn diagonal
   "Returns a diagonal sparse string with the top end located at corner."
   [direction corner length character]
   (let [[first-row first-col] corner
         _length (Math/abs length)
         op (if (< length 0) - +)]
     (into {} (map (fn [n]
                     [[(op first-row n)
                       ((directions direction) first-col n)]
                      (str character)])
                   (range _length)))))

Таким образом, результатом приведенного выше примера будет: {[0 0] "a", [-1 -1] "a"}. Конечно, стоит переименовать параметр length, например. to horizontal-displacement или что-то подобное.

P.S:.

Я установил github repo для вышеуказанного упомянутые изменения и их соответствующие тестовые примеры (по другим тестам):

ответил Attilio 6 PM00000090000005731 2017, 21:42:57

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

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132