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

Question

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

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

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

Answer 1

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

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

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

ОБНОВЛЕНИЕ:

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

• Дерево AVL
• Абстрактное дерево двоичного поиска
• Дерево Андерссона
• СвязаноСписок
• Поисковое дерево
• Красно-черное дерево
• Несбалансированное дерево
• Очередь

• Куча

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

Answer 2

Это не Cocoa Touch, но библиотека коллекций GNU Objective-C имеет Красно-черное дерево и абстрактное Двоичное дерево , а такжекуча других вещей, не связанных с деревьями.

Answer 3

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

Answer 4

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