Содержание


Работа со структурами данных в языках Си и Python

Часть 7. Бинарные поисковые деревья (BST)

Comments

Серия контента:

Этот контент является частью # из серии # статей: Работа со структурами данных в языках Си и Python

Следите за выходом новых статей этой серии.

Этот контент является частью серии:Работа со структурами данных в языках Си и Python

Следите за выходом новых статей этой серии.

Эта статья посвящена одной из разновидностей двоичных деревьев: бинарным поисковым деревьям. Как обычно будут рассмотрены теоретические алгоритмы для выполнения различных операций: вставка и удаление узла, поиск максимума/минимума и практические реализации данных алгоритмов на языках Си и Python.

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

Бинарные поисковые деревья (англ. binary search tree или сокращенно BST) - это разновидность двоичного дерева, обладающая следующими отличительными свойствами:

  1. для каждого узла X (если X не равен NULL) все узлы в его левом поддереве содержат значения, которые ВСЕГДА меньше значения узла X.
  2. все узлы в правом поддереве узла Х содержат значения, которые соответственно ВСЕГДА больше значения узла X.
  3. каждый узел в таком дереве является родителем для своих поддеревьев.

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

Результат вставки узлов в бинарное поисковое дерево может оказаться непредсказуемым. Если вставлять в такое дерево узлы, которые уже были предварительно отсортированы, то это приведет к вырождению дерева. На рисунке 1 показаны две одинаковые по содержанию реализации поискового дерева, но с различными корневыми узлами.

Рисунок 1. Два варианта представления бинарного поискового дерева
Рисунок 1. Два варианта представления бинарного поискового дерева
Рисунок 1. Два варианта представления бинарного поискового дерева

В листинге 1 приведено объявление структур для узла бинарного дерева и самого дерева на языке Си.

Листинг 1. Определение структур для представления дерева и его узлов
struct node
{
  int data;
  struct node * left;
  struct node * right;
};

struct tree
{
  struct node * root;	// указатель на корень дерева
  int count;			// количество узлов в дереве
};

Структура, использующаяся для описания узла дерева, полностью совпадает со структурой, использующейся для описания связного списка. Используя эти две структуры можно подготовить функцию на языке Си для создания дерева (см. листинг 2).

Листинг 2. Функция для создания дерева
struct tree * tree_create(void)
{
struct tree * new_tree = malloc(sizeof * new_tree);
	if (new_tree == NULL) return NULL;
	new_tree->root = NULL;
	new_tree->count = 0;
	return new_tree;
}

Вставка узла в бинарное поисковое дерево

Перед вставкой нового элемента в бинарное дерево обязательно нужно проверить, нет ли в нем уже такого элемента. Для этого необходимо начать обход дерева с корневого узла и проверить, не превосходит ли значение корневого узла добавляемого значения. Если корневой узел больше добавляемого элемента, то необходимо переместиться в левое дочернее дерево. В противном случае - в правое. Функция поиска определенного узла в дереве, приведенная в листинге 3, вернет 1 в случае, если искомое значение будет найдено, или 0, если указанное значение в дереве отсутствует.

Листинг 3. Функция для поиска узла в дереве
int bin_search(const struct tree * search_tree, int item)
{
  const struct node * search_node;
  search_node = search_tree->root;
	for(;;)
	{
		if (search_node == NULL) return 0;
		else if (item == search_node->data) return 1;
		else if (item > search_node->data) search_node = search_node->right;  
		else search_node = search_node->left;  
	}
}

После выполнения данной проверки можно переходить к добавлению узла в бинарное дерево. Функция вставки аналогична функции поиска: необходимо пройти по дереву и вставить узел в нужное место. Для этого следует выбрать левое или правое поддерево корневого узла, а затем рекурсивно перемещаться по выбранному поддереву до тех пор, пока не будет найдена позиция для вставки узла, как показано в листинге 4.

Листинг 4. Функция для вставки узла в бинарное поисковое дерево
int insert(struct tree * search_tree, int item)
{
	struct node * search_node, **new;

	new = &search_tree->root;
	search_node = search_tree->root;

	for(;;)
	{
		if(search_node == NULL)
		{
			search_node = *new = malloc(sizeof * search_node);
			if(search_node != NULL)
			{
				search_node->data = item;
				search_node->left = search_node->right=NULL;
				search_tree->count++;
				return 1;
			}
			else return 0;
		}
		else if(item == search_node->data) return 2;
else if(item > search_node->data)
{
new = &search_node->right;
			search_node = search_node->right;
		}
		else
		{
			new = &search_node->left;
			search_node = search_node->left;
		}
	}
}

