[OOP] Common Type System - Задача 6


9

 

Define the data structure binary search tree with operations for "adding new element", "searching element" and "deleting elements". It is not necessary to keep the tree balanced. Implement the standard methods from System.Object – ToString(), Equals(…), GetHashCode() and the operators for comparison  == and !=. Add and implement the ICloneable interface for deep copy of the tree. Remark: Use two types – structure BinarySearchTree (for the tree) and class TreeNode (for the tree elements).
 
Някой имали идея какво точно се иска в задачата да ми подскаже малко.

в C# OOP от Божидар Пенчев (0 точки)


Отговори



30

Малко теория:

Двоичното дърво е структура от данни съставена от елементи (nodes) и връзки между тях. Всяка връзка е или null (не същестува) или сочи към ноуд. Всеки ноуд се сочи точно от един друг ноуд, който е негов родител и може да сочи най-много два друди ноуда – ляв наследник и десен наследник. Наследниците също са двоични дървета, съответно ляво и дясно поддрърво.

Двоично дърво за търсене е двоично дърво, при което всички елементи от лявото поддърво са по-малки от корена и всички елементи от дясното поддърво са по-големи от корена.

Обхождане на двоично дърво

Обхождане по ширинина - Елементите се обхождат спрмо височината на която се намират, като се започва от корена. Резултата от обхождането по ширина на примерното дърво е: 4, 3, 8, 1, 5, 16.

Обхождане по дълбочина – Има няколко начина за обхождане по дълбочина спрямо това, кога обработваме елемена и кога неговите наследници.

Ляво-Корен-Дясно – inorder tree walk – първо се обработва лявото поддърво, след това елемента и след това дясното поддърво. Пример: 1, 3, 4, 5, 8, 16. Елементите са показват в сортиран вид.

Корен-Ляво- Дясно – preorder tree walk – първо се обработва корена, след това лявото и дясното поддърво. Пример: 4, 3, 1, 8, 5, 16.

Операции над двоични дървета за търсене

Търсене на елемент по ключ

Пояснение: В програмната ми реализация всеки ноуд има ключ и стойност/допълнителни данни. Елементите се подреждат спрямо ключа си и за това той имплементира IComparable. Типа на данните може да бъде какъвто и да е обект. Задачата може да се реализира и като ноудовете имат само ключ.

Също така, за улеснение при реализиране на наякои операции над дървото, ноудовете имат допълнително поле, което сочи към родителя им. Коренът на дървото е единствения връх без родител, т.е. има родител равен на null.

Дървото ми не поддържа елементи с еднакви ключове. При опит за добавяне на елемент със същестуващ ключ се променя стойността на вече съсщестуващия елемент с тази на новия елемент.

Търсенето на елемен в двоично дърво за търсене става чрез binary search.  Функцията връща null, ако елемента не е намерен и елемета, ако е.

  1. Ако текущият елемент е равен на елемента, който търсим или е null (не същестува) => връщаме текущият елемент.
  2. Ако текущият елемент е по-малък от елемента, който търсим - извикваме търсещата функция за лявото поддървo. Иначе - извикваме търсещата функция за дясното поддърво.

 

Добавяне на елемент

При добавянето на елемент, първо търсим празно поддърво (null node), където може да добавим новия елемент.

При търсенето започваме от корена на дървото и поддържаме два указателя – към текущият елемент, на който сме и към елемента, от който сме дошли (родителя на текущия елемент), и променяме тези указатели, докато се движим надолу по дървото.

След като търсенето приключи: текущия елемент е null и на негово място ще бъде записан новия елемент, чиито родител е ноуда, от който сме дошли.  

При самото добавяне на елемета имаме няколко възможности:

  1. Родителя на текущия елемент е null. Единстеният възможен такъв връх е коренът на дървото и за това променяме корена на дървото да бъде новият елемент.
  2. Проверяваме ключа на елемета, който ще добавяме
    1. Ако е по-малък от ключа на елемента, от който идваме –> закачаме новия елемент като негов ляв наследник.
    2. Ако е по-голям от ключа  на елемента, от който идваме –> закачаме новия елемент като негов  десен наследник.
    3. Ако е равен на ключа на ключа на елемента, от който идваме –>  дървото ми не поддържа елементи с еднакви ключове и за това променят стоността на родителския елемент с тази на новия елемент. Друг варият е да се хврърли ексепшън.

 

Добавяне на елемент с ключ 5.

Изтриване на елемент

