Бинарное Дерево Поиска На C++


Ценю ваши мысли и отзывы...

БСТ.ч

//
//  BST.h
//  BST
//
//  
//
//

#ifndef BST_h
#define BST_h

//  includes
#include <memory>
#include <string>
#include <iostream>


namespace bst {

template<class Key, class Data>
class BST
{
public:

    //
    //  Node
    //

    class Node {
    public:
        Node(const Key& k, const Data& d, Node* p)
        : key(k)
        , data(d)
        , left(nullptr)
        , right(nullptr)
        , parent(p) {}

        Node(const Key& k, const Data& d, std::unique_ptr<Node>& l, std::unique_ptr<Node>& r, Node* p)
        : key(k)
        , data(d)
        , left(std::move(l))
        , right(std::move(r))
        , parent(p) {}

        const Key& GetKey() const { return key; }
        Key& GetKey() { return key; }
        const Data& GetData() const { return data; }
        Data& GetData() { return data; }
        std::unique_ptr<Node>& GetLeft() { return left; }
        const std::unique_ptr<Node>& GetLeft() const { return left; }
        std::unique_ptr<Node>& GetRight() { return right; }
        const std::unique_ptr<Node>& GetRight() const { return right; }
        Node* GetParent() { return parent; }
        const Node* GetParent() const { return parent; }

        void SetLeft(std::unique_ptr<Node>& l) { left = std::move(l); }
        void SetRight(std::unique_ptr<Node>& r) { right = std::move(r); }
        void SetParent(Node* p) { parent = p; }
        void SetData(const Data& d) { data = d; }

    private:
        std::unique_ptr<Node> left;
        std::unique_ptr<Node> right;
        Node* parent;
        Key key;
        Data data;
    };

    //
    //  BST
    //

    BST()
    : root(nullptr) {}

    void Insert(const Key& k, const Data& d);
    void Remove(const Key& k);
    void Print(std::ostream& os);

private:
    void InsertHelper(std::unique_ptr<Node>& node, const Key& k, const Data& d);
    void RemoveHelper(std::unique_ptr<Node>& node, const Key& k);
    void PrintHelper(std::ostream& os, std::unique_ptr<Node>& node);


private:
    std::unique_ptr<Node> root;

};  //  BST

}  //  bst


template<class Key, class Data>
void bst::BST<Key,Data>::Remove(const Key& k)
{
    if(root) {
        RemoveHelper(root, k);
    } else {
        //  empty tree
    }
}

