Binary Search Tree Implementation in C++ STL?
Do you know, please, if C++ STL contains a Binary Search Tree (BST) implementation, or if I should construct my own BST object? In case STL conains no implementation of BST, are there any libraries available? My goal is to be able to find the desired record as quickly as possible: I have a list of records (it should not be more few thousands.), and I do a per-frame (its a computer game) search in that list. I use unsigned int as an identifier of the record of my interest. Whatever way is the fastest will work best for me.
@Bunkai.Satori: well a BST could work for that, however in the worst case you would be looking at O(n) instead of O(log n) for retrievals (that is, if the tree is completely unbalanced). For what you want std::map or std::set would probably work best (the former if you want to store a key and a value it points to or the latter if you just care about storing keys).
@Bunkai sure thing. Let me offer you a better tip (from someone with a dozen games under his belt) : Don’t focus on the speed of the game loop right now. Focus on getting your game playable in a demo state. Little things like «I need a better performing set than this» is an easy thing to fix. Hell, you can use a vector at this stage and you’re still fine. Don’t let something like «I need this performance boost» stop you from moving forward with your game!
@Bunkai: And that’s exactly why you should ask about your goals and not the step, so your horizon can expand. 🙂
4 Answers 4
What you need is a way to look up some data given a key. With the key being an unsigned int , this gives you several possibilities. Of course, you could use a std::map :
typedef std::map my_records; However, there’s other possibilities as well. For example, it’s quite likely that a hash map would be even faster than a binary tree. Hash maps are called unordered_map in C++, and are a part of the C++11 standard, likely already supported by your compiler/std lib (check your compiler version and documentation). They were first available in C++TR1 ( std::tr1::unordered_map )
If your keys are rather closely distributed, you might even use a simple array and use the key as an index. When it comes to raw speed, nothing would beat indexing into an array. OTOH, if your key distribution is too random, you’d be wasting a lot of space.
If you store your records as pointers, moving them around is cheap, and an alternative might be to keep your data sorted by key in a vector:
typedef std::vector < std::pair> my_records; Due to its better data locality, which presumably plays nice with processor cache, a simple std::vector often performs better than other data structures which theoretically should have an advantage. Its weak spot is inserting into/removing from the middle. However, in this case, on a 32bit system, this would require moving entries of 2*32bit POD around, which your implementation will likely perform by calling CPU intrinsics for memory move.
Источник
Бинарное дерево с stl
БлогNot. Как сделать бинарное дерево средствами STL
Как сделать бинарное дерево средствами STL
В библиотеке шаблонов STL не предусмотрены отдельные контейнеры для деревьев. С другой стороны, коль скоро там существуют map и set , можно использовать, например, их.
А можно обойтись и простым вектором, как сделано в прилагаемом коде — ведь «дерево» — всего лишь логический способ организации данных.
Наше дерево состоит просто из целых чисел, в левое поддерево добавляются узлы, меньшие либо равные узла-родителя, а в правое — те, что больше.
Я не заморачивался «визуальным» представлением дерева в консоли, но все нужные обходы реализовал. Перед обходами дерево выводится в «списочном» виде, который показывает, какие потомки есть у какого элемента, если потомка нет, для него хранится и выводится значение -1 .
Всего существует 3 основных способа обхода двоичного дерева — прямой, симметричный (поперечный) и обратный, наверное, это проще изобразить, чем описать словами:
Прямой обход двоичного дерева
Симметричный обход двоичного дерева
Обратный обход двоичного дерева
В программу «зашито» для теста такое вот незамысловатое дерево:
Тестовое двоичное дерево
Вот полный исходник демо-программки, проверена в Visual Studio 2010 Express.
#include #include using namespace std; struct node < //структура для "дерева чисел" unsigned int data; int left; int right; >; void makeNode (vector &v1, int data) < //создать узел, не добавляя struct node b1 = < data, -1, -1 >; v1.push_back(b1); > void setLeftNode (vector &v1, int current, int data) < //поставить узел влево unsigned int leftIndex = v1.size(); v1[current].left = leftIndex; makeNode (v1, data); >void setRightNode (vector &v1, int current, int data) < //поставить узел вправо unsigned int rightIndex = v1.size(); v1[current].right = rightIndex; makeNode (v1, data); >int insertNode (vector &v1, int data) < //вставить узел if (v1.size() == 0) return -1; //сначала создать хотя бы 1 узел через makeNode unsigned int currentIndex = 0; while ( currentIndex < v1.size() ) < if (data else currentIndex = v1[currentIndex].left; > else < if (v1[currentIndex].right == -1) < setRightNode (v1, currentIndex, data); return 1; >else currentIndex = v1[currentIndex].right; > > return 0; > void preOrderTraversing(vector &v1, unsigned int index) < //прямой обход cout void inOrderTraversing(vector &v1, unsigned int index) < //симметричный обход if (v1[index].left != -1) inOrderTraversing (v1,v1[index].left ); cout void postOrderTraversing(vector &v1, unsigned int index) < //обратный обход if (v1[index].left != -1) postOrderTraversing(v1,v1[index].left ); if (v1[index].right != -1) postOrderTraversing(v1, v1[index].right); cout int main () < vector v1; makeNode(v1, 5); int order[] = < 3, 7, 1, 4, 6, 8 >; //порядок добавления узлов для теста int n = sizeof(order)/sizeof(int); //количество добавляемых узлов for (int i=0; i
Результат выполнения программы:
Tree is: 0) data=5 leftIndex=1 rightIndex=2 1) data=3 leftIndex=3 rightIndex=4 2) data=7 leftIndex=5 rightIndex=6 3) data=1 leftIndex=-1 rightIndex=-1 4) data=4 leftIndex=-1 rightIndex=-1 5) data=6 leftIndex=-1 rightIndex=-1 6) data=8 leftIndex=-1 rightIndex=-1 pre-order traversing: 5 3 1 4 7 6 8 in-order traversing: 1 3 4 5 6 7 8 post-order traversing: 1 4 3 6 8 7 5
13.05.2016, 14:45 [8345 просмотров]
Источник
STL Бинарные деревья с++
Добрый вечер.
Хочу узнать подробно о бинарных деревьях в STL.
После поиска по интернету наткнулся на :
Где сказано что в STL не реализованы бинарные деревья.
Дальнейший поиск не дал особо никаких результатов.
Знаю что в STL есть контейнер (Multi)Set и (Multi)Map которые по описанию являются бинарными деревьями.
Пожалуйста, объясните что к чему.
Бинарные деревья
Здравствуйте господа. Очень нуждаюсь в вашей помощи по бинарным деревьям. Собственно, имеется.
бинарные деревья
Вершина двоичного дерева содержит указатель на строку и указатели на правое и левое поддеревья.
Бинарные деревья
Очень нужна помощь, вообще деревья не понимаю. ( Вершина дерева содержит указатель на строку и N.
бинарные деревья
Здравствуйте! Помогите пожалуйста доделать задачу на бинарные деревья. Язык только начали.
Не являются бинарными деревьями, а используют бинарные деревья для реализации своей функциональности. Внутри они могут быть бинарными деревьями (IB), но наружу этого интерфейса не выдают.
#include int main() { std::mapchar, int> m; } 
В STL нет бинарных деревьев.
Если структуры данных, которые основаны на бинарных деревьях, хоть это и не является обязательным фактором и не прописано в стандарте.
При этом там, как правило, самобалансирующиеся деревья (обычно используют К/Ч деревья), а это частный случай бинарных.
Добавлено через 4 минуты
Как пример (не самой лучшей) реализации
Деревья
Функцию для освобождения памяти надо добавить + по хорошему всё это в класс/шаблон класса запихать.
Но, наверное, новичкам будет проще с таким кодом работать т.к. писал его тот же новичок (я), лет 6 назад.
Источник
Деревья в STL
В STL конкретная реализация бинарного дерева представлена структурой set , поддерживающей упорядоченное множество уникальных элементов.
#Основные операции
Структуру set можно объявить от любого типа, для которого реализован оператор сравнения — в частности, для пар и тюплов он реализован автоматически как лексикографическая сортировка.
Так как set реализован как сбалансированное двоичное дерево поиска — а конкретно как красно-черное дерево — все операции с его элементами работают за $O(\log n)$.
#Итераторы
Также set , как и все контейнеры STL, поддерживает итераторы.
Начало set (наименьший элемент) можно получить через .begin() , конец — через .end() . Обратите внимание, что .end() , как и все итераторы, указывает на конец полуинтервала — то есть на несуществующий элемент, идущий после последнего.
= 1 2 Инкремент и декремент итераторов работает за логарифмические время.
#Связанные структуры
В STL есть несколько структур со схожей функциональностью:
- map ассоциирует с ключами значения и позволяет получать их как из бесконечных массивов: m[x] = y .
- multiset поддерживает дубликаты элементов. .count(x) у него возвращает количество элементов с заданным ключом, а не просто 0 или 1. Его можно реализовать как map , в котором в качестве значений хранятся количества элементов.
- multimap возвращает по ключу много различных значений вместо одного и позволяет итерироваться по ним (то же самое, что использовать). Его можно реализовать как map> .
Также у всех этих контейнеров есть аналоги, работающие на хеш-таблицах вместо деревьев: unordered_set , unordered_map , unordered_multiset и unordered_multimap . В них поиск, удаление и вставка в среднем работают за константное время, но нет lower_bound и упорядоченного итерирования.
Источник