Simple view
Full metadata view
Authors
Statistics
Implementacja drzew binarnych w języku Python
Python implementation of binary trees
Python implementation of selected binary trees is presented. Basic operations supported by binary search trees are described: insertion of a node, deletion of a node, searching for a specific key, finding minimum or maximum node, finding the successor or the predecessor of a current node. Main tree traversal methods are shown: inorder, preorder, postorder, level-order.Binary search trees are basic structures used to implement dynamic sets of items that allow finding an item by its key. Searching is efficient only for balanced trees but for real data a tree may become unbalanced. That is why three modified kinds of trees are also shown. Red-black trees and AVL trees use an additional node attribute to ensure that trees remain approximately balanced. Splay trees improve access to frequently used nodes, they are placed near the root of the tree.All source code has been covered by unit test scripts.
binary search tree, red-black tree, AVL tree, splay tree, DSW algorithm, tree rotations, tree traversal
W pracy przedstawiono implementację w języku Python wybranych rodzajów drzew binarnych. Opisano podstawowe operacje na binarnych drzewach poszukiwań, takie jak dodawanie nowego węzła, usuwanie węzła, wyszukiwanie elementu o danym kluczu, wyszukiwanie elementu o największym lub najmniejszym kluczu, wyszukiwanie następnika lub poprzednika danego elementu. Pokazano najważniejsze metody przechodzenia przez drzewo: inorder, preorder, postorder, poziomami.Binarne drzewa poszukiwań są podstawową strukturą używaną do zaimplementowania zbiorów dynamicznych, których elementy mają być wyszukiwane przez swój klucz. Operacje wyszukiwania są wydajne dla drzew zrównoważonych, ale nie zawsze tak musi być. Z tego powodu w pracy przedstawiono zmodyfikowane drzewa, z usprawnieniami poprawiającymi wydajność podstawowych operacji. Drzewa czerwono-czarne i drzewa AVL utrzymują się w postaci w przybliżeniu zrównoważonej dzięki dodatkowemu atrybutowi dołączonemu do węzła.Drzewa splay natomiast poprawiają dostęp do najczęściej używanych elementów przez przemieszczenie ich bliżej korzenia.W pracy został również zaprezentowany algorytm DSW, który każde binarne drzewo poszukiwań wydajnie sprowadza do postaci zrównoważonej. Dla czterech wymienionych rodzajów drzew przygotowano kod zarówno w podejściu obiektowym (hierarchie klas drzewowych), jak i w podejściu z funkcjami (zestawy funkcji przypominających pseudokod). Cały kod został pokryty testami jednostkowymi, dodano także testy porównujące zachowanie różnych rodzajów drzew.
binarne drzewo poszukiwań, drzewo czerwono-czarne, drzewo AVL, drzewo splay, algorytm DSW, rotacje drzewa, przechodzenie drzewa
| dc.abstract.en | binarne drzewo poszukiwań, drzewo czerwono-czarne, drzewo AVL, drzewo splay, algorytm DSW, rotacje drzewa, przechodzenie drzewa | pl |
| dc.abstract.pl | W pracy przedstawiono implementację w języku Python wybranych rodzajów drzew binarnych. Opisano podstawowe operacje na binarnych drzewach poszukiwań, takie jak dodawanie nowego węzła, usuwanie węzła, wyszukiwanie elementu o danym kluczu, wyszukiwanie elementu o największym lub najmniejszym kluczu, wyszukiwanie następnika lub poprzednika danego elementu. Pokazano najważniejsze metody przechodzenia przez drzewo: inorder, preorder, postorder, poziomami.Binarne drzewa poszukiwań są podstawową strukturą używaną do zaimplementowania zbiorów dynamicznych, których elementy mają być wyszukiwane przez swój klucz. Operacje wyszukiwania są wydajne dla drzew zrównoważonych, ale nie zawsze tak musi być. Z tego powodu w pracy przedstawiono zmodyfikowane drzewa, z usprawnieniami poprawiającymi wydajność podstawowych operacji. Drzewa czerwono-czarne i drzewa AVL utrzymują się w postaci w przybliżeniu zrównoważonej dzięki dodatkowemu atrybutowi dołączonemu do węzła.Drzewa splay natomiast poprawiają dostęp do najczęściej używanych elementów przez przemieszczenie ich bliżej korzenia.W pracy został również zaprezentowany algorytm DSW, który każde binarne drzewo poszukiwań wydajnie sprowadza do postaci zrównoważonej. Dla czterech wymienionych rodzajów drzew przygotowano kod zarówno w podejściu obiektowym (hierarchie klas drzewowych), jak i w podejściu z funkcjami (zestawy funkcji przypominających pseudokod). Cały kod został pokryty testami jednostkowymi, dodano także testy porównujące zachowanie różnych rodzajów drzew. | pl |
| dc.affiliation | Wydział Fizyki, Astronomii i Informatyki Stosowanej | pl |
| dc.area | obszar nauk ścisłych | pl |
| dc.contributor.advisor | Kapanowski, Andrzej - 100452 | pl |
| dc.contributor.author | Matusiewicz, Ewelina | pl |
| dc.contributor.departmentbycode | UJK/WFAIS | pl |
| dc.contributor.reviewer | Kapanowski, Andrzej - 100452 | pl |
| dc.contributor.reviewer | Marcinek, Roman - 100088 | pl |
| dc.date.accessioned | 2020-07-27T12:00:19Z | |
| dc.date.available | 2020-07-27T12:00:19Z | |
| dc.date.submitted | 2017-10-24 | pl |
| dc.fieldofstudy | informatyka stosowana | pl |
| dc.identifier.apd | diploma-119461-129685 | pl |
| dc.identifier.project | APD / O | pl |
| dc.identifier.uri | https://ruj.uj.edu.pl/xmlui/handle/item/224453 | |
| dc.language | pol | pl |
| dc.subject.en | binary search tree, red-black tree, AVL tree, splay tree, DSW algorithm, tree rotations, tree traversal | pl |
| dc.subject.pl | Python implementation of selected binary trees is presented. Basic operations supported by binary search trees are described: insertion of a node, deletion of a node, searching for a specific key, finding minimum or maximum node, finding the successor or the predecessor of a current node. Main tree traversal methods are shown: inorder, preorder, postorder, level-order.Binary search trees are basic structures used to implement dynamic sets of items that allow finding an item by its key. Searching is efficient only for balanced trees but for real data a tree may become unbalanced. That is why three modified kinds of trees are also shown. Red-black trees and AVL trees use an additional node attribute to ensure that trees remain approximately balanced. Splay trees improve access to frequently used nodes, they are placed near the root of the tree.All source code has been covered by unit test scripts. | pl |
| dc.title | Implementacja drzew binarnych w języku Python | pl |
| dc.title.alternative | Python implementation of binary trees | pl |
| dc.type | master | pl |
| dspace.entity.type | Publication |