C ++ Создание сбалансированного дерева двоичного поиска с использованием структуры массива - PullRequest
Новая
       20

C ++ Создание сбалансированного дерева двоичного поиска с использованием структуры массива

0 голосов
/ 06 мая 2018

поручено хранить двоичное дерево внутри вектора. Внутри каждого узла хранятся int ID, int Age и строковое имя.

Узлы хранятся и организуются в векторе по идентификатору.

При сохранении двоичного дерева в векторе я использую алгоритм 2i и 2i + 1, чтобы продиктовать левый и правый потомок узла соответственно.

Мне удалось создать метод вставки, который, по моему мнению, удовлетворяет этим условиям, однако по какой-то причине при попытке напечатать значения моего вектора я получаю отрицательные значения. Для этого конкретного примера я вставляю следующие значения

100 21 Стан

50 30 Фил

Я пытаюсь разместить другой узел

30 31 Алиса

Согласно источникам, это приводит к тому, что дерево становится неуравновешенным.

Итак, я пытаюсь создать сбалансированное дерево двоичного поиска, используя узлы, хранящиеся в векторе. Ранее я создал несбалансированное дерево, используя эту предыдущую структуру вставки. Тем не менее, Я не совсем понимаю, что такое сбалансированное двоичное дерево поиска

Итак, мои вопросы таковы:

  1. Что такое сбалансированное дерево двоичного поиска?

  2. Что бы вы предложили мне изменить в моей функции вставки, чтобы стимулировать создание сбалансированного дерева?

Заранее спасибо!

Вот мой код: 

#include "BinaryTree.h"
#include <string>
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
int index = 0;

struct Node
{
    int ID = -1;
    int age = -1;
    string name = "";

    Node()
    {


    }

    Node(int id, int Age, string nm)
    {
        this->ID = id;
        this->age = Age;
        this->name = nm;
    }
};

vector<Node> binaryTree;


BST::BST()
{

}





void BST::insert()
{
    unsigned int ID;
    int AGE;
    string NAME;
    int root = 0;

    bool success = false;
    cout << "Please enter the ID number, age and name:" << endl;


    cin >> ID >> AGE >> NAME;

    Node *tree = new Node(ID, AGE, NAME);



    if (!binaryTree.empty())
    {
        do
        {
            if (tree->ID > binaryTree.at(root).ID && binaryTree.at(root).ID != 0)
            {
                root = 2 * root + 2;
                if (root >= binaryTree.size()) binaryTree.resize((2 * root + 2 + 1) * 5);

            }

            if (tree->ID < binaryTree.at(root).ID && binaryTree.at(root).ID != 0)
            {
                root = 2 * root + 1;
                if (root >= binaryTree.size()) binaryTree.resize((2 * root + 2 + 1) * 5);

            }

            if (binaryTree.at(root).ID == -1)
            {
                binaryTree[root] = *tree;
                success = true;
            }
        } while (!success);
    }

    if (binaryTree.empty())
    {
        binaryTree.push_back(*tree);
    }

    delete tree;

}

1 Ответ

0 голосов
/ 06 мая 2018

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

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

Для вставки вы можете сделать следующее:

1) Добавить новый элемент в первый неиспользуемый индекс в массиве.

2) Используйте для этого алгоритм upheap. Это работает так, что вы сравниваете элемент с его родителем и меняете местами в зависимости от свойства дерева (например, в max heap, если child> parent). Вы делаете это рекурсивно до корня дерева (индекс 1). Это занимает O(log n) время.

Это должно дать вам идеально сбалансированное двоичное дерево с реализацией массива.

...