template<class Key, class Data>
void bst::BST<Key,Data>::RemoveHelper(std::unique_ptr<Node>& node, const Key& k)
{
    if(node->GetKey() == k) {
        //  found

        if(node->GetRight() && node->GetLeft()) {
            //  2 child
            //  swap with left child
            //  call function with new left child

            //  make a copy of left
            std::unique_ptr<Node> leftLeft = std::move(node->GetLeft()->GetLeft());
            std::unique_ptr<Node> leftRight = std::move(node->GetLeft()->GetRight());

            //  make a copy of node
            std::unique_ptr<Node> left = std::move(node->GetLeft());
            std::unique_ptr<Node> nodeRight = std::move(node->GetRight());
            Node* nodeParent = node->GetParent();

            bool isRightChild = false;
            if(nodeParent && nodeParent->GetRight() == node) {
                isRightChild = true;
            }

            //  setup node
            node->SetParent(left.get());
            node->SetRight(leftRight);
            node->SetLeft(leftLeft);

            //  setup left
            left->SetParent(nodeParent);
            left->SetLeft(node);
            left->SetRight(nodeRight);

            //  connect left to parent
            //  and recursively call
            if(isRightChild) {
                if(nodeParent) {
                    nodeParent->SetRight(left);
                    RemoveHelper(nodeParent->GetRight(), k);
                } else {
                    root = std::move(left);
                    RemoveHelper(root->GetLeft(), k);
                }
            } else {
                if(nodeParent) {
                    nodeParent->SetLeft(left);
                    RemoveHelper(nodeParent->GetLeft()->GetLeft(), k);
                } else {
                    root = std::move(left);
                    RemoveHelper(root->GetLeft(), k);
                }
            }
        } else if(node->GetRight()) {
            //  1 child
            //  make a copy of left
            std::unique_ptr<Node> rightLeft = std::move(node->GetRight()->GetLeft());
            std::unique_ptr<Node> rightRight = std::move(node->GetRight()->GetRight());

            //  make a copy of node
            std::unique_ptr<Node> right = std::move(node->GetRight());
            std::unique_ptr<Node> nodeLeft = std::move(node->GetLeft());
            Node* nodeParent = node->GetParent();

            bool isRightChild = false;
            if(nodeParent && nodeParent->GetRight() == node) {
                isRightChild = true;
            }

            //  setup node
            node->SetParent(right.get());
            node->SetRight(rightRight);
            node->SetLeft(rightLeft);

            //  setup left
            right->SetParent(nodeParent);
            right->SetRight(node);
            right->SetLeft(nodeLeft);

            //  connect left to parent
            //  and recursively call
            if(isRightChild) {
                if(nodeParent) {
                    nodeParent->SetRight(right);
                    RemoveHelper(nodeParent->GetRight()->GetRight(), k);
                } else {
                    root = std::move(right);
                    RemoveHelper(root->GetRight(), k);
                }
            } else {
                if(nodeParent) {
                    nodeParent->SetLeft(right);
                    RemoveHelper(nodeParent->GetLeft()->GetRight(), k);
                } else {
                    root = std::move(right);
                    RemoveHelper(root->GetRight(), k);
                }
            }
        } else if(node->GetLeft()) {
            //  1 child
            //  make a copy of left
            std::unique_ptr<Node> leftLeft = std::move(node->GetLeft()->GetLeft());
            std::unique_ptr<Node> leftRight = std::move(node->GetLeft()->GetRight());


            //  make a copy of node
            std::unique_ptr<Node> left = std::move(node->GetLeft());
            std::unique_ptr<Node> nodeRight = std::move(node->GetRight());
            Node* nodeParent = node->GetParent();

            bool isRightChild = false;
            if(nodeParent && nodeParent->GetRight() == node) {
                isRightChild = true;
            }

            //  setup node
            node->SetParent(left.get());
            node->SetRight(leftRight);
            node->SetLeft(leftLeft);

            //  setup left
            left->SetParent(nodeParent);
            left->SetLeft(node);
            left->SetRight(nodeRight);

            //  connect left to parent
            //  and recursively call
            if(isRightChild) {
                if(nodeParent){
                    nodeParent->SetRight(left);
                    RemoveHelper(nodeParent->GetRight()->GetLeft(), k);
                } else {
                    root = std::move(left);
                    RemoveHelper(root->GetLeft(), k);
                }
            } else {
                if(nodeParent) {
                    nodeParent->SetLeft(left);
                    RemoveHelper(nodeParent->GetLeft()->GetLeft(), k);
                } else {
                    root = std::move(left);
                    RemoveHelper(root->GetLeft(), k);
                }
            }
        } else {
            //  leaf
            //  remove
            node.reset();
        }
    } else if(node->GetRight() && node->GetRight()->GetKey() < k) {
        RemoveHelper(node->GetRight(), k);
    } else if(node->GetLeft() && node->GetLeft()->GetKey() > k) {
        RemoveHelper(node->GetLeft(), k);
    } else {
        //  not found
    }
}


template<class Key, class Data>
void bst::BST<Key,Data>::Insert(const Key& k, const Data& d)
{
    if(root) {
        InsertHelper(root, k, d);
    } else {
        root = std::unique_ptr<Node>(new Node(k,d, nullptr));
    }
}

template<class Key, class Data>
void bst::BST<Key,Data>::InsertHelper(std::unique_ptr<Node>& node, const Key& k, const Data& d)
{
    if(node->GetKey() < k) {
        //  insert into right subtree

        //  first check there is a right subtree
        if(node->GetRight()) {
            //  recursivley traverse the right subtree
            InsertHelper(node->GetRight(), k, d);
        } else {
            //  no right subtree?
            //  then insert item as right child
            std::unique_ptr<Node> tempNode(new Node(k,d, node.get()));
            node->SetRight(tempNode);
        }
    } else if(node->GetKey() > k) {
        //  insert into left subtree

        //  first check there is a left subtree
        if(node->GetLeft()) {
            //  recursivley traverse the left subtree
            InsertHelper(node->GetLeft(), k, d);
        } else {
            //  no left subtree?
            //  then insert item as left child
            std::unique_ptr<Node> tempNode(new Node(k,d, node.get()));
            node->SetLeft(tempNode);
        }
    } else {
        //  found
        //  insert here
        node->SetData(d);
    }
}

