Имеет ли Cocoa Touch структуру данных дерева поиска?

Я изучал это в Google и читал запись Collections в документации SDK и ничего не обнаруживал. Есть ли реализация BST (любой из ее вариантов), доступная из коробки с iOS SDK?

Кажется странным, что что-то настолько базовое будет отсутствовать на крупной платформе разработки. Является ли их реализация хэши только волшебной? Или разработчики полагают, что никто не собирается вставлять/удалять вещи, у которых есть заказ?

На данный момент я могу использовать NSSet, поскольку, как я знаю, большинство из нас (включая меня) не пишут ничего с тоннами вычислений на iOS, которые нуждаются в гарантированном времени доступа, но все равно грызет меня.

Ответ 1

CFBinaryHeap выглядит довольно многообещающим и полезным, но это может быть не совсем то, что вы хотите, поскольку оно не является бинарным деревом поиска, а heap. Они похожи, но не одинаковы, поэтому я чувствую, что класс Core Foundation CFTree может быть немного лучше. Здесь описание из ссылки класса CFTree:

Вы используете CFTree для создания древовидных структур, которые представляют иерархические организации информации. В таких структурах каждое дерево node имеет ровно одно родительское дерево (за исключением корневого дерева, у которого нет родителя) и может иметь несколько дочерних элементов.

Если вам не нравится C (Core Foundation - C, а не Objective-C), вы можете использовать библиотеку JKPTree, которая является Objective-C оболочкой CFTree. Вы можете скачать его здесь.

UPDATE:

Я просто нашел другую библиотеку под названием CHDataStructures, которая упрощает создание широкого спектра структур данных. Он поддерживает следующие структуры данных (и многие другие не включенные в список):

Дерево AVL
Абстрактное дерево двоичного поиска
Дерево Андерссон
Связанный список
Дерево поиска
Красное Черное дерево
Несбалансированное дерево
Queue
Heap

Вы можете скачать CHDataStructures здесь.

Ответ 2

CoreFoundation имеет CFBinaryHeap тип, который вы можете использовать. Там нет обложки Obj-C, но немного C никому не повредит.

Ответ 3

Вы можете использовать std::set из стандартной библиотеки С++, если вы назовете файл с расширением .mm (Objective-C ++).

Ответ 4

Это не Cocoa Touch, но библиотека коллекций GNU Objective-C имеет Red-Black Tree и абстрактное Binary Tree, а также множество других недревесных коллекций,