RADIX TREES

Podatkovna struktura je način organizacije podatkov. Področje podatkovnih struktur obravnava enostavnejše strukture, kot so seznam, sklad, vrsta, tabela ter zahtevnejše, kot so drevesa, grafi, množice. V diplomskem delu se osredotočimo na posebno obliko dreves, ki jih imenujemo bazna drevesa. V prvem poglavju smo za boljše razumevanje nadaljnjih poglavij razložili pojem algoritma, pojem podatkovne strukture in pojem drevesa. Nadaljevali smo z razlago urejanja z radiksom, ki je motivacija za uvedbo baznih dreves. V tem poglavju razložimo osnove urejanja z radiksom ter opišemo in razložimo dva načina urejanja z radiksom. Oba načina razložimo še na podlagi primerov. Tretje poglavje posvetimo glavni temi našega diplomskega dela, kjer razložimo idejo baznih dreves. Naslednja tri poglavja posvetimo razlagi vsake od podvrst baznih dreves. Na podlagi teoretične razlage in praktičnega prikaza s primeri razložimo digitalno drevo, drevo trie in patricia drevo. Zadnje poglavje posvetimo razlagi delovanja algoritma, ki smo ga realizirali v programskem jeziku C++.Data structure is a way of organizing data. The field of data structures treats very simple structures such as lists, stacks, queues, arrays as well as more pretentious structures such as trees, graphs, sets. In this diploma thesis we focus on a special form of trees which are called radix trees. In the first chapter we explained the idea of algorithm, data structure and tree for a better understanding of the following chapters. We continued with the explanation of radix sort which is the motivation for introducing radix trees. In this chapter we explain the basics of radix sort and describe two ways of radix sort. Both ways are explained on the bases of examples. The third chapter is devoted to the main topic of our diploma thesis, where the idea of radix trees is explained. The next three chapters are devoted to the explanations of each sub-sort of radix trees. On the basis of theoretical explanation and the practical presentation with examples we explain the digital tree, trie and patricia tree. The last chapter is devoted to the explanation of the algorithm operation which was carried out in the C++ programming language