Двоичное дерево поиска

Question

Мой профессор отправил несколько обзорных вопросов к финальному экзамену. И я не могу найти ответы на это. Любая помощь будет принята с благодарностью!

Рассмотрим двоичное дерево из n узлов:
а. Каково минимальное и максимальное количество листовых узлов?
б. Какое минимальное и максимальное значение высоты?
с. Сколько указателей используется деревом (не считая нулевых указателей и предполагая, что мы не сохраняем поле, в котором хранится родительский элемент)?

* d. Каково наихудшее время выполнения для вставки n узлов в (изначально пустое) двоичное дерево поиска?

Answer 1

• Максимальное количество листьев - ceil (n / 2).Минимальное число 1
• Максимальная высота n.Минимальный этаж (log_2 (n))

Answer 2

Рассмотрим:

Если вы пытаетесь максимизировать количество листьев, вам нужно как можно меньше внутренних узлов (и наоборот, если вы пытаетесь минимизировать количество листьев).Как вы можете это сделать?

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

Сколько существует способов добраться до каждого узла дерева?Таким образом, сколько указателей вам нужно?

Answer 3

Я предполагаю, что вы либо пишете на C или C ++.

а. Узел, если структура определена так: struct node {struct node * left, * right; }; Вы можете заметить, что структура может иметь 0, 1 или 2 листа. Таким образом, максимум равен 2, минимум равен 0 листьев.

b. Минимальная высота равна нулю, в которой будет содержаться только корневой узел. Обратите внимание, что корневой узел не считается высотой 1. Он также иногда называется глубиной. Вот алгоритм для высоты:

    int height(struct node *tree) 
    { 
    if (tree == NULL) return 0;
    return 1 + max (height (tree->left), height (tree->right)); 
    }

Подробнее: http://wiki.answers.com/Q/How_do_you_find_out_the_height_of_a_Binary_Search_Tree#ixzz1NIB17SkL

с. Извините, если я так поступлю, но я предполагаю, что если мы наметим это на листе бумаги, мы попытаемся найти количество «ссылок», которые мы будем использовать? В этом случае это будет просто число узлов в дереве -1 для корневого узла. Этот алгоритм, найденный на этой странице http://forums.techarena.in/software-development/1147688.htm, может помочь вам: проверьте, имеет ли root значение null, затем передайте левый и правый узлы в качестве параметров в функцию.

int countnodes(Node* root)
{
    if (root == null || k<=0)
    {
      return 0;
    } else {
        return 1 + count(root.left,k-1) + count(root.right,k-1);
    }
}
// remember to subtract one at the end.
int totalnodes = countnodes(root) - 1;

д. Временная сложность в лучшем случае составляет O (nlogn), где n - количество вставляемых узлов. Худший случай - O (n). Это прямо линейно.

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

Надеюсь, это поможет. Удачи на экзамене! У меня был мой несколько месяцев назад. ;)

Answer 4

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