Глава 20 AVL-деревья: интрузивное и владеющее

Ориентация главы

Хеш-отображение отвечает «где этот ключ»; AVL-дерево отвечает «что ещё рядом с этим ключом»: обход по порядку естественно сортирован, а диапазонные запросы («все сессии с ID от 20 до 30») проходят дерево один раз. XRT даёт ему два лица — интрузивный xavl (узел встраивается в бизнесовый объект, вставка-удаление без выделений, один клан со связным списком главы 17) и владеющий xavltree (дерево владеет объектами; изъятие есть передача). Логика выбора между лицами продолжает «массивы значений против массивы указателей» (глава 14): принадлежность объекта решает форму контейнера. Глава ведёт оба лица парой полных образцов и досконально разбирает «мультииндексность» (одно дерево по ID, другое по имени) — убийственное применение интрузивной формы.

20.1引入

Менеджеру сессий нужны два представления: эксплуатационной стороне — «найти ровно эту по ID сессии» (хеширование умеет), аудитной — «экспортировать всё в порядке ID» или «выгрузить отрезок ID» — хеширование не умеет, сортированному массиву вставка стоит линейно, список вовсе неупорядочен. Ответ AVL-дерева — сбалансированное двоичное дерево поиска: вставка, удаление и поиск все O(log n), обход по порядку и есть сортированная последовательность, диапазонный запрос проходит дерево один раз.

Второе решение следует сразу: кто кем владеет — дерево объектами или наоборот? Объекты сессий уже живут в пуле (их жизненным циклом ведает пул); дереву нужно лишь «организовать их по ID» — интрузивный xavl, узел — поле объекта, ноль выделений. А самостоятельный сценарий («этой пачке конфигурационных записей и жить и умирать с деревом») берёт владеющий xavltree: вставка есть передача, изъятие есть возврат. Это решение зеркалит главу 14 в точности; с этой главой экзамен многовариантности тома 3 получает последний кусок.

20.2概念

Два лица, одна таблица

Обход по порядку — и есть сортировка

«Самобалансирование» AVL для пользователя — чёрный ящик: вы поставляете только трёхзначную функцию сравнения; ротации, высоты и ребалансировку дерево ведает само. Подпись-сигнатуру сравнения стоит разглядеть — (查找键, 树节点, 用户数据) (ключ поиска, узел дерева, пользовательские данные): ключ и узел — разные типы (один — ключ, другой — узел, несущий ключ); в интрузивной форме сравнение сперва обратным поиском через offsetof берёт носителя, затем сравнивает ключи — та же идиома «обратного поиска», что и XRT_CONTAINER_OF главы 17.

Интрузивный: индекс без выделений

Дескриптор xavl сам по себе без содержимого (Init лишь инициализирует дескриптор); вставка лишь перецепляет связи существующих объектов — ни одного кучевого выделения на всём пути. Где живут бизнесовые объекты — решаете вы: стековый массив (образец один), пул объектов (глава 22), даже slot_map — дереву всё равно, оно только связывает. Один объект с двумя полями-узлами висит на двух деревьях сразу: «одно по ID, другое по имени» — C-форма мультииндексности баз данных. Цена записана в функции сравнения: каждое сравнение делает обратный поиск носителя; эта индирекция — прирождённая стоимость интрузивной формы.

Владеющий: владение и передача

xavltree распоряжается жизнью и смертью объектов: вставка есть передача (дерево выделяет узел, оборачивающий объект), итерация выдаёт указатели объектов, а изъятие (семейство Take) возвращает объект вам и отдаёт узел дереву. Оно годится сценам «данные прирождённо принадлежат этому дереву» — конфигурационные записи, статические словари. Когда не нужны ни мультииндексность, ни внешний пул, владеющая форма пишет вдвое меньше шаблонного кода.

Разделение труда с хеш-отображением

AVL и отображения главы 18 — не конкуренты, а коллеги. Точный поиск по одному ключу — оба уровня O(1)/O(log n), у хеширования константа меньше; но как только вопрос становится «что ещё рядом с этим ключом» — упорядоченный обход, диапазонные запросы, предшественник/последователь, минимум/максимум — хеширование структурно не умеет, а AVL начинает всё с O(log n). На практике менеджер ресурсов часто держит обоих: xmap на горячем пути локации, xavl как упорядоченное представление для аудитов и экспорта — одна пачка объектов под двумя индексами (один объект на двух индексах — как раз форма интрузивного). Таблица выбора главы 23 записывает это разделение правилом: только поиск → отображение; поиск + порядок → AVL; и то и другое → держать обоих; не заставляйте один контейнер тащить два вида вопросов.

Семантика повторных ключей

