Напишите самую короткую программу, чтобы проверить, сбалансировано ли двоичное дерево

15

Для каждого узла в сбалансированном двоичном дереве максимальная разница высот левого дочернего поддерева и правого дочернего поддерева не превышает 1.

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

Ниже приведен пример:

           2 <-- root: Height 1
          / \
         7   5 <-- Height 2
        / \   \
       2   6   9 <-- Height 3
          / \  /
         5  11 4 <-- Height 4 

Высота бинарного дерева: 4

Ниже приведены двоичные деревья и отчет о том, сбалансированы они или нет:

Тестовый пример 1

Дерево выше не сбалансировано .

Тестовый пример 2

Вышеуказанное дерево сбалансировано .

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

вход

Корень бинарного дерева. Это может быть в форме ссылки на корневой объект или даже списка, который является допустимым представлением двоичного дерева.

Выход

Возвращает истинное значение: если дерево сбалансировано

Возвращает значение Falsey: если дерево не сбалансировано.

Определение двоичного дерева

Дерево - это объект, который содержит значение и два других дерева или указатели на них.

Структура бинарного дерева выглядит примерно так:

typedef struct T
{
   struct T *l;
   struct T *r;
   int v;
}T;

Если для представления двоичного дерева используется представление списка, оно может выглядеть примерно так:

[root_value, left_node, right_node]
Т. Салим
источник
2
Может ли ввод быть пустым деревом?
TSH
1
В вашем первоначальном примере дерева, если вы удалите лист 4, сбалансировано ли оставшееся дерево?
Нил
Нет, не тот пример, я имел в виду исходный, используя искусство ASCII.
Нил
Согласно моей собственной реализации "C, 117 байт": Нет, поскольку высота правого дерева подзадачи, начинающегося с "5", равна 2, а высота левого дерева подзаголовка равна 0.
Т. Салим
Изменения не менее 6 символов, но, пожалуйста, удалите запятую между «сбалансированным» и «двоичным» - «двоичное дерево» - это существительное, поэтому написание «сбалансированного двоичного дерева» эквивалентно «красный, снегоход» - запятая не обязательна.
Геза

Ответы:

8

Желе , 11 байт

ḊµŒḊ€IỊ;߀Ạ

Попробуйте онлайн!

Пустое дерево представлено как [].

Эрик Outgolfer
источник
Спасибо Эрику за то, что он один из первых, кто ответил на этот вопрос. Желе, безусловно, очень популярный язык на этом сайте. Я думаю, что я должен позволить себе реализовать этот язык. Хорошо учиться на надежном языке написания скриптов для гольфа.
Т. Салим
Поздравляю Эрика Outgolfer, вы победитель.
Т. Салим
3

Пролог (SWI) , 49 байт

N+_/B/C:-X+B,Y+C,abs(X-Y)<2,N is max(X,Y)+1.
0+e.

Попробуйте онлайн!

Представляет деревья как Value/Left_Child/Right_Child, причем атомом является пустое дерево e. Определяет +/2, что выводит через успех или неудачу, с несвязанной переменной (или переменной, уже равной высоте дерева) слева и деревом справа - если аргумент высоты недопустим, добавьте 9 байтов для определения -T:-_+T..

N + _/B/C :-            % If the second argument is a tree of the form _Value/B/C,
    X+B,                % X is the height of its left child which is balanced,
    Y+C,                % Y is the height of its right child which is balanced,
    abs(X-Y) < 2,       % the absolute difference between X and Y is strictly less than 2,
    N is max(X,Y)+1.    % and N is the height of the full tree.
0 + e.                  % If, on the other hand, the second argument is e, the first is 0.
Несвязанная строка
источник
(Если значение каждого узла может быть опущено во входных данных, _/может быть взято за -2 байта.)
Несвязанная строка
3

Wolfram Language (Mathematica) , 50 байтов

f@_[x_,y_]:=f@x&&f@y&&-2<Depth@x-Depth@y<2;f@_=1>0

Используйте Nullдля нуля, value[left, right]для узлов. Например, следующее дерево записывается как 2[7[2[Null, Null], 6[5[Null, Null], 11[Null, Null]]], 5[Null, 9[4[Null, Null], Null]]].

    2
   / \
  7   5
 / \   \
2   6   9
   / \  /
  5  11 4

Попробуйте онлайн!

alephalpha
источник
Это действительно красиво!
Грег Мартин
3

Python 3.8 (предварительная версия) , 133 125 байт

b=lambda t:((max(l[0],r[0])+1,abs(l[0]-r[0])<2)if(l:=b(t[1]))[1]and(r:=b(t[2]))[1]else(0,0))if t else(0,1)
h=lambda t:b(t)[1]

