Struct bintree::tree::BinaryTree

pub struct BinaryTree<T> where
    T: Copy + Clone + PartialOrd + PartialEq,  { /* fields omitted */ }

Реализация бинарного дерева поиска на языке Rust. О СТРУКТУРЕ: Бинарное дерево поиска (Binary Search Tree) - условно направленный граф, каждый узел котрого имеет ключ - некое значение, которое можно сравнивать и две ветви - правую и левую. (будем считать, что ветви есть всегда, просто они могут быть либо пустыми, либо содержать значение). В левой ветви хранятся узлы, ключи (значения) которых меньше ключа текущего узла. В классической реализации бинарное дерево не хранит одинаковые ключи. В моей реализации это возможно, узлы, ключи которых больше или равны текущему хранятся в левой ветви.

В текущей реализации удалять ключи ПОКА ЧТО нельзя из-за сложностей реализации, но это временно. Реализована система добавления и поиска ключа, а также ряд других полезных фич, упрощающих жизнь.

Дерево можно сравнивать с себе подобными деревьями по принципу "равно-неравно". От трейта PartialOrd решил отказаться во избежание недопонимания пользователя. Если вы хотите сравнить размер, то это возможно сделать с помощью методов len() и is_empty(). Если вы хотите сравнивать ещё что-то, то можете написать свою функцию или реализовать полноценный трейт.

Также дерево можно вывести на экран с помощью форматного вывода (т.е. print!("{:?}" ...). Трейт Debug также упрощает работу с тестами, т.е. вы можете использовать дерево для тестирования моих или ваших функций.

Так же к дереву подключён трейт Clone, позволяющий полностью копировать экземпляр дерева, если в этом есть необходимость.

Дерево может импользовать все те типы, которые поддерживают трейты Copy, Clone, PartialOrd, PartialEq. Иными словами их можно переносить, копировать, сравнивать между собой по типу больше-меньше и равно-неравно. Если типы, которые вы хотите использовать, не поддерживают этих трейтов (а именно: сложные структуры, которые хранят свои значения в куче (Vec, LinkedList, HashMap и т.д.), срезы, статические массивы, NAN и т.д.), то вы не сможете импользовать дерево по техническим причинам :(

Если вы хотите полностью ознакомится с кодом, то переходите по ссылке ниже: https://github.com/dinaraparanid/Structures/tree/master/src Это репозиторий на GitHub с полной версией кода. Если есть предложения, то не стесняйтесь, предлагайте :)

Implementations

impl<T> BinaryTree<T> where
    T: Copy + Clone + PartialOrd, 

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

pub fn new() -> Self

Метод new() делает всё то же, что и default() По сути является конструктором для дерева.

Example

use bintree::tree::BinaryTree;

let new_tree = BinaryTree::<i32>::new();
let def_tree = BinaryTree::<i32>::default();

assert_eq!(new_tree.len(), 0); // размер дерева
assert_eq!(def_tree.len(), 0); // см. len() ниже

pub fn len(&self) -> usize

Метод len возвращает размер дерева как беззнаковое 64 битное Если вдруг размер оказался отрицательным, то вам немедленно нужно обратиться к врачу или перестать ломать чужой код :)

Example

use bintree::tree::BinaryTree;

let mut tree = BinaryTree::new();
tree.insert(&1); // добавление в дерево
tree.insert(&2); // об этом поговорим
tree.insert(&3); // позже

assert_eq!(tree.len(), 3);

pub fn is_empty(&self) -> bool

Метод is_empty() отвечает на вопрос: "пусто ли наше дерево?" Если пусто, то возвращается true, иначе false;

Example

use bintree::tree::BinaryTree;

let empty_tree = BinaryTree::<i32>::new();
let mut not_empty_tree = BinaryTree::new();

not_empty_tree.insert(&1);
not_empty_tree.insert(&2);
not_empty_tree.insert(&3);

assert_eq!(empty_tree.len(), 0);
assert_eq!(empty_tree.is_empty(), true);

assert_eq!(not_empty_tree.len(), 3);
assert_eq!(not_empty_tree.is_empty(), false);

pub fn insert(&mut self, val: &T)

Метод insert() добавляет значение в дерево. Значение берётся по неизменяемой ссылке, так что смело юзайте, хотя я бы не рекомендовал использовать типы, которые не хранятся на стеке или неразмерные типы. Ах, да, их и нельзя импользовать)

Example

use bintree::tree::BinaryTree;
 
let mut tree = BinaryTree::new();
tree.insert(&1);
tree.insert(&2);
tree.insert(&3);

assert_eq!(tree.contains(&1), true); // проверка на наличие значения в дереве.
assert_eq!(tree.contains(&2), true); // для лучшего понимания см tests.rs
assert_eq!(tree.contains(&3), true); // метод contains() рассмотрен ниже

pub fn contains(&self, val: &T) -> bool

Метод contains() проверяет наличие значения в дереве Если оно есть, то возвращает true, иначе false

Example

use bintree::tree::BinaryTree;