Если в дереве уже есть узел с тем же ключом, Insert возвращает тот существующий узел (не NULL) — повтор не ошибка и не перезапись; «что делать» возвращается вызывающему: заменить значение, отказать или переименовать. Семантику возврата надо запомнить твёрдо: NULL — успешная вставка (наоборот многим библиотекам); не-NULL — «столкновение ключей, вот старый узел».

20.3示例

Первая полная программа: интрузивный индекс и упорядоченная итерация

Из репозиторного образца examples/containers/avl/main.c:

 */

#include <stdio.h>
#include <stddef.h>

#include <xrt.h>



/* 外部会话对象直接嵌入树节点，不产生额外分配。 */
typedef struct examplesession {
	int ID;
	const char* Name;
	xavlnode Index;          /* 侵入式链接：挂在 ID 索引树上 */
} examplesession;



/* 从侵入式链接恢复完整会话（节点地址 - 字段偏移）。 */
static examplesession* exampleSession(xavlnode* pNode)
{
	return (examplesession*)((bytes)pNode - offsetof(examplesession, Index));
}







 */
static int exampleCompare(const void* pKey, const xavlnode* pNode, ptr pUserData)
{
	const examplesession* pSession = (const examplesession*)(
		(cbytes)pNode - offsetof(examplesession, Index)
	);
	int iID = *(const int*)pKey;

	(void)pUserData;
	return (iID > pSession->ID) - (iID < pSession->ID);
}



int main(void)
{
	xavl tSessions;          /* 树句柄：本身零分配 */
	xavliter tIterator;
	examplesession pSessions[] = {
		{ 30, "gamma", { 0 } },
		{ 10, "alpha", { 0 } },
		{ 20, "beta", { 0 } }
	};

	if ( !xrtAVLInit(&tSessions) ) {
		return 1;
	}

	




	 */
	for ( size_t i = 0; i < 3; i++ ) {
		xrtAVLNodeInit(&pSessions[i].Index);
		if (
			xrtAVLInsert(
				&tSessions,
				&pSessions[i].Index,
				&pSessions[i].ID,
				exampleCompare,
				NULL,
				NULL
			) == NULL
		) {
			return 2;
		}
	}

	


	 */
	xrtAVLIterBegin(&tSessions, &tIterator);
	while ( true ) {
		xavlnode* pNode = xrtAVLIterNext(&tIterator);
		examplesession* pSession;

		if ( pNode == NULL ) {
			break;
		}
		pSession = exampleSession(pNode);
		printf("id=%d name=%s\n", pSession->ID, pSession->Name);
	}
	return 0;
}

Что только что произошло. (1) Массив сессий лежит на стеке (30, 10, 20 вперемешку); поле Index встраивает xavlnode — перед подвешиванием xrtAVLNodeInit обнуляет связи, этот шаг не опционален. (2) Сравнение (iID > pSession->ID) - (iID < pSession->ID): сперва обратный поиск носителя, затем ключ, трёхзначный возврат; вычитание предотвращает переполнение (старый знакомый главы 14). (3) xrtAVLInsert успешен ровно возвратом NULL — в цикле ветка == NULL и есть ветка успеха. (4) Ноль кучевых выделений на всём пути: дерево лишь связало три стековых объекта в упорядоченную структуру. (5) Обход по порядку всегда выводит 10, 20, 30 — порядок вставки 30,10,20 на вывод не влияет; ценность «индекса» — расцепление порядка вставки и упорядоченного представления. (6) offsetof(examplesession, Index) — обратный поиск: адрес узла минус смещение поля даёт адрес носителя — сопутствующая идиома интрузивности.

Вторая полная программа: владеющее дерево и диапазонные запросы

Из examples/containers/avl_tree/main.c, демонстрация владеющего дерева и интервальной итерации:

 */

#include <stdio.h>

#include <xrt.h>



/* 拥有型配置对象：整条结构会被复制进树内存储。 */
typedef struct exampleconfig {
	int ID;
	int Timeout;
} exampleconfig;



/* 按配置编号比较查找键与对象（容器式：直接拿对象指针）。 */
static int exampleCompare(const void* pKey, const void* pItem, ptr pUserData)
{
	int iID = *(const int*)pKey;
	int iItemID = ((const exampleconfig*)pItem)->ID;

	(void)pUserData;
	return (iID > iItemID) - (iID < iItemID);
}