template<class Key, class Data>
void bst::BST<Key,Data>::Print(std::ostream& os)
{
    if(!root) {
        PrintHelper(os, root);
    }
}


template<class Key, class Data>
void bst::BST<Key,Data>::PrintHelper(std::ostream& os, std::unique_ptr<Node>& node)
{
    //  print key
    os << "Key: " << node->GetKey() << std::endl;

    if(node->GetLeft()) {
        os << "Left: " << node->GetLeft()->GetKey() << std::endl;
    } else {
        os << "Left: null" << std::endl;
    }

    if(node->GetRight()) {
        os << "Right: " << node->GetRight()->GetKey() << std::endl;
    } else {
        os << "Right: null" << std::endl;
    }

    os << std::endl;

    if(node->GetLeft()) {
        PrintHelper(os, node->GetLeft());
    }

    if(node->GetRight()) {
        PrintHelper(os, node->GetRight());
    }
}


#endif /* BST_h */

main.cpp

//
//  main.cpp
//  BST
//
//  
//
//

#include <iostream>
#include "BST.h"

int main(int argc, const char * argv[]) {


    bst::BST<int,int> bst1;
    bst1.Insert(6, 6);
    bst1.Insert(4, 4);
    bst1.Insert(8, 8);

    bst1.Insert(3, 3);
    bst1.Insert(5, 5);

    bst1.Insert(7, 7);
    bst1.Insert(9, 9);

    bst1.Print(std::cout);

    bst1.Remove(6);

    bst1.Print(std::cout);

    // insert code here...
    std::cout << "Hello, World!\n";

    std::cin.get();

    return 0;
}

Я добавил код на GitHub здесь

Я использую уникальный указатель на диспетчер памяти. Каждый узел имеет левого и правого ребенка. Может двигаться только дочерний узел.



Комментарии
1 ответ

Комментарий Код

Традиционные, что макросы все в верхнем регистре.

#ifndef BST_h
#define BST_h

Кроме того, что коротковат. Когда я делаю это, я обычно добавляю пространство имен кода в составе караула. Также вы хотите сделать пространство уникальным (поэтому он никогда не будет конфликтовать, я использую название домена, которым я владею, вы могли бы использовать МНГ?). Другие соглашения об именовании, которые вы должны высматривать. Определяемые пользователем типы, как правило, имеют начальную букву достопримечательностей и объектов и функций, как правило, имеют начальную букву в нижнем регистре. Лично я также инициализировать первой буквы в пространстве имен, но это очень случайный.

Я бы сделал что-то вроде этого:

#ifndef  SRG_TREE_BST_H
#define SRG_TREE_BST_H

namespace SRG::Tree {
class BST {
// STUFF
};
}
#endif

Компилятор должен сгенерировать предупреждение об этом.

        Node(const Key& k, const Data& d, Node* p)
: key(k)
, data(d)
, left(nullptr)
, right(nullptr)
, parent(p) {}

Порядок в списке не важен. Заказа члены инициализируются в порядке их объявления в ниже. Компилятор должен предупредить вас, что два заказа не совпадают. Почему компилятор предупреждает Вас, что на более сложные классы это может быть важно (порядок инициализации членов) и это ложное впечатление вы даете читателя может смутить их. Так всегда делают инициализации списка том же порядке, как порядке декларации.

Вторичное внимание. Так как это составляет для вас это означает, что вы не обрабатываете ошибки как предупреждения. Вернуться в свой компилятор и свою очередь, до предупреждения уровня, как высоко, как это пойдет. Затем установить компилятор будет рассматривать предупреждения как ошибки. Каждый предупреждение-это логическая ошибка в вашем мышлении. Весь новый код должен компилироваться с нулевым предупреждения.

Геттеры/сеттеры нарушить инкапсуляцию и разоблачать внутренних видов класса. Они, как правило, считается плохая вещь в C++. Они очень понравились в Java, потому что много средства использовать их.

В C++ мы предпочитаем action() методы, которые изменяют класс, а не вам(), выполнить действия, установить (), если это утечки функциональность класса к внешним объектам.

