Эй, у меня тест через несколько дней, поэтому я провожу несколько практических тестов, и возник этот вопрос, на который я не знаю, как правильно ответить:
т 1 и является постоянным натуральным числом, дерево t-avl - это BST st для каждой вершины x (t> = | height (x.right) - height (x.left) |) мы будем отмечать n_k как минимальное число вершин для дерева t-AVL высоты k. написать рекурсивную формулу для n_k и кратко объяснить, почему это правильно, используйте формулу, чтобы доказать, что для каждого t-avl дерева высотой k k = O (log (n))
, поэтому я добрался до факт, что формула n_k = n_ (k-1) + n_ (kt-1) + 1, но я не знаю, чтобы объяснить, почему это правильно, и я не знаю, как доказать, что k = O (log (n) )