Двоичный поиск древовидной структуры данных реализация в C++11 с помощью смарт-указатели


Эта реализация является частью моего проекта с открытым исходным кодом лес.

Я написал следующий заголовочный файл для реализации двоичного структура поиска данных дерево, которое поддерживает следующие операции:

  • Вставить
  • Поиск
  • Предзаказ Обхода
  • В Порядке Обхода
  • Обход В Обратном Порядке
  • В Ширину Обход
  • Найти Минимум
  • Найти Максимальное
  • Найти Предшественника
  • Найти Преемника
  • Высота
  • Размер
  • Пустые

Я с нетерпением жду, чтобы услышать Ваше мнение об этой реализации и предложения/исправления вы можете иметь.

/**
 * @file binary_search_tree.h
 */

#ifndef BINARY_SEARCH_TREE_H
#define BINARY_SEARCH_TREE_H

#include <iostream>
#include <algorithm>
#include <queue>
#include <fstream>
#include <memory>

/**
 * @brief The forest library namespace
 */
namespace forest {
  namespace binary_search {
    /**
     * @brief binary search Tree node struct
     */
    template <typename key_t>
    struct node {
      key_t key;     ///< The key of the node
      std::weak_ptr<node> parent;    ///< The parent of the node
      std::shared_ptr<node> left;    ///< The left child of the node
      std::shared_ptr<node> right;   ///< The right child of the node
      /**
       * @brief Constructor of a binary search tree node
       */
      node(const key_t key) {
        this->key = key;
        this->parent.reset();
        this->left = nullptr;
        this->right = nullptr;
      }
    };
    /**
     * @brief binary search tree class
     */
    template <typename key_t>
    class tree {
    private:
      std::shared_ptr<node <key_t> > root;
      void pre_order_traversal(std::shared_ptr<node <key_t> > &x, void handler(std::shared_ptr<node <key_t> >)) {
        if (x == nullptr) return;
        handler(x);
        pre_order_traversal(x->left, handler);
        pre_order_traversal(x->right, handler);
      }
      void in_order_traversal(std::shared_ptr<node <key_t> > &x, void handler(std::shared_ptr<node <key_t> >)) {
        if (x == nullptr) return;
        in_order_traversal(x->left, handler);
        handler(x);
        in_order_traversal(x->right, handler);
      }
      void post_order_traversal(std::shared_ptr<node <key_t> > &x, void handler(std::shared_ptr<node <key_t> >)) {
        if (x == nullptr) return;
        post_order_traversal(x->left, handler);
        post_order_traversal(x->right, handler);
        handler(x);
      }
      void breadth_first_traversal(std::shared_ptr<node <key_t> > &x, void handler(std::shared_ptr<node <key_t> >)) {
        std::queue <std::shared_ptr<node <key_t> > > queue;
        if (x == nullptr) return;
        queue.push(x);
        while(queue.empty() == false) {
          std::shared_ptr<node <key_t> > y = queue.front();
          handler(y);
          queue.pop();
          if (y->left != nullptr) queue.push(y->left);
          if (y->right != nullptr) queue.push(y->right);
        }
      }
      const unsigned long long height(std::shared_ptr<node <key_t> > &x) {
        if (x == nullptr) return 0;
        return std::max(height(x->left), height(x->right)) + 1;
      }
      const unsigned long long size(std::shared_ptr<node <key_t> > &x) {
        if (x == nullptr) return 0;
        return size(x->left) + size(x->right) + 1;
      }
    public:
      tree() {
        root = nullptr;
      }
      ~tree() {

      }
      /**
       * @brief Performs a Pre Order Traversal starting from the root node
       * @return void
       */
      void pre_order_traversal(void handler(std::shared_ptr<node <key_t> >)) {
        pre_order_traversal(root, handler);
      }
      /**
       * @brief Performs a In Order Traversal starting from the root node
       * @return void
       */
      void in_order_traversal(void handler(std::shared_ptr<node <key_t> >)) {
        in_order_traversal(root, handler);
      }
      /**
       * @brief Performs a Post Order Traversal starting from the root node
       * @return void
       */
      void post_order_traversal(void handler(std::shared_ptr<node <key_t> >)) {
        post_order_traversal(root, handler);
      }
      /**
       * @brief Performs a Breadth First Traversal starting from the root node
       * @return void
       */
      void breadth_first_traversal(void handler(std::shared_ptr<node <key_t> >)) {
        breadth_first_traversal(root, handler);
      }
      /**
       * @brief Inserts a new node into the binary search tree
       * @param key The key for the new node
       * @return The the inserted node otherwise nullptr
       */
      const std::shared_ptr<node <key_t> > insert(const key_t key) {
        std::shared_ptr<node <key_t> > current = root;
        std::shared_ptr<node <key_t> > parent = nullptr;
        while(current!=nullptr) {
          parent = current;
          if (key > current->key) {
            current = current->right;
          } else if (key < current->key) {
            current = current->left;
          } else {
            return nullptr;
          }
        }
        current = std::make_shared<node <key_t> >(key);
        current->parent = parent;
        if(parent == nullptr) {
          root = current;
        } else if (current->key > parent->key) {
          parent->right = current;
        } else if (current->key < parent->key) {
          parent->left = current;
        }
        return current;
      }
      /**
       * @brief Performs a binary search starting from the root node
       * @return The node with the key specified otherwise nullptr
       */
      const std::shared_ptr<node <key_t> > search(const key_t key) {
        std::shared_ptr<node <key_t> > x = root;
        while (x != nullptr) {
          if (key > x->key) {
            x = x->right;
          } else if (key < x->key) {
            x = x->left;
          } else {
            return x;
          }
        }
        return nullptr;
      }
      /**
       * @brief Finds the node with the minimum key
       * @return The node with the minimum key otherwise nullptr
       */
      const std::shared_ptr<node <key_t> > minimum() {
        std::shared_ptr<node <key_t> > x = root;
        if (x == nullptr) return nullptr;
        while(x->left != nullptr) x = x->left;
        return x;
      }
      /**
       * @brief Finds the node with the maximum key
       * @return The node with the maximum key otherwise nullptr
       */
      const std::shared_ptr<node <key_t> > maximum() {
        std::shared_ptr<node <key_t> > x = root;
        if (x == nullptr) return nullptr;
        while(x->right != nullptr) x = x->right;
        return x;
      }
      /**
       * @brief Finds the successor of the node with key specified
       * @return The successor of the node with key specified otherwise nullptr
       */
      const std::shared_ptr<node <key_t> > successor(const key_t key) {
        std::shared_ptr<node <key_t> > x = root;
        while (x != nullptr) {
          if (key > x->key) {
            x = x->right;
          } else if (key < x->key) {
            x = x->left;
          } else {
            if (x->right != nullptr) {
              x = x->right;
              while(x->left != nullptr) x = x->left;
              return x;
            }
            std::shared_ptr<node <key_t> > parent = x->parent.lock();
            while (parent != nullptr && x == parent->right) {
              x = parent;
              parent = parent->parent.lock();
            }
            return parent;
          }
        }
        return nullptr;
      }
      /**
       * @brief Finds the predecessor of the node with key specified
       * @return The predecessor of the node with key specified otherwise nullptr
       */
      const std::shared_ptr<node <key_t> > predecessor(const key_t key) {
        std::shared_ptr<node <key_t> > x = root;
        while (x != nullptr) {
          if (key > x->key) {
            x = x->right;
          } else if (key < x->key) {
            x = x->left;
          } else {
            if (x->left != nullptr) {
              x = x->left;
              while(x->right != nullptr) x = x->right;
              return x;
            }
            std::shared_ptr<node <key_t> > parent = x->parent.lock();
            while (parent != nullptr && x == parent->left) {
              x = parent;
              parent = parent->parent.lock();
            }
            return parent;
          }
        }
        return nullptr;
      }
      /**
       * @brief Finds the height of the tree
       * @return The height of the binary search tree
       */
      const unsigned long long height() {
        return height(root);
      }
      /**
       * @brief Finds the size of the tree
       * @return The size of the binary search tree
       */
      const unsigned long long size() {
        return size(root);
      }
      /**
       * @brief Finds if the binary search tree is empty
       * @return true if the binary search tree is empty and false otherwise
       */
      const bool empty() {
        if (root == nullptr) {
          return true;
        } else {
          return false;
        }
      }
    };
  }
}