В этом случае Node это просто свойство сумка. Единственный класс с доступов является bst так просто сделать члены общественных и позволить дереву, чтобы эффективно управлять ими.

        const Key& GetKey() const { return key; }
Key& GetKey() { return key; }
const Data& GetData() const { return data; }
Data& GetData() { return data; }
std::unique_ptr<Node>& GetLeft() { return left; }
const std::unique_ptr<Node>& GetLeft() const { return left; }
std::unique_ptr<Node>& GetRight() { return right; }
const std::unique_ptr<Node>& GetRight() const { return right; }
Node* GetParent() { return parent; }
const Node* GetParent() const { return parent; }

void SetLeft(std::unique_ptr<Node>& l) { left = std::move(l); }
void SetRight(std::unique_ptr<Node>& r) { right = std::move(r); }
void SetParent(Node* p) { parent = p; }
void SetData(const Data& d) { data = d; }

Конечно, вы можете использовать здесь умные указатели.

        std::unique_ptr<Node> left;
std::unique_ptr<Node> right;

Лично я думаю, что дерево могло справиться с этим. Но я не могу действительно жаловаться на использование. Так что это просто личный комментарий.

Родителя. Хммм.

        Node* parent;

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

Уверен, что это способ найти, чтобы:

    void Print(std::ostream& os); // should this not be const???

Но в C++ печать обычно осуществляется через operator<<. Таким образом, вы должны определить это (оно может вызвать Print).

    friend std::ostream& operator<<(std::ostream& s, bst const& t) {
t.Print(s);
return s;
}

Не оставляйте пустые блоки, лежащие вокруг кода.

    if(root) {
RemoveHelper(root, k);
} else {
// empty tree // Useless comment delete this block.
}

Есть вспомогательную функцию, чтобы сделать unique_ptr является объекты: std::make_unique().

    if(root) {
InsertHelper(root, k, d);
} else {
// root = std::unique_ptr<Node>(new Node(k,d, nullptr));
root = std::make_unique<Node>(k, d, nullptr);
}

Аааа печати и рекурсии.

Во всех остальных местах у вас есть нулевым. Печати nullно не для корневого узла. Что означает пустой гравюры на дереве ничего. Это кажется немного противоречивым. Я бы сделал его распечатать null для пустого дерева.

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

    if(!root) {
PrintHelper(os, root);
}

Рекурсия. Вы можете сделать свой рекурсии намного проще. В первую вещь, которую вы сделать, это проверить, если у вас отвалилась после конца. Если да вернуться (и вы можете печатать значение null). Затем вы можете сделать все ваши печатные работы, зная, что вы находитесь в действительный узел.

Тоже предпочитаю "\n" за std::endl. Разница между двумя заключается в том, что std::endl заставит буфера для промывки (которая делает поток очень неэффективно). Автоматическая промывка-это почти всегда неправильно, что нужно делать и причины замедлений в потоковом код.

Так что я бы переписать свою печать, как это:

template<class Key, class Data>
void bst::BST<Key,Data>::Print(std::ostream& os)
{
PrintHelper(os, root.get());
}

template<class Key, class Data>
void bst::BST<Key,Data>::PrintHelper(std::ostream& os, Node* node)
{
if (node == nullptr) {
os << "null\n";
}

// print key
os << "Key: " << node->GetKey() << "\n"
<< "Left: (" << node->GetLeft().get() << ")\n"
<< ", Right: (" << node->GetRight().get() << ")\n;
}

