dc.contributor.author | Li, Mengdu | |
dc.date.accessioned | 2016-05-04T12:08:07Z | |
dc.date.available | 2016-05-04T12:08:07Z | |
dc.date.issued | 2016-05-04T12:08:07Z | |
dc.identifier.uri | http://hdl.handle.net/10222/71623 | |
dc.description.abstract | We present a provably linearizable and lock-free relaxed AVL tree called the non- blocking ravl tree. At any time, the height of a non-blocking ravl tree is bounded by logφ(2m) + c, where φ is the golden ratio, m is the total number of successful INSERT operations performed so far and c is the number of active concurrent processes performing INSERT operations at this time. The most signi cant feature of the non-blocking ravl tree is that it does not rebalance itself after DELETE operations. Compared to other self-balancing Binary Search Trees (BSTs), which typically intro- duce a large number of rebalancing cases after DELETE operations, the non-blocking ravl tree has much fewer rebalancing cases, which makes it much simpler to imple- ment in practice. Our experimental studies show that our solution is potentially the best candidate for many real-world applications. | en_US |
dc.language.iso | en | en_US |
dc.subject | concurrent data structure | en_US |
dc.subject | non-blocking | en_US |
dc.subject | self-balancing binary search tree | en_US |
dc.subject | relaxed AVL tree | en_US |
dc.subject | amortized complexity | en_US |
dc.title | Deletion Without Rebalancing in Non-Blocking Self-Balancing Binary Search Trees | en_US |
dc.date.defence | 2016-04-29 | |
dc.contributor.department | Faculty of Computer Science | en_US |
dc.contributor.degree | Master of Computer Science | en_US |
dc.contributor.external-examiner | n/a | en_US |
dc.contributor.graduate-coordinator | Norbert Zeh | en_US |
dc.contributor.thesis-reader | Andrew Rau-Chaplin | en_US |
dc.contributor.thesis-reader | Alex Brodsky | en_US |
dc.contributor.thesis-supervisor | Meng He | en_US |
dc.contributor.ethics-approval | Not Applicable | en_US |
dc.contributor.manuscripts | Not Applicable | en_US |
dc.contributor.copyright-release | Not Applicable | en_US |