#endif

Вот демонстрация того, как выше заголовочный файл может использоваться.

    #include "binary_search_tree.h"

    int main() {
        // Generate a binary_search tree with integer keys
        forest::binary_search::tree <int> binary_search_tree;

        // Insert 7 plain nodes
        binary_search_tree.insert(4);
        binary_search_tree.insert(2);
        binary_search_tree.insert(90);
        binary_search_tree.insert(3);
        binary_search_tree.insert(0);
        binary_search_tree.insert(14);
        binary_search_tree.insert(45);

        // Perform In-Order-Traversal
        binary_search_tree.in_order_traversal([](auto node){ std::cout << node->key << std::endl; });

    return 0;
}


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

Я бы поставил узла внутри дерева, как частный член.

    template <typename key_t>
struct node {
key_t key; ///< The key of the node
std::weak_ptr<node> parent; ///< The parent of the node
std::shared_ptr<node> left; ///< The left child of the node
std::shared_ptr<node> right; ///< The right child of the node
/**
* @brief Constructor of a binary search tree node
*/
node(const key_t key) {
this->key = key;
this->parent.reset();
this->left = nullptr;
this->right = nullptr;
}
};

Таким образом в дереве кодекса можно ссылаться как node а не node<key_t>. Немного короче.

Что еще более важно node является реализацией деталь, которая не должна быть доступна пользователю из дерева. Подвергая его вы не подтекает детали реализации и привязка самостоятельно, чтобы поддерживать ее.