int main(void)
{
	xavltree tConfigs;
	xavltreeiter tIterator;
	exampleconfig pInput[] = {
		{ 30, 3000 },
		{ 10, 1000 },
		{ 20, 2000 }
	};
	int iSearch = 20;

	/* 初始化即绑定元素大小与比较函数——之后树全权管理存储。 */
	if ( !xrtAVLTreeInit(&tConfigs, sizeof(exampleconfig), exampleCompare, NULL) ) {
		return 1;
	}

	


	 */
	for ( size_t i = 0; i < 3; i++ ) {
		if ( xrtAVLTreeAdd(&tConfigs, &pInput[i].ID, &pInput[i], NULL) == NULL ) {
			xrtAVLTreeUnit(&tConfigs);
			return 2;
		}
	}

	/* 点查 ID=20：拿到树内元素的直接指针（可读写）。 */
	{
		exampleconfig* pConfig = (exampleconfig*)xrtAVLTreeFind(&tConfigs, &iSearch);

		if ( pConfig != NULL ) {
			printf("id=%d timeout=%d\n", pConfig->ID, pConfig->Timeout);
		}
	}

	



	 */
	if ( xrtAVLTreeIterFrom(&tConfigs, &iSearch, &tIterator) ) {
		exampleconfig* pConfig;

		while ( (pConfig = (exampleconfig*)xrtAVLTreeIterNext(&tIterator)) != NULL ) {
			printf("range id=%d timeout=%d\n", pConfig->ID, pConfig->Timeout);
		}
	}

	/* 整树释放：所有元素存储一并归还。 */
	xrtAVLTreeUnit(&tConfigs);
	return 0;
}

Что только что произошло. (1) Вставка-передача: конфигурационные объекты, войдя в дерево, держатся деревом; итерация выдаёт указатели объектов. (2) Сперва точное попадание в id=20 — форма поиска и вывода попадания. (3) Диапазонная итерация идёт от нижней границы 20 до верхней 40, выводя 20, 30 — «интервальный экспорт» есть прямое применение диапазонной итерации; даже полного обхода дерева не нужно. (4) Дерево распоряжается жизнью и смертью: при Unit/Destroy объекты освобождаются вместе с ним — владеющая семантика экономит вам и заботу, и один слой контроля.

От образцов к инженерии: трёхъярусная структура индексов

Настоящий менеджер ресурсов — обычно «трёхъярусная структура индексов»: внизу хранилище объектов (пул или slot_map, ведающие жизнью, смертью и стабильными адресами); в середине индекс локации (xmap или xintmap, ключ → дескриптор); наверху упорядоченное представление (интрузивный xavl, аудиторские экспорты и диапазонные запросы). Каждый ярус делает своё дело — хранилище гарантирует стабильные адреса, локация несёт горячий путь, представление несёт порядок — и интрузивный AVL существует именно потому, что ярус хранения гарантирует неизменность адресов объектов. Эта трёхъярусная структура появится в полной форме в таблице соединений главы 67; дойдя туда, вернитесь и сравните: два образца этой главы натренировали минимальное употребление среднего и верхнего ярусов.

20.4契约

• Повторные ключи: не-NULL от Insert = столкновение, возврат — существующий узел; NULL = успех. Ветку успеха пишите == NULL.
• Интрузивный ноль выделений: NodeInit до Insert; жизненный цикл объекта обязан покрывать период на дереве; снятие с дерева прежде уничтожения объекта (та же дисциплина, что у списка главы 17).
• Владеющий: вставка-передача; Unit/Destroy освобождают сами объекты.
• Функция сравнения: трёхзначный возврат; интрузивная форма сперва делает обратный поиск носителя; от переполнения — двухшаговое сравнение вычитанием.
• Итерация: по порядку = возрастание; диапазонная итерация идёт по поддеревьям интервала, никогда по всему дереву.

Проверка функции сравнения

Вся поведенческая корректность AVL стоит на функции сравнения; она заслуживает тестирования как самостоятельная единица. Три вопроса проверки: трёхзначная ли — равенство обязано возвращать 0; сравнение, возвращающее -1 или 1 на равных, даёт «не могу найти только что вставленный ключ»; переполненно-безопасная ли — целочисленные сравнения двухшаговой формой вычитания; согласованная ли — одна и та же пара ключей обязана сравниваться взаимно-дополняюще с любого направления (a<b влечёт b>a); несогласованная функция сравнения полностью разрушает структурный баланс дерева. Закончив функцию сравнения, скормите ей ручные случаи (меньше/равно/больше/экстремумы) и лишь потом вешайте дерево — этот порядок избавляет от целого сеанса «дерево ведёт себя странно».

Типичные ошибки

if ( xrtAVLInsert(&tSessions, &pSessions[i].Index, &pSessions[i].ID,
		exampleCompare, NULL, NULL) ) {
	/* казалось, сюда = успех; на деле сюда = столкновение ключей */
}

if ( xrtAVLInsert(&tSessions, &pSessions[i].Index, &pSessions[i].ID,
		exampleCompare, NULL, NULL) == NULL ) {
	/* NULL — успешная вставка */
}

examplesession* pDead = find_expired(&tSessions);
xrtFree(pDead);                        /* Index всё ещё на дереве - дерево повисло */

examplesession* pDead = find_expired(&tSessions);
xrtAVLRemove(&tSessions, &pDead->Index);   /* сперва снять с дерева */
xrtFree(pDead);                             /* потом уничтожить */

Практические задания

Итоги