Форум программистов, компьютерный форум CyberForum.ru
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 15, средняя оценка - 4.87
TheAthlete
153 / 153 / 13
Регистрация: 31.08.2010
Сообщений: 535
#1

Англо-русского словарь методом дерева бинарного поиска - C++

20.04.2011, 17:27. Просмотров 2013. Ответов 2
Метки нет (Все метки)

Здравствуйте!
Есть задача: реализовать англо-русский словарь с помощью бинарного дерева поиска. Решаю эту задачу на примере книги "Алгоритмы на С++ Роберт Седжвик".
Часть уже реализовал:

Item.h - АТД (абстрактный тип данных) элемента, содержит ключ (Key) - английское слово, соответствующее ему русское слово (item) и счетчик (количество обращений к ключу)

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#ifndef ITEM_H
#define ITEM_H
 
#include <iostream>
#include <string>
 
typedef std::string Key;
 
class Item
{
    friend std::ostream &operator<<(std::ostream &os, const Item &x);
    friend std::istream &operator>>(std::istream &in, Item &x);
    friend bool operator==(const Item &lhs, const Item &rhs);
    friend bool operator<(const Item &lhs, const Item &rhs);
public:
    Item(const size_t c = 0) : Count(c) {}
    Item(const Key &itsKeyval, const std::string &itsInfo, const size_t c = 0) : keyval(itsKeyval), info(itsInfo), Count(c) {}
    ~Item() {}
 
    Key key()           const { Count++; return keyval; }
    std::string item()  const { return info; }
    bool null()         const { return keyval.empty(); }
    int count()         const { return Count; }
    
    bool scan(const Key &itsKeyval, const std::string &itsInfo, const size_t c);
    void show(std::ostream &os = std::cout) { os << keyval << " " << info << " " << Count << std::endl; }
 
private:
    Key keyval;
    std::string info;
    mutable size_t Count; // позволяет изменять переменную даже в константной функции-члене
};
 
#endif
Item.cpp

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include "Item.h"
#include <iostream>
 
using std::istream;
using std::ostream;
using std::string;
 
bool Item::scan(const Key &itsKeyval, const std::string &itsInfo, const size_t c) {
    Count = c;
    keyval = itsKeyval;
    info = itsInfo;
    return !keyval.empty() && !info.empty();
}
 
ostream &operator<<(ostream &os, const Item &x) {
    os << x.keyval << " " << x.info << " " << x.Count;
    return os;
}
 
istream &operator>>(istream &in, Item &x) {
    in >> x.keyval >> x.info >> x.Count;
    if (!in) x = Item(); // ввод неудачен: вернуть объект в стандартное состояние
    return in;
}
 
bool operator==(const Item &lhs, const Item &rhs) {
    return lhs.keyval == rhs.keyval;
}
 
bool operator<(const Item &lhs, const Item &rhs) {
    for(string::size_type ix1 = 0, ix2 = 0; ix1 != lhs.keyval.size() && ix2 != rhs.keyval.size(); ++ix1, ++ix2) {
        return lhs.keyval[ix1] < rhs.keyval[ix2];
    }
}
ST.h - Таблица символов на основе дерева бинарного поиска

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
#ifndef ST_H
#define ST_H
 
#include <iostream>
 
template<typename Item, typename Key>
class ST
{
public:
    ST() : head(0) {}
    ~ST() {}
 
    Item search(Key v) { return searchR(head, v); }
    void insert(Item x) { insertR(head, x); }
    void show(std::ostream &os) { showR(head, os); }
    void remove(Item x) { removeR(head, x.key()); }
    
private:
    struct node {
        Item item;
        node *l, *r;
        node(Item x) : item(x), l(0), r(0) {}
    };
    
    typedef node *link;
    
    link head;
    Item nullItem;
 
    Item searchR(link h, Key v) {
        if (h == 0) return nullItem;
 
        Key t = h->item.key();
 
        if (v == t) 
            return h->item;
 
        if (v < t)
            return searchR(h->l, v);
        else
            return searchR(h->r, v);
    }
 
    void insertR(link &h, Item x) {
        if (h == 0) {
            h = new node(x);
            return;
        }
        if (x.key() < h->item.key())
            insertR(h->l, x);
        else
            insertR(h->r, x);
    }
 
    void showR(link h, std::ostream &os) {
        if (h == 0) return;
        showR(h->l, os);
        h->item.show(os);
        showR(h->r, os);
    }
 
    // Ротации в BST-деревьях
    void rotR(link &h) {
        link x = h->l;
        h->l = x->r;
        x->r = h;
        h = x;
    }
    
