Aproksymacja Optymalnych Binarnych Drzew Poszukiwań

Binarne drzewo poszukiwań (BST), to jedna z podstawowych struktur danych. Służy do przechowywania posortowanych danych, w sposób pozwalający na wykonywanie zapytań w optymalnym czasie. Struktura drzewa jest następująca, każdy wierzchołek w swoim lewym poddrzewie ma wartości mniejsze, a w prawym poddrzewie wartości większe od własnej wartości. Zazwyczaj BST mają wysokość O(log n), co zezwala na wykonywanie podstawowych operacji w czasie O(log n). Zakładając, że wiemy, jak często każda wartość w drzewie jest wyszukiwana, możemy skonstruować drzewo operujące efektywniej. W problemie Optymalnego Binarnego Drzewa Poszukiwań na wejściu otrzymujemy rozkład prawdopodobieństwa wyszukania każdej wartości z naszego BST oraz każdego przedziału wartości, które nie należą do BST. Celem jest znalezienie drzewa, które minimalizuje oczekiwany czas wyszukiwania. W naszej pracy badamy problem aproksymacji Optymalnego Binarnego Drzewa Poszukiwań. Prezentujemy nowy algorytm ze współczynnikiem aproksymacji 3/2 o złożoności czasowej O(n log n). Dodatkowo prezentujemy częściowe wyniki z zakresu problemu (1+ε)-aproksymacji. Dowodzimy, że dla ciągów wejściowych z odpowiednio dużą entropią, aktualne algorytmy są już dostatecznie dobre. Dla ciągów z niską entropią pokazujemy, jak ta własność może być użyta w celu uzyskania dobrej aproksymacji.

The binary search tree (BST) is one of the most fundamental data structures. It is widely used to store ordered data, allowing for efficient updates and look-ups. A BST for a set of values is a binary tree, in which for every node it holds that each node in its left subtree holds a smaller value and each node in its right subtree holds a higher value. Usually we want the BST to be of O(log n) height to ensure O(log n) complexity of basic operations. However, if we knew how often each value in the BST is queried, we could create a tree that allows for sublogarithmic operations. In the Optimal Binary Search Tree problem, we are given probabilities of accessing each value in the BST and every interval between these values. The objective is to construct a tree that minimizes the expected access time. In this thesis, we study the approximation aspect of the OBST problem. We introduce a new O(n log n) time algorithm with approximation ratio 3/2. This algorithm also produces a tree with the same cost upper bound as the best previously known algorithms. Additionally, we give partial results for the (1+ε)-approximation problem. We show that for inputs with great enough entropy, the existing approximation algorithms are already good enough. For inputs with lower entropy we show how this property can be used to obtain a good approximation, if we had subquadratic algorithms for few other problems in this space.