Voltar

## Árvore Burkhard-Keller - Estrutura de dados

0 Curtidas
```/**
* Burkhard-Keller Tree
*
* Maintains a finite metric space with an integer-valued distance function.
* Supports insert() and getWithinDistance(k).
*
* TEMPLATE PARAMETERS:
*   T: element type
*   Distance: a function (or functor) from TxT to non-negative integers.
*       Must be a metric. Distance zero implies equality.
*
**/
#include
#include
using namespace std;
template
class BkTree
{
public:
BkTree() {
root_ = NULL;
size_ = 0;
}
~BkTree() {
if(root_) delete root_;
}
/** Does nothing if the tree already contains this element. **/
void insert(T item) {
if(!root_) {
size_ = 1;
root_ = new Node(item, -1);
return;
}

Node *t = root_;

while(true) {
int d = Distance(t->item, item);

if(!d) return;

Node *ch = t->firstChild;

while(ch) {
if(ch->distToParent == d) {
t = ch;
break;
}

ch = ch->nextSibling;
}

if(!ch) {
Node *newChild = new Node(item, d);
newChild->nextSibling = t->firstChild;
t->firstChild = newChild;
size_++;
break;
}
}
}
int size() const {
return size_;
}
bool empty() const {
return !size_;
}
int count(T item) const {
return getWithinDistance(item, 0);
}
/**
* Finds all elements within a distance of 'k' of 'center', inclusive.
* Fills 'result' and returns the number of elements found.
* Gives no guarantees about the order in which results are returned.
**/
int getWithinDistance(T center, int k, vector *result = NULL) const {
assert(k >= 0);

if(!root_) return 0;

int found = 0;
queue< Node* > q;
q.push(root_);

while(!q.empty()) {
Node *t = q.front();
q.pop();
int d = Distance(t->item, center);

if(d <= k) {
if(result) result->push_back(t->item);

found++;
}

Node *ch = t->firstChild;

while(ch) {
if(d - k <= ch->distToParent && ch->distToParent <= d + k)
q.push(ch);

ch = ch->nextSibling;
}
}

return found;
}
private:
struct Node {
T item;
int distToParent;
Node *firstChild;
Node *nextSibling;
Node(T x, int dist) {
item = x;
distToParent = dist;
firstChild = nextSibling = NULL;
}
~Node() {
if(firstChild) delete firstChild;

if(nextSibling) delete nextSibling;
}
};
Node *root_;
int size_;
};
//------------- TESTING --------------
#include
#include
int EditDistance(const string &s, const string &t)
{
int m = s.size();
int n = t.size();
vector< vector< int > > tab(m + 1, vector< int >(n + 1, 0));

for(int i = m - 1; i >= 0; i--) for(int j = n - 1; j >= 0; j--) {
if(s[i] == t[j]) tab[i][j] = tab[i + 1][j + 1];
else tab[i][j] = 1 + (tab[i + 1][j] ? tab[i][j] : tab[i][j + 1]);
}

return tab[0][0];
}
int main()
{
BkTree tree;
assert(tree.size() == 0);
assert(tree.empty());
tree.insert("boobs");
assert(tree.size() == 1);
assert(!tree.empty());
assert(tree.count("boobs"));
assert(!tree.count("books"));
assert(tree.getWithinDistance("boobs", 0) == 1);
assert(tree.getWithinDistance("boobs", 1) == 1);
assert(tree.getWithinDistance("books", 0) == 0);
assert(tree.getWithinDistance("books", 1) == 1);
tree.insert("books");
assert(tree.size() == 2);
assert(!tree.empty());
assert(tree.count("boobs"));
assert(tree.count("books"));
assert(!tree.count("boots"));
assert(tree.getWithinDistance("books", 0) == 1);
assert(tree.getWithinDistance("books", 1) == 2);
assert(tree.getWithinDistance("boots", 1) == 2);
assert(tree.getWithinDistance("boobs", 1) == 2);
vector< string > pool;
int n = 100;
int len = 10;

for(int i = 0; i < n; i++) {
string word;

while((int)word.size() < len) word += 'a' + rand() % 26;

pool.push_back(word);
}

vector< vector< int > > dist(n, vector< int >(n));

for(int i = 0; i < n; i++) for(int j = 0; j < n; j++)
if(i == j)
dist[i][j] = 0;
else
assert(dist[i][j] = EditDistance(pool[i], pool[j]));

BkTree< string, EditDistance > tree2;

for(int i = 0; i < n; i++) {
assert(tree2.size() == i);
assert(!tree2.count(pool[i]));
tree2.insert(pool[i]);
assert(tree2.count(pool[i]));

for(int d = 0; d <= len; d++) {
int ans = 0;

for(int j = 0; j <= i; j++) if(dist[i][j] <= d) ans++;

assert(tree2.getWithinDistance(pool[i], d) == ans);
}
}

assert(tree2.size() == n);
}

```