    void rotL(link &h) {
        link x = h->r;
        h->r = x->l;
        x->l = h;
        h = x;
    }
 
    // Разбиение BST-дерева
    void partR(link &h, int k) {
        int t = (h->l == 0) ? 0 : h->l->N;
        if (t > k) {
            partR(h->l, k);
            rotR(h);
        }
        if (t > k) {
            partR(h->r, k - t - 1);
            rotL(h);
        }
    }
 
    link joinLR(link a, link b) {
        if (b == 0) return a;
        partR(b, 0);
        b->l = a;
        return b;
    }
 
    void removeR(link &h, Key v) {
        if (h == 0) return;
        Key w = h->item.key();
        if (v < w) removeR(h->l, v);
        if (w < v) removeR(h->r, v);
        if (v == w) {
            link t = h;
            h = joinLR(h->l, h->r);
            delete t;
        }
    }
};
 
#endif
Внимание вопрос: при реализации разбиения BST-дерева (другое названиие бинарного дерева поиска) (метод Item partR(link &h, int k)), предполагается, что каждый узел дерева содержит размер своего поддерева (в данном методе это элемент h->l->N)

Я так полагаю, что необходимо добавить элемент N в структуру node:

C++
1
2
3
4
5
6
struct node {
        Item item;
        node *l, *r;
                      int N;
        node(Item x) : item(x), l(0), r(0), N(0) {}
    };
Только не пойму никак как определить размер поддерева для узла и тем самым записать это значение в N.

Зарание спасибо!
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
20.04.2011, 17:27
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Англо-русского словарь методом дерева бинарного поиска (C++):

Англо-русский словарь построен в виде двоичного дерева в программе с++ - C++
Англо-русский словарь построен в виде двоичного дерева. Каждая компонента содержит английское слово, соответствующее ему русское слово и...

Словарь на основе бинарного дерева - C++
Объясните, пожалуйста, что делает программа в функциях push и как осуществляется поиск, не совсем понимаю, для чего нужны l,r. Получается ,...

Распечатка бинарного дерева поиска - C++
Много где висит функция void print(int deep, ptree p) { if(p) { print(deep + 1, p-&gt;l); for ( int i = 0; i &lt; deep; i ++...

Итератор дерева бинарного поиска - C++
Если у нас в качестве коллекции выступают вектора, очереди, стеки и т.п. то там вроде бы всё понятно инкремент, декремент итератора...

Создание бинарного дерева поиска - C++
Людииииии помогите пож-таааа.....Нужно создать бинарное дерево поиска, считывая элементы из текст файла.. Очень нужноооо:( кто нибудь:(:(...

Реализация бинарного дерева поиска - C++
Не выводит значения узлов деревьев, как я понял происходит утечка памяти, но я не пойму, что нужно сделать. Программа ошибку не выдаёт....

2
volovzi
267 / 169 / 8
Регистрация: 14.03.2010
Сообщений: 501
21.04.2011, 02:38 #2
TheAthlete, глубина поддерева в текущем узле — это максимальная из глубин поддеревьев этого узла + 1. Если поддерева нет, то есть указатель нулевой, то и глубина этого поддерева считается нулевой.
Соответственно, устанавливается эта глубина при каждом изменении в структуре дерева. Это дело нужно отслеживать и правильно обрабатывать.
0
Nata267
0 / 0 / 0
Регистрация: 01.06.2014
Сообщений: 1
01.06.2014, 15:25 #3
Написать рекурсивную функцию, которая устанавливает значение счетчика для узла = сумма счетчиков левого и правого узла + 1 и вызывать ее когда узел меняет местоположение. В частности вызывать ее в методах rotR, rotL для обоих узлов
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
01.06.2014, 15:25
Привет! Вот еще темы с ответами:

Реализация бинарного дерева поиска - C++
Задача: Реализация бинарного дерева поиска Компилируется нормально, а при запуске выбивает ошибку : &quot;Необработанное исключение по адресу...

Вычисление высоты бинарного дерева поиска на С++ - C++
Никак не могу вывести нормально высоту дерева, уже второй день маюсь, подскажите пожалуйста, в чем проблема ? Например : Высоту...

Удаления узла из бинарного дерева поиска - C++
Уже довольно много времени убил на эту задачу, теорию понимаю, на практике реализовать никак не получается. Помогите пожалуйста написать...

Итератор для бинарного дерева поиска. - C++
Господа, нужен совет знатоков. Бинарное дерево поиска представлено следующей структурой. template &lt;typename ValueType&gt; struct Node {...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
3
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru