208 lines
10 KiB
BibTeX
208 lines
10 KiB
BibTeX
% The example bibliographical entries below were borrowed from the
|
||
% <https://www.ctan.org/pkg/biblatex-iso690> package documentation.
|
||
|
||
@ARTICLE{avl,
|
||
author = {Adelson-Velskij, Georgij and Landis, Evgenij},
|
||
year = {1962},
|
||
month = {01},
|
||
pages = {263-266},
|
||
title = {An algorithm for the organization of information},
|
||
volume = {146},
|
||
journal = {Doklady Akad. Nauk SSSR}
|
||
}
|
||
|
||
@ARTICLE{wavl,
|
||
author = {Haeupler, Bernhard and Sen, Siddhartha and Tarjan, Robert E.},
|
||
title = {Rank-Balanced Trees},
|
||
year = {2015},
|
||
issue_date = {June 2015},
|
||
publisher = {Association for Computing Machinery},
|
||
address = {New York, NY, USA},
|
||
volume = {11},
|
||
number = {4},
|
||
issn = {1549-6325},
|
||
url = {https://doi.org/10.1145/2689412},
|
||
doi = {10.1145/2689412},
|
||
abstract = {Since the invention of AVL trees in 1962, many kinds of binary search trees have been proposed. Notable are red-black trees, in which bottom-up rebalancing after an insertion or deletion takes O(1) amortized time and O(1) rotations worst-case. But the design space of balanced trees has not been fully explored. We continue the exploration. Our contributions are three: We systematically study the use of ranks and rank differences to define height-based balance in binary trees. Different invariants on rank differences yield AVL trees, red-black trees, and other kinds of balanced trees. By relaxing AVL trees, we obtain a new kind of balanced binary tree, the weak AVL tree (wavl tree), whose properties we develop. Bottom-up rebalancing after an insertion or deletion takes O(1) amortized time and at most two rotations, improving the three or more rotations per deletion needed in all other kinds of balanced trees of which we are aware. The height bound of a wavl tree degrades gracefully from that of an AVL tree as the number of deletions increases and is never worse than that of a red-black tree. Wavl trees also support top-down, fixed look-ahead rebalancing in O(1) amortized time. Finally, we use exponential potential functions to prove that in wavl trees rebalancing steps occur exponentially infrequently in rank. Thus, most of the rebalancing is at the bottom of the tree, which is crucial in concurrent applications and in those in which rotations take time that depends on the subtree size.},
|
||
journal = {ACM Trans. Algorithms},
|
||
month = {6},
|
||
articleno = {30},
|
||
numpages = {26},
|
||
keywords = {data structures, exponential potential function, red-black trees, AVL trees, search trees, Balanced binary trees, amortized complexity}
|
||
}
|
||
|
||
@ARTICLE{ravl,
|
||
author = {Sen, Siddhartha and Tarjan, Robert E. and Kim, David Hong Kyun},
|
||
title = {Deletion Without Rebalancing in Binary Search Trees},
|
||
year = {2016},
|
||
issue_date = {September 2016},
|
||
publisher = {Association for Computing Machinery},
|
||
address = {New York, NY, USA},
|
||
volume = {12},
|
||
number = {4},
|
||
issn = {1549-6325},
|
||
url = {https://doi.org/10.1145/2903142},
|
||
doi = {10.1145/2903142},
|
||
abstract = {We address the vexing issue of deletions in balanced trees. Rebalancing after a deletion is generally more complicated than rebalancing after an insertion. Textbooks neglect deletion rebalancing, and many B-tree--based database systems do not do it. We describe a relaxation of AVL trees in which rebalancing is done after insertions but not after deletions, yet worst-case access time remains logarithmic in the number of insertions. For any application of balanced trees in which the number of updates is polynomial in the tree size, our structure offers performance competitive with that of classical balanced trees. With the addition of periodic rebuilding, the performance of our structure is theoretically superior to that of many, if not all, classic balanced tree structures. Our structure needs lg lg m+ 1 bits of balance information per node, where m is the number of insertions and lg is the base-two logarithm, or lg lg n+ O(1) with periodic rebuilding, where n is the number of nodes. An insertion takes up to two rotations and O(1) amortized time, not counting the time to find the insertion position. This is the same as in standard AVL trees. Using an analysis that relies on an exponential potential function, we show that rebalancing steps occur with a frequency that is exponentially small in the height of the affected node. Our techniques apply to other types of balanced trees, notably B-trees, as we show in a companion article, and particularly red-black trees, which can be viewed as a special case of B-trees.},
|
||
journal = {ACM Trans. Algorithms},
|
||
month = {sep},
|
||
articleno = {57},
|
||
numpages = {31},
|
||
keywords = {Balanced trees, exponential potential function, amortized complexity, algorithm, data structure, database access methods}
|
||
}
|
||
|
||
@ARTICLE{hypothesis,
|
||
author = {MacIver, David R. and Hatfield-Dodds, Zac and {many other contributors}},
|
||
doi = {10.21105/joss.01891},
|
||
month = {11},
|
||
title = {{Hypothesis: A new approach to property-based testing}},
|
||
year = {2019}
|
||
}
|
||
|
||
@INPROCEEDINGS{rbtree,
|
||
author={Guibas, Leo J. and Sedgewick, Robert},
|
||
booktitle={19th Annual Symposium on Foundations of Computer Science (sfcs 1978)},
|
||
title={A dichromatic framework for balanced trees},
|
||
year={1978},
|
||
volume={},
|
||
number={},
|
||
pages={8-21},
|
||
doi={10.1109/SFCS.1978.3}
|
||
}
|
||
|
||
@ARTICLE{adams_1993,
|
||
title={Functional Pearls Efficient sets—a balancing act},
|
||
volume={3},
|
||
DOI={10.1017/S0956796800000885},
|
||
number={4},
|
||
journal={Journal of Functional Programming},
|
||
publisher={Cambridge University Press},
|
||
author={Adams, Stephen},
|
||
year={1993},
|
||
pages={553–561}
|
||
}
|
||
|
||
@INPROCEEDINGS{btree,
|
||
author = {Bayer, Rudolf and McCreight, Edward},
|
||
title = {Organization and Maintenance of Large Ordered Indices},
|
||
year = {1970},
|
||
isbn = {9781450379410},
|
||
publisher = {Association for Computing Machinery},
|
||
address = {New York, NY, USA},
|
||
url = {https://doi.org/10.1145/1734663.1734671},
|
||
doi = {10.1145/1734663.1734671},
|
||
abstract = {Organization and maintenance of an index for a dynamic random access file is considered. It is assumed that the index must be kept on some pseudo random access backup store like a disc or a drum. The index organization described allows retrieval, insertion, and deletion of keys in time proportional to logk I where I is the size of the index and k is a device dependent natural number such that the performance of the scheme becomes near optimal. Storage utilization is at least 50\% but generally much higher. The pages of the index are organized in a special data-structure, so-called B-trees. The scheme is analyzed, performance bounds are obtained, and a near optimal k is computed. Experiments have been performed with indices up to 100,000 keys. An index of size 15,000 (100,000) can be maintained with an average of 9 (at least 4) transactions per second on an IBM 360/44 with a 2311 disc.},
|
||
booktitle = {Proceedings of the 1970 ACM SIGFIDET (Now SIGMOD) Workshop on Data Description, Access and Control},
|
||
pages = {107–141},
|
||
numpages = {35},
|
||
keywords = {key deletion, paging, information retrieval, data structures, key insertion, random access files, dynamic index maintenance, key retrieval},
|
||
location = {Houston, Texas},
|
||
series = {SIGFIDET '70}
|
||
}
|
||
|
||
@BOOK{knuth1998art,
|
||
title={The Art of Computer Programming: Volume 3: Sorting and Searching},
|
||
author={Knuth, Donald E.},
|
||
isbn={9780321635785},
|
||
url={https://books.google.cz/books?id=cYULBAAAQBAJ},
|
||
year={1998},
|
||
publisher={Pearson Education}
|
||
}
|
||
|
||
@BOOK{cormen2009introduction,
|
||
author = {Cormen, Thomas},
|
||
title = {Introduction to algorithms},
|
||
publisher = {MIT Press},
|
||
year = {2009},
|
||
address = {Cambridge, Mass},
|
||
isbn = {9780262033848}
|
||
}
|
||
|
||
@BOOK{labyrint,
|
||
author = {Mareš, Martin and Valla, Tomáš},
|
||
title = {Průvodce labyrintem algoritmů},
|
||
publisher = {CZ.NIC, z.s.p.o.},
|
||
year = {2017},
|
||
isbn = {9788088168225},
|
||
url = {http://pruvodce.ucw.cz}
|
||
}
|
||
|
||
@ONLINE{ib002,
|
||
title = {Algoritmy a datové struktury I},
|
||
url = {https://is.muni.cz/predmet/fi/jaro2022/IB002},
|
||
urldate = {2022-05-01},
|
||
location = {Brno},
|
||
langid = {czech}
|
||
}
|
||
|
||
@ONLINE{ib111,
|
||
title = {Základy programování},
|
||
url = {https://is.muni.cz/predmet/fi/podzim2021/IB111},
|
||
urldate = {2022-05-01},
|
||
location = {Brno},
|
||
langid = {czech}
|
||
}
|
||
|
||
@ONLINE{llrb,
|
||
author = {Sedgewick, Robert},
|
||
title = {Left-leaning Red-Black Trees},
|
||
year = {2008},
|
||
url = {https://sedgewick.io/wp-content/uploads/2022/03/2008-09LLRB.pdf},
|
||
urldate = {2022-05-10}
|
||
}
|
||
|
||
@SOFTWARE{llvm,
|
||
author = {{LLVM Project}},
|
||
title = {\texttt{\_\_tree}},
|
||
url = {https://github.com/llvm/llvm-project/blob/main/libcxx/include/__tree},
|
||
version = {commit \texttt{990ea39}},
|
||
date = {2022-05-02},
|
||
}
|
||
|
||
@SOFTWARE{jdk,
|
||
author = {{Oracle and/or its affiliates}},
|
||
title = {\texttt{TreeMap.java}},
|
||
url = {https://github.com/openjdk/jdk/blob/master/src/java.base/share/classes/java/util/TreeMap.java},
|
||
version = {commit \texttt{fb469fb}},
|
||
date = {2022-05-02},
|
||
}
|
||
|
||
@SOFTWARE{csharp,
|
||
author = {{.NET Foundation and Contributors}},
|
||
title = {\texttt{SortedSet.cs}},
|
||
url = {https://github.com/dotnet/runtime/blob/main/src/libraries/System.Collections/src/System/Collections/Generic/SortedSet.cs},
|
||
version = {commit \texttt{215b39a}},
|
||
date = {2022-05-02},
|
||
}
|
||
|
||
@SOFTWARE{agda,
|
||
author = {Daggitt, Matthew and Allais, Guillaume},
|
||
title = {\texttt{AVL.agda}},
|
||
url = {https://github.com/agda/agda-stdlib/blob/master/src/Data/Tree/AVL.agda},
|
||
version = {commit \texttt{d0841d1}},
|
||
date = {2022-05-02},
|
||
}
|
||
|
||
@SOFTWARE{ocaml,
|
||
author = {{Institut National de Recherche en Informatique et en Automatique}},
|
||
title = {\texttt{set.ml}},
|
||
url = {https://github.com/ocaml/ocaml/blob/trunk/stdlib/set.ml},
|
||
version = {commit \texttt{f52fdc2}},
|
||
date = {2022-05-02},
|
||
}
|
||
|
||
@SOFTWARE{coq,
|
||
author = {{INRIA, CNRS and contributors}},
|
||
title = {\texttt{MSetAVL.v}},
|
||
url = {https://github.com/coq/coq/blob/master/theories/MSets/MSetAVL.v},
|
||
version = {commit \texttt{c1ddf13}},
|
||
date = {2022-05-02},
|
||
}
|
||
|
||
@SOFTWARE{rust,
|
||
author = {{LLVM Project}},
|
||
title = {\texttt{\_\_tree}},
|
||
url = {https://github.com/rust-lang/rust/blob/master/library/alloc/src/collections/btree/map.rs},
|
||
version = {commit \texttt{9805437}},
|
||
date = {2022-05-02},
|
||
}
|