DataStructures

Implementation of advanced data structures. Project contains K-d tree, AVL tree, HashSet and ExtendibleHashing structures. The project has been created as a part of course Algorithms and Data structures 2 (5II215) taught at Faculty of Management Science and Informatics, University of Žilina.

Structures

Class library containing implementation of aforementioned data structures. Individual structures can be obtained from this library through StructureFactory class.

using Structures;

class StructureExample
{
    static void Main(string[] args)
    {
        // Obtaining AVL tree from StructureFactory.
        var avlTree = StructureFactory.Instance.GetAvlTree<int>();
    }
}

AvlTree

Implementation of AVL tree. Objects stored at this structure must implement IComparable interface. Structure does not support duplicate keys and is ordered by the keys in ascending order. Time complexity of Search, Insert and Delete operations are O(log₂n). Finding minimum and maximum through Min and Max properties has the same time complexity as well. Range search time complexity is O(log₂n + m) where m is number of found elements.

KdTree

Implementation of K-d tree. This structure contains objects with multiple secondary (non-unique) keys. Objects stored at this structure must implement IKdComparable interface. Structure does not necessarily stores objects in ascending order due to multidimensionality. Time complexity of Search, Insert and Delete operations are O(log₂n). Range search time complexity is O(k * n^{1 - 1/k}) where k is number of K-d tree dimensions.

HashSet

Implementation of Hash table. Objects stored at the structure should override Equals and GetHashCode method if necessary. Search, Insert and Delete time complexities are O(1).

ExtendibleHashing

Implementation of Extendible hashing. Objects stored at the structure should override Equals and GetHashCode method if necessary. Objects stored in this structure must implement ISerializable interface. Purpose of this structure is to minimize number of file accesses during Search, Insert and Delete operations. File accesses during all these operations are constant.

StructureTests

XUnit test project used to test functionality of each of the structures.

SurveyApp

WPF application used to demonstrate functionality of the structures. It is a sample project consuming Structures class library.