Notes

!Деревья поиска

3 min read

Определение

Деревья поиска - деревья, хранящие в вершинах некоторые значения, называемые ключами, а также умело манипулирующие ими. Все операции обычно выполняются за высоту дерева, а для удобно перемещения по нему, дерево обычно хранит значения в определенном порядке, зачастую отсортированы по ключам.

Что зачастую умеют:

  • add x - O(h)
  • remove x - O(h)
  • find x - O(h)
  • lower_bound x - O(h)
  • merge - O(h)
  • split - O(h)

Двоичные деревья поиска

Определение

Двоичное бинарное дерево - бинарное дерево, в каждой вершине которого записано значение, называем ключом, причем, если в вершине лежит x, то в поддереве ее левого сына лежат только вершины, меньшие x, а в поддереве правого сына - большие x.

Основные операции в ДДП

Поиск элемента

Алгоритм:

  • Встаем в корень
  • Сравниваем элемент, который хотим вставить с текущим, идем вправо или влево в зависимости от результата сравнения.
  • Если мы пришли в элемент с нужным ключом, то нашли его в дереве, если нет, то должны когда-то из дерева выйти, это значит, что ключа в нем нет. Работает все это, очевидно, за высоту дерева.
Код
bool exists(node *root, int key) {  
	if (root == nullptr) {    
		return false;  
	}  
	if (root->key == key) {    
		return true;  
	}  
	if (root->key > key) {    
		return exists(root->l, key);  
	}  
	return exists(root->r, key);
}

Добавление элемента

Алгоритм:

  • Встаем в корень
  • Сравниваем элемент, который хотим вставить с текущим, идем вправо или влево в зависимости от результата сравнения.
  • Если пришли в элемент, ключ которого равен тому, что мы пытаемся добавить, то ничего делать не надо, если же мы смогли выйти из дерева, то создаем новую вершину и привязываем ее туда, откуда мы вышли, правила дерева не нарушатся, так как мы все время шли в нужную сторону.
Код
node *insert(node *root, int key) {
	if (root == nullptr) {    
		node *nw = new node();    
		nw->h = 1;   
		nw->key = key;  
		return nw; 
	}
	if (root->key == key) {   
		return root; 
	}  
	if (root->key > key) {
		root->l = insert(root->l, key); 
	} else {  
		root->r = insert(root->r, key); 
	}  
	root = balance(root); 
	return root;
}

Удаление элемента

Сначала нужно найти элемент, который мы хотим удалить, для Если у удаляемой вершины нет сыновей, или сын один, то мы можем просто его выкинуть и перепривязать потомка, ничего не сломается. Если сыновей два, то мы ищем самого большого потомка в правом поддереве, у него всего один потомок, мы свапаем его с нужной вершиной, дерево при этом не ломается, ну и теперь удалить нужную вершину не представляет труда.

AVL -дерево

Создатели:

  • Адельсон-Вельсский
  • Ландис

Принцип работы

Заведем отображение h(T), равный высоте дерева T. В дереве AVL будем поддерживать: Где L и R соответственно левое и правое поддерево любой вершины исходного дерева v. Лемма. В дереве высоты h хотя вершины, где - ое число Фибоначчи. Доказательство: Легко просто вывести формулу: Из этого можно понять, что высота дерева растет логарифмично, так как и числа Фибоначчи растут логарифмично.

Graph View