Элемент, добавленный первым, автоматически становится корнем дерева. Функция может вернуть одно из 3-х значений: 0 (при вставке произошла ошибка), 1 (узел успешно вставлен), 2 (такой элемент уже есть в дереве).

Удаление узла из бинарного поискового дерева

Функция удаления узла из бинарного дерева также будет возвращать 0, если возникла ошибка, или 1 в случае удачного удаления элемента. В данной функции используется уже знакомый алгоритм поиска, который будет искать элемент, помеченный для удаления. После того, как этот элемент будет обнаружен, возможны 3 варианта действий, которые представлены на рисунке 2.

Рисунок 2. Три варианта удаления элемента из бинарного поискового дерева
Рисунок 2. Три варианта удаления элемента из бинарного поискового дерева
Рисунок 2. Три варианта удаления элемента из бинарного поискового дерева

В первом случае (вариант a) узел z имеет только левый дочерний узел, и при удалении он и будет заменен им. Во втором варианте (рисунок b) узел z заменяется узлом y.

В третьем варианте (рисунок с) корневой узел z заменяется узлом x, что приводит к дополнительным перестроениям в правом поддереве. Узел x становится преемником узла z, так как в левом поддереве узла z все узлы меньше 5, и преемника нужно искать в правом поддереве узла z.

Листинг 5. Функция для удаления узла из бинарного поискового дерева
int delete(struct tree * search_tree, int ** item)
{
	struct node ** q,*z;
	
	q=&search_tree->root;
	z=search_tree->root;
	//поиск удаляемого элемента
	for(;;)
	{
		if(z == NULL) return 0;
		else if(item == (int **)z->data) break;
		else if(item > (int **)z->data)
		{
			q = &z->right;
			z = z->right;
		}
		else
		{
			q = &z->left;
			z = z->left;
		}
	}		
	
	// непосредственное удаление элемента
	if(z->right == NULL) *q = z->left;
	else
	{
		struct node * y = z->right;
		if(y->left == NULL)
		{
			y->left = z->left;
			*q-y;
		}
		else
		{
			struct node * x=y->left;
			while(x->left != NULL)
			{
				y = x;
				x = y->left;
			}
			y->left = x->right;
			x->left = z->left;
			x->right = z->right;
			*q=x;
		}
	}

	search_tree->count --;
	free(z);
	return 1;
}

Проход по дереву

Для прохода по дереву можно использовать рекурсию, так как любое двоичное дерево - это рекурсивная структура. Функции, приведенные в листинге 6, могут распечатать дерево, начиная с любого узла: сначала печатается левое поддерево, потом правое.

Листинг 6. Функции для вывода содержимого дерева
//функция для распечатки фрагмента дерева - с любого узла
static void walk(const struct node * search_node)
{
	if(node == NDLL) return;
	walk(node->left);
	printf("%d ", search_node->data);
	walk(node->right);
}	

//функция для распечатки дерева целиком - с корня
void walk2(const struct tree * my_tree)
{
	walk(my_tree->root);
}

Для прохода по дереву можно обойтись и одной функцией, если ввести массив указателей на узлы, который будет заполняться во время прохода. В функции будет выполняться вложенный цикл для прохода дерева от текущего узла влево до конца. А дополнительный массив поможет обойти все дерево за один проход, так как в нем будет храниться указатель на текущий корневой узел.

Листинг 8. Нерекурсивная реализация обхода дерева
void traverse(const struct tree * search_tree)
{
	struct node * stack[32];
	int count;
	struct node * search_node;
	count = 0;
  search_node = search_tree->root;

	for(;;)
	{
		while(search_node != NOLL)
		{
			stack[count++] = search_node;
			search_node = search_node->left;
		}
		if(count == 0) return ;
		search_node = stack[-count];
		printf("%d",search_node->data);
		search_node = search_node->right;
	}
}

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

Удаление дерева

В этом разделе приведены функции для полного удаления дерева, начиная с листьев и заканчивая корневым узлом.