Попробуйте онлайн!

Принимает дерево в формате «список»: узел [value, left, right]с leftиright узлами является узлами.

Вызвать функцию h .

Возвращает 0или Falseдля несбалансированного дерева. Возвращает 1илиTrue для сбалансированного дерева.

Ungolfed:

# Returns tuple (current height, subtrees are balanced (or not))
def balanced(tree):
  if tree: # [] evaluates to False
    left = balanced(tree[1])
    right = balanced(tree[2])
    # If  the subtrees are not both balanced, nothing to do, just pass it up
    if left[1] and right[1]:
      height = max(left[0], right[0]) + 1
      subtrees_balanced = abs(left[0] - right[0]) < 2
    else:
      height = 0 # Value doesn't matter, will be ignored
      subtrees_balanced = False
  else:
    height = 0
    subtrees_balanced = True
  return (height, subtrees_balanced)

def h(tree):
  return balanced(tree)[1]

-10: обратная логика, от которой нужно избавиться not с

Если разрешено принимать аргументы в середине вызова, это можно сократить до (115 байт)

(b:=lambda t:((max(l[0],r[0])+1,abs(l[0]-r[0])<2)if(l:=b(t[1]))[1]and(r:=b(t[2]))[1]else(0,0))if t else(0,1))(_)[1]

с _тем, чтобы быть деревом, чтобы проверить.

ar4093
источник
2

JavaScript, 162 байта

f=x=>{for(f=0,s=[[x,1]];s[0];){if(!((d=(t=s.pop())[0]).a&&d.b||f))f=t[1];if(f&&t[1]-f>1)return 0;if(d.a)s.push([d.a,t[1]+1]);if(d.b)s.push([d.b,t[1]+1])}return 1}

Попробуйте онлайн!

Формат ввода - это объект

root={a:{node},b:{node},c:value}

объяснение

for(f=0,s=[[x,1]];s[0];){if(!((d=(t=s.pop())[0]).a&&d.b||f))f=t[1]

Выполняя поиск в ширину, найдите глубину первого узла, в котором отсутствует одна или несколько ветвей.

if(f&&t[1]-f>1)return 0;if(d.a)s.push([d.a,t[1]+1]);if(d.b)s.push([d.b,t[1]+1])}

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

return 1}

Если такой узел не найден, вернуть 1

fənɛtɪk
источник
1
Вероятно, есть какой-то способ улучшить поиск в ширину, но я не мог об этом думать.
fəˈnɛtɪk
1
Я думаю, что это не работает в некоторых допустимых случаях, таких как самый первый пример, который должен стать сбалансированным, когда вы удаляете лист 4.
Нил
1

Юлия, 56 байт

f(t)=t!=()&&(-(f.(t.c)...)^2<2 ? maximum(f,t.c)+1 : NaN)

Со следующей структурой, представляющей двоичное дерево:

struct Tree
    c::NTuple{2,Union{Tree,Tuple{}}}
    v::Int
end

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

Значение Falsey - NaNлюбое целое число является правдивым.

user3263164
источник
1
Предполагая кодировку UTF-8, это на самом деле 57 байтов из-за , согласно встроенному счетчику байтов TIO . В любом случае, добро пожаловать в CG & CC!
Несвязанная строка
1
Да, ты прав. Я исправил это так, что теперь это фактически 56 байтов
user3263164
0

C 117 байт

h(T*r){r=r?1+h(h(r->l)>h(r->r)?r->l:r->r):0;}b(T*r){return r->l&&!b(r->l)||r->r&&!b(r->r)?0:abs(h(r->l)-h(r->r))<=1;}

Структура реализации выглядит следующим образом:

 typedef struct T
    {
        struct T * l;

        struct T * r;

        int v;

    } T;

Попробуйте это на JDoodle

Т. Салим
источник
Похоже, что это 117 байт, хотя <2вместо этого вы можете выполнить последнюю проверку
Джо Кинг,
Кроме того, я не уверен, насколько это верно, поскольку оно опирается на структуру данных, определенную вне представления
Джо Кинг,
0

Python 2 , 99 96 94 байта

lambda A:A==[]or(abs(D(A[1])-D(A[2]))<2)*f(A[1])*f(A[2])
D=lambda A:A>[]and-~max(map(D,A[1:]))

Попробуйте онлайн!

3 байта от Джо Кинга .

Принимает ввод как: пустой узел есть [], а другие узлы есть [<value>, <leftNode>, <rightNode>]. Выходы 0/1для False / True.

Час Браун
источник