Эти последние два огромные функции. Путь больше, чем они должны быть (я держу пари держать parent член в линию правильно. Я еще не успел дигг в них и найти проблему. Но я вернусь сегодня вечером.

Но как эти строки меня пугают:

            //  make a copy of node
std::unique_ptr<Node> left = std::move(node->GetLeft());
std::unique_ptr<Node> nodeRight = std::move(node->GetRight());

Неа. Вы не делаете копию. Вы просто перенесли указатели. Комментарии, которые не синхронизированы с кодом хуже то бесполезные комментарии. Вы хотите, чтобы я поверила в комментарии (Вы делаете копию), а я считаю, что код (перемещении указателей). Вы верите, что вы делали копии, и это предположение вызывает код ниже, чтобы сломать? Я не знаю. В качестве сопровождающего, я бы тебя ненавидеть как я теперь бы нужно отлаживать свой код, чтобы убедиться, что вы сделали это правильно, то исправить ваш код или ваш комментарий.

Вставьте Вспомогательную

Мой первый хоть об этом. Заключается в том, что если ключ уже существует, то его не вводя данные (мы с перезаписью данных). Теперь это может быть ОК, но было бы неплохо знать. Если мы посмотрим на стандартные контейнеры вставки в std::карта возвращает логическое значение, указывающее, если вставить получилось (правда данные были вставлены, ложные сведения не был вставлен, но данные в карте).

Остальное возвращается к стандартной рекурсии. Вы можете удалить половину остального кода. Не проверять, если влево/вправо нулевые, но просто повторно звонить InsertHelper() перестройка и новое значение. Если значение является нулем на входе вас создать значение и вернуть его.

// This is how I would write it.
// Slightly different as I would use pointers not smart pointers
// But I am sure you can modify to copensate.
Node* bst::BST<Key,Data>::InsertHelper(Node* node, const Key& k, const Data& d)
{
// When you fall off the end
// Then create the node and return it.
if (node == nullptr) {
return new Node(k, d, nullptr);
}

if (k < node->key) {
node->left = InsertHelper(node->left, k, d);
}
else if (k > node->key) {
node->right = InsertHelper(node->right, k, d);
}
else {
node->data = d;
}
// If you did not fall of the end.
// Then return the node as the result so it sets itself back.
return node;
}

Удалить Helper

Одна вещь, я хотел бы отметить, это то, что вы обычно не проходят unique_ptr не по ссылке.

void bst::BST<Key,Data>::PrintHelper(std::ostream& os, std::unique_ptr<Node>& node);

Если интерфейс требует unique_ptr по ссылке вы можете сказать, если это берут на себя ответственность или нет. Когда вы проходите unique_ptr на интерфейс параметр обычно значение параметра это вынуждает вас использовать std::move() для передачи собственности. Я полагаю, что в данном случае это может быть нормально, а вы не знаете, если вы собираетесь взять на себя ответственность, но в случае использования меня немного настораживает.

Это путь к долгой случай, но в особых случаях.

Это должно выглядеть так:

// This is how I would write it.
// Slightly different as I would use pointers not smart pointers
// But I am sure you can modify to copensate.
Node* bst::BST<Key,Data>::RemoveHelper(Node* node, const Key& k)
{
// When you fall off the end
// the key was not found. So just return null.
if (node == nullptr) {
return nullptr;
}

// In most cases we return the current node.
// So lets keep track of that separately. If this
// is the node we are going to delete then we update
// this with the node we are going to replace it with.
Node* result = node;

if (k < node->key) {
// Note if we don't remove node-left then it will
// return back the same value and nothing happens.
// If we do delete node->left we will return the replacement value.
// Note: In this case the node is not deleted so result is not changed.
node->left = RemoveHelper(node->left, k);
}
else if (k > node->key) {
// See comment above about left.
node->right = RemoveHelper(node->right, k);
}
else {

// We found the node we delete.
// In here we must change `result` to reflect the new node.

// If either of the sub-trees is empty this becomes easy as the other
// sub-tree becomes the new current node.
if (node->left == nullptr || node->right == nullptr) {
result = node->left == nullptr ? node->right : node->left;
delete node;
}
else {
// OK both sub trees are not null.
// We must find a node to be used here.
// A node where all the nodes to the right are larger
// and all the nodes to the left are smaller.
//
// If we look in the right sub-tree. Then the left most
// node in this sub tree fulfills these requirements.
// We can also easily remove it as it will not have a
// left-subtree. Once we have it assign the
// left and right sub-trees of the current node to it
// It will be inserted into the tree with the return
// below.
node->right = findLeftMostNode(node->right, result);
result->left = node->left;
result->right= node->right;
delete node;
}

}
// If you did not fall of the end.
// Then return the result
return result;
}

Node* findLeftMostNode(Node* node, Node*& result)
{
if (node->left == nullptr) {
// We found the left most node. So this is the result.
result = node;
// We return its right-subtree so that it can be glued
// back into the BST.
return node->right;
}

// We have not found the left most node.
// So keep looking.
node->left = findLeftMostNode(node->left, result);
return node;
}

6
ответ дан 21 марта 2018 в 03:03 Источник Поделиться