При изтриването на елементи използвам помощна  функция за местене на дадено поддъво, на мястото на друго поддърво. Тя се грижи за гранични случаи, като местене на празно дърво или местене на дърво на мястото на корена на дървото. При всяко местене и изтриване на елементи трябва да се внимава връзките между елеметните да запазят правилни.

При изтриване на елемент трябва да се запази свойстовото на двоичното дърво за търсене – елементите на лявото поддърво да са по-малки от родителя си и елементите на дясното поддърво да са по-големи от родителя си.

Имаме няколко възможни ситуации.

  1. Елемента  няма ляв наследник / няма ляв и десен наследник –> Заменяме елемента за изтриване с десния му наследник (null ако няма).

Изтриваме елемент 11, който няма ляв и десен наследник.

 

     2.   Елемента няма десен наследник -> Заменяме елемента за изтриване с левия му наследник.

Изтриваме елемент 11, който няма десен наследник.  Заменяме го с левият му наследник:

         a.  Правим левия наследник на родителя на ноуд 11 да бъде равен на десния наследник на ноуд 11.

         b.  Променяме родителя на ноуд 15 да е бъде равен на родителя на ноуд 11.

     3.  Елемента има ляв и десен наследник => Намираме най-малкият елемент, който е по-голям от ноуда за изтриване (най-левия елемент в дясното поддърво на ноуда за изтриване). С него заменяме елемента за изтриване, за да се запази свойството на двойчното дърво за търсене.

  1. Ако минималният елемент НЕ е директният десен наследик на ноуда за изтриване, трябва да преместим дясното поддърво на минималния елемент на мястото, на минималния елемент. Минималният емемен няма ляво поддърво и за това не се налага да правим нищо.

Местим минималния елемент на позицията на елемента за изтриване.

 

За по-подробно обяснение на материята може да прочетете:

  1. CLRS - Introduction to Algorithms - Chapter 12
  2. Наков – „Програмиране =++ Алгоритми“, Глава 2.2
  3. Sedgewick – Algorithms 4th ed -  Chapter 3.2

 

Моето решение: GitHub

Обяснение:

Създавам дженерик клас BST<TKey, TValue>, като ограничавам TKey да бъде IComparable, защото функциите за търсене, изтриване и добавяне изискват сравнение по ключ.

BST е съставен от елемети от клас TreeNode,  който съм вложил в BST, защото ноудовете нямат смисъл, когато не са част от дърво.  Също така, по този начин скривам вътрешното представяне на класа. Всеки ТreeNode  има ключ и стойност, и указатели към левия, и десния си наследник, както и към родителя си, защото така се улесняват операциите върху дървото.

При реализацията на публичните методи за добавяне, изтриване, търсене на елемент и изчистване на дървото съм спазил сигнатурата на методите от IDictionary итерфейса, но не го имплементирам.

За Equals  съществъват много начини за реализация. Аз съм сравнявам дали ключовете на две дървета съвпадат.

За да подпомогна реализацията на ToString и пропъртитата Keys и Values, съм направил медод InorderTreeWalk(TreeNode node, Action<TreeNode> action), където node е някакъв ноуд от дървото а action е „държавен“ делегат, който връща void. В ToString чрез ламбда функция добавям данните на текущият ноуд към стринг билдър.

За да подпомогна реализацията на Clone, подобно на ToString, съм напрвим метод PreorderTreeWalk(TreeNode node, Action<TreeNode> action). Като обхожраме елементите preorder и ги добавяме към ново дърво се получава дърво с идентична структура. Отново добавям елементите чрез ламбда функция.


от andon (439 точки)


0
Браво, за това с ламбда функциите не се бях сетил. Забравил си да имплементираш IEnumerable<>.

от georgi.ivanov (3261 точки)

0
Мм да, мерси. Ще го фиксна утре :)

от andon (439 точки)



1
Информация тук:
http://en.wikipedia.org/wiki/Binary_tree
Примерна имплементация тук:
http://hectorcorrea.com/blog/binary-tree-in-c-sharp

от hatrox (0 точки)


0
Само дето се иска Binary Search Tree, а не Binary Tree. http://en.wikipedia.org/wiki/Binary_search_tree

от NikolaNikolov (397 точки)


1

Решение - BST

При моята имплементация всички операции в дървото се извършват рекурсивно и методите на пръв поглед могат да изглеждат малко объркани. За обхождане използвам само DFS. TreeNodeEnum ми е нужен за интерфейса IEnumerable<V>.


от georgi.ivanov (3261 точки)


0
@Божидар Пенчев
Здравей, може би в старата презентация е била задача 5, но сега е задача 6. Моля те коригирай заглавието, за да не се объркваме.
Благодаря.
Edit. Teodor я промени вместо теб.
Поздрави