let mut tree = BinaryTree::new();
tree.insert(&1);
tree.insert(&2);
tree.insert(&3);

assert_eq!(tree.contains(&1), true);
assert_eq!(tree.contains(&2), true);
assert_eq!(tree.contains(&3), true);

pub fn first(&self) -> &T

Метод first() возвращает минимальное значение, которое хранится в дереве. Если дерево пустое, то пудет вызвана паника, сообщающая о том, что дерево пусто, так что будьте осторожны.

Example

use bintree::tree::BinaryTree;

let mut tree = BinaryTree::new();

tree.insert(&3);
assert_eq!(tree.first(), &3);

tree.insert(&2);
 assert_eq!(tree.first(), &2);

tree.insert(&1);
 assert_eq!(tree.first(), &1);

pub fn last(&self) -> &T

Метод last() возвращает наибольший элемент дерва. В случае, когда дерево пусто, вызывается паника.

Example

use bintree::tree::BinaryTree;

let mut tree = BinaryTree::new();

tree.insert(&1);
assert_eq!(tree.last(), &1);

tree.insert(&2);
assert_eq!(tree.last(), &2);

tree.insert(&3);
assert_eq!(tree.last(), &3);

pub fn append(&mut self, other: &BinaryTree<T>)

Метод append() передаёт элементы из 1 дерева в другое. Используемое дерево остаётся неизменным, так что его можно также использовать. Здесь мы создаём итератор из второго дерева и перемещаем по ссылкам элементы в первое дерево.

Example

use bintree::tree::BinaryTree;

let mut tree1 = BinaryTree::new();
let mut tree2 = BinaryTree::new();

tree1.insert(&1);
tree2.insert(&2);
tree2.insert(&3);

tree1.append(&tree2);

assert_eq!(tree1.into_iter().collect::<Vec<i32>>(), vec![1, 2, 3]);

Trait Implementations

impl<T: Clone> Clone for BinaryTree<T> where
    T: Copy + Clone + PartialOrd + PartialEq, 

fn clone(&self) -> BinaryTree<T>

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<T: Debug> Debug for BinaryTree<T> where
    T: Copy + Clone + PartialOrd + PartialEq, 

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<T> Default for BinaryTree<T> where
    T: Copy + Clone + PartialOrd + PartialEq, 

Головная структура дерево хранит 2 поля: вершину дерева и размер дерева. Вершина дерева представлена структурой TreeKnot - узел дерева (см knot.rs)

fn default() -> Self

Returns the "default value" for a type.

impl<T> FromIterator<T> for BinaryTree<T> where
    T: Copy + Clone + PartialOrd + PartialEq, 

Добавление трейта FromIterator для дерева Теперь мы можем построить целое дерево из итератора.

Example

use bintree::tree::BinaryTree;
use std::iter::FromIterator;

let range = (0..11).step_by(2);
let mut new_tree = BinaryTree::from_iter(range);

assert_eq!(new_tree.into_iter().collect::<Vec<i32>>(), vec![0, 2, 4, 6, 8, 10]);

fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self

Creates a value from an iterator.

impl<T> IntoIterator for BinaryTree<T> where
    T: Copy + Clone + PartialOrd + PartialEq, 

Добавляем дереву трейт IntoIterator. Теперь мы можем итерироваться (ходить) по дереву. Типом, который хранит наш итератор является пользовательский тип, который должен соответствовать правилам, описанным выше. В качестве итератора используем свою структуру TreeIter (см. iter.rs)

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

Example

use bintree::tree::BinaryTree;

let mut tree = BinaryTree::new();

tree.insert(&1);
tree.insert(&2);
tree.insert(&3);

let test1 = tree.clone().into_iter().collect::<Vec<i32>>();
let test2 = tree.clone().into_iter().min().unwrap();
let test3 = tree.clone().into_iter().sum::<i32>();

assert_eq!(test1, vec![1, 2, 3]);
assert_eq!(test2, 1);
assert_eq!(test3, 6);

type Item = T

The type of the elements being iterated over.

type IntoIter = TreeIter<T>

Which kind of iterator are we turning this into?

fn into_iter(self) -> TreeIter<T>

Метод into_iter() превращает наше дерево в TreeIter.

Example

use bintree::tree::BinaryTree;

let mut tree1 = BinaryTree::new();
let mut tree2 = BinaryTree::new();

tree1.insert(&1);
tree2.insert(&2);
tree2.insert(&3);

tree1.append(&tree2);

assert_eq!(tree1.into_iter().collect::<Vec<i32>>(), vec![1, 2, 3]);

impl<T: PartialEq> PartialEq<BinaryTree<T>> for BinaryTree<T> where
    T: Copy + Clone + PartialOrd + PartialEq, 

fn eq(&self, other: &BinaryTree<T>) -> bool

This method tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &BinaryTree<T>) -> bool

This method tests for !=.

impl<T> StructuralPartialEq for BinaryTree<T> where
    T: Copy + Clone + PartialOrd + PartialEq,