Заметка о наименовании. Определяемые пользователем типы, как правило, начинаются с прописной буквы. В то время как переменные и функции начинаются с маленькой буквы. В C++ есть чрезвычайно важная информация, она позволяет быстро визуально определить тип и таким образом понять смысл быстрее код.

Я не вижу необходимости parent член. Он просто делает вещи более сложными.

Почему ты используешь std::shared_ptr? Делает узел свой левый и правый детей. Что другой объект owns узел другой, чем его родитель? Кажется, плохой выбор на мой взгляд и вы могли бы упростить код, используя std::unique_ptr.

Во всех ваших обходов у вас handler функция, чтобы сделать работу на каждом узле.

      void pre_order_traversal(std::shared_ptr<node <key_t> > &x, void handler(std::shared_ptr<node <key_t> >));

Но почему обработчик узла получить shared_ptr по значению. Почему вы не сдали общий указатель на ссылку? Почему это даже сделать общий указатель? Обработчик не должен иметь возможности модифицировать дерево (как он может нарушать ограничения на дереве). На мой взгляд единственное, что обработчик может сделать-это объект данных, и только константной этого объекта данных.

      void pre_order_traversal(std::shared_ptr<node <key_t> > &x, void handler(key_t const&));

Не знаю, почему вы задаете функцию. Проблема в том, что много кода в C++11 и C++14 и C++17 использует лямбды (которые функторы (наверное)). Так что ваш обработчик должен быть шаблон, который позволяет любому обобщенный код, который будет выполнен.

      // Unchecked syntax here.
// You may need to tweak but it will be similar to this.
void pre_order_traversal(std::shared_ptr<node <key_t> > &x, std::function<void(key_t)>&);

Не определите методы, которые вам не нужны.

      tree() {
root = nullptr;
}
~tree() {

}