3

За любителите на по-интересните структури от данни, могат да видят имплементацията ми на AVL Tree - двойчно дърво, което се балансира:

http://azlatkov.wordpress.com/2013/03/10/avl-tree-in-c/ 
или ако не ви се четат обяснения направо:
https://github.com/zlatkov/Telerik/tree/master/C%23OOP/CommonTypeSystem/4.AVLTree

Поздрави. :)


от zlatkov (580 точки)


2

TreeNode

Binary Search Tree

Demo

за ToString() използвам StringBuilder, предаван по референция при всички рекурсивни извиквания и добавям ключа към него, същата е идеята и на Equals() само че този път по референция се предава bool. При енумератора ги добавям за по-лесно в списък, който пак е по референция и накрая връщам всичките елементи в него с yield return. Clone() е връх по връх, като тук съм променил малко реда, за да са им еднакви корените, че иначе няма да са еднакви, а резултантното дърво е пак с ref. И накрая хеш кода се получава много лесно като има foreach. 


от Rokata (397 точки)


0
В презентацията пише да използваме struct за BinarySearchTree и class за TreeNode. На мен ми се струва, че трябва да е обратното.Може ли някой да ми каже бъркам ли? Нали не е хубаво да слагаме логика в struct? А на мен ми се струва, че методите за добавяне, търсене и изтриване трябва да са именно там.

от linach (717 точки)


0
Абсолютно те подкрепям в разсъжденията - явно е объркано условието.

от stoyanov (2483 точки)


2

Решил съм задачата за имплементиране на “Binary Search Tree” с използването на балансирано дърво от вида: „Дърво на Андерсон“ (Andersson tree), което има сходни показатели, като тези на „Червено-Черните дървета“ (Red-Black trees). Пишат че е по-опростено и имплементира в опростен вид симетрично „Двоично Б дърво“ (Binary B-tree), но пак е малко странно че за всички методи се работи с рекурсия.

Дърветата на Андерсон (или АА-Дървета (AA-trees)) са измислени от Арне Андерсон (Arne Andersson) в своя публикация  “Balanced Search Trees Made Simple”.

Примерния код на C#

Тюториала и статията за самия алгоритъм

Моето решение

Тест

 


от stanev.plamen (1143 точки)


0

Някой може ли да удари едно рамо как да направя рекурсивното добавяне на елемент да работи, защото явно през пропъртитата за ляв и десен наследник не мога да предам референция - ето кода.


от lostm1nd (846 точки)


0
В AddRecursive() проверяваш дали root == null и ако да го присвояваш, ако не извикваш AddRecursion(). 1ят параметър на AddRecursion() го третираш като родителски възел, т.е. тестваш и евентуално присвояваш неговите Left/Right пропъртита.
if (current.Value <= number) ... не е добра идея, защото по дефиниция дървото не може да съдържа възли с еднакъв ключ. Ако намериш възел с ключ, който е равен на кандидата за добавяне, трябва да хвърлиш exception.

от kzhokham (102 точки)

0
Ако намериш възел с ключ, който е равен на кандидата за добавяне, можеш просто да смениш стойността му вместо да хвърляш exception - това си зависи от начина на имплементация според мен

от dzhenko (3893 точки)



0

Решениe и от мен: Click  smiley


от kzhokham (102 точки)


1

В условието на задачата има изискване да се добави и имплементира ICloneable интерфейсът за deep copy на дървото.

Поради добре подредената структура на BST това не е трудоемка работа, но аз реших да експериментирам с използване на сериализация, защото при по-сложни класове и при липса на достатъчно време това може да се окаже подходящо решение.

За целта направих следното:

1. Добавих атрибут [Serializable] пред всеки от двата класа BST и TreeNode.

2. Добавих следните директиви в началото на класа:

using System.Runtime.Serialization.Formatters.Binary;
using System.IO;

(избирам двоичен форматер, като алтернативата е XML форматер)

3. Методът за клониране използва MemoryStreаm и изглежда така (тъй като е кратък, поствам го тук директно):

    public object Clone()
    {
        MemoryStream ms = new MemoryStream();

        BinaryFormatter bf = new BinaryFormatter();

        bf.Serialize(ms, this);

        ms.Position = 0;

        object obj = bf.Deserialize(ms);

        ms.Close();

        return obj;
    }

Форматът изглежда много по-опростен, отколкото с използване на FileStream, но затова пък използването на FileStream позволява да си направим копие върху диска, лесно достъпно и "по-видимо", отколкото паметта. Това може да се види от лекцията на Ники Костов.


от ellapt (6303 точки)