Листинг 9. Функции для удаления дерева
//функция для удаления отдельного узла дерева и его потомков
static void destroy(struct node * search_node)
{
	if(search_node == NOLL) return;
	destroy(search_node->left);
	destroy(search_node->right);
	free(search_node);
} 

//функция для полного удаления дерева
void destroy(struct tree * search_tree)
{
	destroy(search_tree->root);
	free(search_tree);
}

Нахождение минимума и максимума в бинарном поисковом дереве

В листинге 10 приведены две функции для поиска в дереве узлов с минимальным и максимальным значением. Минимальное значение нужно искать в левом поддереве корневого элемента, а максимальное - в правом.

Листинг 10. Функции для поиска минимального и максимальных значений
struct node * tree_minimum(struct tree * search_tree)
{
	struct node * search_node;
search_node = search_tree->root;
	while (search_node->left != NULL)
			search_node = search_node->left;
	return search_node;
}

struct node * tree_maximum(struct tree * search_tree)
{
	struct node * search_node;
	search_node = search_tree->root;
	while (search_node->right != NULL)
			search_node = search_node->right;
	return search_node;
}

Определение типа двоичного дерева

Чтобы определить относится ли данное двоичное дерево к поисковым бинарным деревьям, можно использовать функцию из листинга 11.

Листинг 11. Определение типа двоичного дерева
int isBST(struct node* node) 
{
	return(isBSTUtil(node, INT_MIN, INT_MAX));
}

int isBSTUtil(struct node* node, int min, int max) 
{
	if (node==NULL) return(true);

	if (node->data<min || node->data>max) return(false);

return (
		isBSTUtil(node->left, min, node->data) &&
		isBSTUtil(node->right, node->data+1, max)
);
}

Практическая реализация алгоритмов

В файле sources.zip, прикрепленном к данной статье, находятся две программы, в которых используются описанные выше алгоритмы для обработки бинарного поискового дерева. В файле bst_operations.с находится реализация на языке Си, а файл bst_operations.py содержит реализацию на языке Python.

Программа на языке Си обладает большей функциональностью, нежели версия на Python. В Си-программе сначала создается бинарное поисковое действие из 10 узлов, затем содержимое дерева распечатывается, и из него удаляется один узел. После этого выполняется еще одна распечатка, чтобы проверить, как прошло удаление, и дерево удаляется уже полностью с освобождением памяти. В Python-программе выполняется только создание и распечатка бинарного поискового дерева из 10 узлов. Остальные алгоритмы остались нереализованными, но их можно разработать самостоятельно, используя версии на языке Си в качестве образца.

Заключение

В данной статье были рассмотрены основные алгоритмы, использующиеся для работы с одной из самых популярных структур данных – бинарным поисковым деревом. Кроме теоретических описаний в статье были представлены и практические реализации данных алгоритмов на языке программирования Си. Для лучшего усвоения материала читателю предлагается самостоятельно разработать реализацию этих алгоритмов на языке Python и решить следующие задачи:

  1. если вставить в бинарное поисковое дерево числа в диапазоне от 1 до 64 в порядке возрастания таким образом, что сначала вставляются нечетные числа, потом четные, то какова будет высота этого дерева?
  2. если сначала вставить 3 числа: 32, 16, 48, а потом все остальные в прежнем порядке, то какова будет высота этого дерева?

Ресурсы для скачивания


Похожие темы

  • Работа со структурами данных в языках Си и Python. Часть 1.
  • Работа со структурами данных в языках Си и Python. Часть 2.
  • Работа со структурами данных в языках Си и Python. Часть 3.
  • Работа со структурами данных в языках Си и Python. Часть 4.
  • Работа со структурами данных в языках Си и Python. Часть 5.
  • Работа со структурами данных в языках Си и Python. Часть 6.
  • Работа со структурами данных в языках Си и Python. Часть 7.

Комментарии

Войдите или зарегистрируйтесь для того чтобы оставлять комментарии или подписаться на них.

static.content.url=http://www.ibm.com/developerworks/js/artrating/
SITE_ID=40
Zone=Linux, Open source
ArticleID=665288
ArticleTitle=Работа со структурами данных в языках Си и Python: Часть 7. Бинарные поисковые деревья (BST)
publish-date=05312011