Ваш член root ручками все это автоматически. Вам не нужно определить конструктор.

Предпочитают не передавать объекты по значению.

      const std::shared_ptr<node <key_t> > insert(const key_t key) {

Если key_t большой, то вы вынуждают unneccasery копии дорогих для копирования объекта. Пройти по ссылку или R-значение ссылки.

      const std::shared_ptr<node <key_t> > insert(key_t const& key) {
const std::shared_ptr<node <key_t> > insert(key_t&& key) {

Почему вы возвращаетесь в shared_ptr? Может булевую переменную, чтобы указать на успехи. Но, возвращаясь узла позволяет другим людям много вокруг дерева и отменить ограничения на дереве. Вы должны стоять на страже против этих доступов не продвигая его.

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

Если вы хотите дать доступ к дереву у итератор (нужно только иметь родителя указатель на узел).

Это может быть упрощена.

      const bool empty() {
if (root == nullptr) {
return true;
} else {
return false;
}
}

Вам не нужен тест на логическое условие ветвь кода, которая возвращает логическое значение. Просто вернуть выражение.

      const bool empty() const {  // const method.
return (root == nullptr);
}

Также обратите внимание, эта функция (и высота/размер) и т. д. не изменяют внутреннюю структуру дерева. В результате они должны быть отмечены const.

8
ответ дан 4 апреля 2018 в 03:04 Источник Поделиться

#ifndef BINARY_SEARCH_TREE_H
#define BINARY_SEARCH_TREE_H

Предпочитают использовать названия знаков, которые имеют некоторую степень уникальности к ним. Просто повторно использовать имя заголовка охранник может привести к высока вероятность столкновений между токены препроцессора. Вы можете использовать:


  • Название Проекта

  • Имя Пространства Имен

  • Имя файла

  • Любой хороший дифференциатор - идентификатор GUID / дата создания / случайных чисел

Пример:

//      LIB   NS     FILE                 DATE
#ifndef MYLIB_FOREST_BINARY_SEARCH_TREE_H_04042018
#define MYLIB_FOREST_BINARY_SEARCH_TREE_H_04042018


#include <iostream>
#include <algorithm>
#include <queue>
#include <fstream>
#include <memory>

Старайтесь держать #includeзаказал. Особенно когда вы попадаете в более крупные проекты, так проще для разработчиков кода в двоичный/словарь поиск через ваш список сравнения линейный поиск.


template <typename key_t>
struct node { ... };

Не подвергайте детали реализации. node является реализацией деталь tree. Нет никаких причин, пользователи библиотеки должны знать, как вы реализовали ваш бинарное дерево поиска (БСТ).

    template <typename key_t>
class tree {
private:
struct node { ... };


      std::weak_ptr<node> parent;    ///< The parent of the node
std::shared_ptr<node> left; ///< The left child of the node
std::shared_ptr<node> right; ///< The right child of the node

Это std::shared_ptr естественный собственности абстракция для вашего tree? Каждый node в дереве принадлежит одной другой node (или корень), так std::shared_ptr это перебор по сравнению с std::unique_ptr. Если вы хотите ссылаться на свои родителя, нет ничего плохого в использовании сырых указателей в собственности контекстах. В C++17 будет предоставлять мира тупой смарт-указатель, если вы действительно хотите, чтобы избежать сырые указатели.

      node * parent;                 ///< The parent of the node
std::unique_ptr<node> left; ///< The left child of the node
std::unique_ptr<node> right; ///< The right child of the node


      node(const key_t key) {
this->key = key;
this->parent.reset();
this->left = nullptr;
this->right = nullptr;
}

Предпочитаю инициализации присваивания в конструкторах. Некоторые типы классов не могут быть назначены; некоторые не могут быть по умолчанию-инициализировать, некоторые могут быть дорогими, чтобы назначить вместо инициализации.

      node(const key_t key)
: key(key),
parent{nullptr},
left{nullptr},
right{nullptr} {
}

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

      node * parent {nullptr};              
std::unique_ptr<node> left {nullptr};
std::unique_ptr<node> right {nullptr};

explicit node(const key_t key) : key {key} {}


namespace forest {
namespace binary_search {
template <typename key_t>
class tree { ... }

Нейминг-это важно. Когда пользователи вашей библиотеки сталкиваются с ваш код, они могут сказать, что он делает? Существует множество сортов деревьев. tree не дают типа дерева, если его указанием пространства имен. Что может быть using объявлены другими. Вместо этого, не больше смысла в название класса binary_search_tree? Сделать работу с библиотекой код проще для читателей и писателей.


      void pre_order_traversal(std::shared_ptr<node <key_t> > &x, void handler(std::shared_ptr<node <key_t> >)) {
if (x == nullptr) return;
handler(x);
pre_order_traversal(x->left, handler);
pre_order_traversal(x->right, handler);
}

Не пропустите интеллектуального указателя в качестве параметра функции, если вы хотите использовать или манипулировать собой смарт-указатель (т. е. доля/передача права собственности). Увидеть GOTW 91

Делать пустые и однострочные высказывания видно.

        if (x == nullptr) {
return;
}


    const std::shared_ptr<node <key_t> > insert(const key_t key) {

Для входных параметров, проходят типы, дешево копировать по значению, а все остальное со ссылкой на const. Мы не знаем, что key_t пользователь планирует использовать, может быть intможет быть std::string.

Не вызываемый необходимостью собственного вставленный узел? Стандартная библиотека возвращает пару, что говорит звонящий, если он уже существовал и итератор, указывающий туда, где он существует или был вставлен. Если вы хотите раздавать сильная ссылка, рассмотреть вопрос об использовании std::shared_ptrС сглаживания конструктора (см. #8), чтобы вернуть key_t вместо всего node.


Рассмотрим читаемость callsite. Почему пользователи вашей библиотеки будут волновать детали node? Не лучше ли просто передать значение функции отображается?

        handler(x->key);

В callsite, пользователь имеет дело только с значения.

    binary_search_tree.in_order_traversal([](auto key){ std::cout << key << std::endl; });


      ~tree() {

}

Поскольку деструкторы являются рекурсивными по умолчанию, деструктор ваше дерево по сути делает следующее:

      ~tree() {
// destroy root here
// which calls root->~node()
// which calls root->left->~node()
// which calls root->left->left->~node()
// which calls root->left->left->left->~node()
// which calls root->left->left->left->left->~node()
// ...
}

Игнорируя тот факт, что вы позволяете внутренним узлам долевой собственности извне, считают в худшем случае ситуация с реализацией: дерево \ФП\$ элементы, заказать, с широтой \$1\$ (в основном связанного списка). Все нормально , если у вас достаточно места в стеке для все эти рекурсивные вызовы деструктора. Поскольку глубина стека не ограничена это, вам потребуется предоставить итеративный подход к уничтожению дерева.

Также рассмотрим, как операции копирования работать с Смарт-указатели. std::shared_ptr это можно копировать, но копия по умолчанию операции просто доли собственности (поверхностное копирование) вместо создания индивидуальной собственности объекта (глубокое копирование). std::unique_ptr не копируемыми. Чтобы получить правильное поведение для копирования дерева, необходимо выполнять эти специальные членами самостоятельно.

Значит вам нужен пользовательский деструктор, конструктор копирования и копирующий оператор присваивания. Согласно правилу пяти, Если вам нужны какие-либо специальные функции-члены, вы должны рассмотреть их все и явно определить их (=default, =deleteили определяемой пользователем).

      ~tree() {...}                             // user-defined dtor
tree(const tree& other) {...} // user-defined copy ctor
tree& operator=(const tree& other) {...} // user-defined copy assign

tree(const tree&) = default; // is the compiler generated
tree(tree&&) = default; // good enough?

2
ответ дан 5 апреля 2018 в 02:04 Источник Поделиться