Два вопроса о бинарных поисковых деревьях

Question

У меня есть два вопроса о бинарных деревьях поиска - один о коде, который я пишу, а другой - о теории. Во-первых, код, который я написал ниже, работает нормально, за исключением случаев, когда я пытаюсь показать случай, когда BST фактически пуст; это дает мне ошибку сегментации, когда я хотел бы распечатать сообщение об ошибке. Я чувствую, что в какой-то момент я перепутал мои указатели, и это дает мне ошибку. Вот мой код:

#include <stdio.h>
#include <stdlib.h>

struct Node {
char *word;
struct Node *left;
struct Node *right;
};

/* Function that creates a new node as a leaf; that is, its     */
/* left and right children are NULL.                */
/* Require: node -> word != NULL                    */
struct Node * createNode (char *word) {
struct Node *item = malloc(sizeof(struct Node));
item -> word = word;
item -> left = NULL;
item -> right = NULL;
return item;
}

/* Recursive function that inserts a node into proper position by   */
/* searching through    tree.                   */
struct Node * insertNode (struct Node *root, char *word) {
// If tree is empty, node becomes root
if(root == NULL)
    return createNode(word);
else {

    if(strcmp(word, root -> word) < 0) {
        root -> left = insertNode(root -> left, word);
        return root;
    } else if(strcmp(word, root -> word) > 0) {
        root -> right = insertNode(root -> right, word);
        return root;
    } else if(strcmp(word, root -> word) == 0)
        printf("Word is already present in the tree.");
}
}

/* Function to display Binary Search Tree via inorder traversal.    */
/*  -- prints entire left subtree, then root, then right subtree    */
void display (struct Node *root) {
if(root -> word == NULL)
    printf("Tree is empty.");
if(root -> left != NULL)
    display(root -> left);
printf("%s\n", root -> word);
if(root -> right != NULL)
    display(root -> right);
}

void main () {
struct Node root;
struct Node *rootP = &root;
root = createNode("
}

Второй вопрос касается заполнения двоичного дерева. Я хочу использовать небольшой словарь, который, конечно, будет в алфавитном порядке. Если я добавлю эти слова в двоичное дерево, начинающееся, скажем, с «aardvark», разве дерево не получит невероятно перекос, поскольку все последующие слова будут следовать за первым по алфавиту и, следовательно, всегда будут правильными детьми? Я боюсь, что у меня получится невероятно несбалансированное дерево! Есть ли какой-нибудь метод, который я могу использовать, чтобы перетасовать дерево, когда я его заполняю?

Спасибо, что нашли время, чтобы прочитать это!

Answer 1

В вашей функции display вам сначала нужно проверить root == null перед проверкой root -> word == null.Это должно исправить ошибку сегмента.

Что касается теоретического вопроса: ответ таков: да, дерево в конечном итоге будет невероятно искажено.Вот что такое сбалансированные бинарные деревья .

Answer 2

if(root -> word == NULL)
    printf("Tree is empty.");

Ваша проблема лежит здесь.Что произойдет, если сам root равен null?Дважды проверьте этот указатель, прежде чем снимать с него ссылку.

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

Answer 3

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