Двоичные деревья (binary search trees)

[eddy_em]

А вот и простейшая реализация двоичных деревьев.

#include <stdio.h>
#include <stdlib.h>
#include <err.h>
#include <assert.h>
#include <stdint.h>

static inline uint32_t log_2(const uint32_t x) {
	uint32_t y;
	asm ( "\tbsr %1, %0\n"
		: "=r"(y)
		: "r" (x)
	);
	return y;
}


typedef struct btree_node{
	int data;
	struct btree_node *left, *right;
} BTree;

// later this function maybe mode difficult
void bt_destroy(BTree *node){
	free(node);
}

// get tree leaf nearest to v
BTree *bt_get(BTree *root, int v){
	if(!root) return NULL;
	int D = root->data;
	if(D == v) return root;
	if(root->data > v) return root->left;
	else return root->right;
}

// find leaf with v or nearest to it (prev)
// prev is nearest parent or NULL for root
BTree *bt_search(BTree *root, int v, BTree **prev){
	if(!root){
		if(prev) *prev = NULL;
		return NULL;
	}
	BTree *p;
	do{
		p = root;
		root = bt_get(root, v);
	}while(root && root->data != v);
	if(prev){
		if(p != root) *prev = p;
		else *prev = NULL;
	}
	return root;
}

BTree *bt_create_leaf(int v){
	BTree *node = calloc(1, sizeof(BTree));
	if(!node) return NULL;
	node->data = v;
	return node;
}

// insert new leaf (or leave it as is, if exists)
// return new node
BTree *bt_insert(BTree **root, int v){
	BTree *closest = NULL, *node = NULL;
	if(root && *root){
		node = bt_search(*root, v, &closest);
		if(node) return node; // value exists
	}
	node = bt_create_leaf(v);
	if(!node) return NULL;
	if(!closest){ // there's no values at all!
		if(root) *root = node; // modify root node
		return node;
	}
	// we have a closest node to our data, so create node and insert it:
	int D = closest->data;
	if(D > v) // there's no left leaf of closest node, add our node there
		closest->left = node;
	else
		closest->right = node;
	return node;
}

// find mostly right element or NULL if no right children
BTree *max_leaf(BTree *root, BTree **prev){
	if(!root)
		return NULL;
	BTree *ret = root->left;
	if(prev) *prev = root;
	while(ret->right){
		if(prev) *prev = ret;
		ret = ret->right;
	}
	return ret;
}
// find mostly left element or NULL if no left children
BTree *min_leaf(BTree *root, BTree **prev){
	if(!root) return NULL;
	BTree *ret = root->right;
	if(prev) *prev = root;
	while(ret->left){
		if(prev) *prev = ret;
		ret = ret->left;
	}
	return ret;
}

void print_tree(BTree *leaf){
	if(!leaf){
		printf("null");
		return;
	}
	printf("(%d: ", leaf->data);
	print_tree(leaf->left);
	printf(", ");
	print_tree(leaf->right);
	printf(")");
}

// remove element, correct root if it is removed
void bt_remove(BTree **root, int v){
	assert(root);
	void conn(BTree *p, BTree *n, BTree *node){
printf("connect: %d and %d through %d\n", p ? p->data : -1,
			n? n->data : -1, node->data);
		if(p->left == node) p->left = n;
		else p->right = n;
	}
	void conn_node(BTree *prev, BTree *next, BTree *node){
		if(!prev) *root = next; // this is a root
		else conn(prev, next, node);
		bt_destroy(node);
	}
	void node_subst(BTree *nold, BTree *nnew, BTree *pold, BTree *pnew){
printf("Substitute: %d by %d\n", nold-> data, nnew->data);
		if(!pold) *root = nnew; // this is a root
		else conn(pold, nnew, nold); // connect parent of old element to new
		conn(pnew, NULL, nnew); // remove node from it's parent
		nnew->left = nold->left;
		nnew->right = nold->right;
		bt_destroy(nold);
	}
	BTree *node, *prev, *Lmax, *Rmin, *Lmp, *Rmp;
	int L, R;
	node = bt_search(*root, v, &prev);
	if(!node) return; // there's no node v
	if(!node->left){ // there's only right child or none at all
		conn_node(prev, node->right, node);
		return;
	}
	if(!node->right){ // the same but like mirror
		conn_node(prev, node->left, node);
		return;
	}
	// we have situation that element have both children
	// 1) find max from left child and min from right
	Lmax = max_leaf(node, &Lmp);
	L = Lmax->data;
	Rmin = min_leaf(node, &Rmp);
	R = Rmin->data;
	// 2) now L is left max, R - right min
	// we select the nearest to v
	if(v - L > R - v){ // R is closest value, substitute node by Rmin
		node_subst(node, Rmin, prev, Rmp);
	}else{ // substitute node by Lmax
		node_subst(node, Lmax, prev, Lmp);
	}
}

// return node need rotation
BTree *rotate_ccw(BTree *node, BTree *prev){
	if(!node) return NULL;
	printf("\n\ntry to rotate near %d", node->data);
	if(prev) printf(", right element: %d", prev->data);
	if(!node->right) printf("\n");
	if(!node->right) return node->left; // no right child -> return left
	BTree *chld = node->right;
	printf(", child: %d\n", chld->data);
	if(prev) prev->left = chld;
	node->right = chld->left;
	chld->left = node;
	if(chld->right){printf("R:%d\n",chld->right->data); return chld;} // need another rotation
	else return node;
}

void tree_to_vine(BTree **root){
	assert(root); assert(*root);
	BTree *node = *root, *prev;
	while((*root)->right) *root = (*root)->right; // max element will be a new root
	while(node && node->right)
		node = rotate_ccw(node, NULL); // go to new root
	prev = node; node = prev->left;
	while(rotate_ccw(node, prev)){
		node = prev->left;
		if(!node->right){
			prev = node;
			node = node->left;
		}
	}
}

// return node->left
BTree *rotate_cw(BTree *node, BTree *parent){ // rotate cw near node->left
	if(!node) return NULL;
	printf("\n\ntry to rotate cw near %d\n", node->data);
	if(parent)printf("\t\tparent: %d\n", parent->data);
	if(!node->left) return NULL;
	BTree *chld = node->left, *rght = chld->right;
	if(parent) parent->left = chld;
	printf("\t\t, child: %d\n", chld->data);
	chld->right = node;
	node->left = rght;
	return chld;
}

// make balanced tree
void vine_to_tree(BTree **root){
	uint32_t depth, i;
	BTree *node = *root, *prev;
	for(depth = 0; node; depth++, node = node->left);
	printf("depth: %u; ", depth);
	depth = log_2(depth);
	printf("log: %d\n", depth);
	for(i = 0; i < depth; i++){
		printf("\nIteration %d\n", i);
		node = *root;
		prev = NULL;
		if((*root)->left) *root = (*root)->left;
		while(node && node->left){
			node = rotate_cw(node, prev);
			if(!node) break;
			prev = node;
			node = node->left;
		}
	}
}

#define INS(X)  do{if(!bt_insert(&root, X)) err(1, "Malloc error");}while(0)
int main(void){
	BTree *tp, *root = NULL;
	int i, ins[] = {7,3,12,1,5,9,20,0,4,6,13,21};
	void search_bt(){
		printf("\nRoot: %d\nTree", root->data);
		print_tree(root); printf("\n\n");
		for(i = 0; i < 22; i++){
			tp = bt_search(root, i, NULL);
			printf("%d ", i);
			if(!tp) printf("not ");
			printf("found\n");
		}
	}
	for(i = 0; i < 12; i++)
		INS(ins[i]);

	search_bt();
	printf("now we delete leafs 4, 12 and 7 (old root!)\n");
	bt_remove(&root, 4); bt_remove(&root, 12); bt_remove(&root, 7);
	search_bt();
	printf("add items 2, 4, 19\n");
	INS(2); INS(4); INS(19);
	search_bt();
	printf("\nnow make a vine\n");
	tree_to_vine(&root);
	search_bt();
	printf("\nAnd balance tree\n");
	vine_to_tree(&root);
	search_bt();
	return 0;
}

Реализованы: вставка новых элементов, удаление элементов, поиск (плюс поиск подходящего родителя для элемента). Еще я воткнул "каноническое" представление двоичных деревьев на печати.
UPD: реализована балансировка.
Связывание элементов после удаления происходит так: если у удаленного элемента лишь один "ребенок", то родитель элемента связывается с "внуком"; если "детей" нет вообще, элемент просто удаляется (с соответствующим обнулением указателей на него у родителя); если детей двое, ищется максимум в левом поддереве и минимум в правом поддереве, новым элементом становится ближайший по значению к удаляемому.
Алгоритм балансировки сворован на просторах интернета. Реализация всего — честная, моя.
Можно еще добавить операции вроде foreach, но пока лень.

Comments

[eddy-em.livejournal.com]

Пока это — забавы ради (а также ради пополнения базы моих сниппетов, т.к. кое-какие алгоритмы обработки изображений потребуют и двунаправленных списков, и двоичных деревьев поиска).
Многопоточность реализовать сложновато: в операциях поиска и вставки она не пригодится; в операции удаления тоже не сильно-то напараллелишь (блокировки наверняка сожрут выигрыш от параллелизации); разве что балансировку наверняка можно распараллелить: строить "лозу" в два потока (поток для левой ветви от корня и поток для правой), строить дерево из лозы в несколько потоков (поворачивать узлы в потоках).
Но, опять-таки, я сильно сомневаюсь, что параллелизация этих операций даст какой-либо значительный выигрыш в производительности. А ради каких-нибудь процентов пятидесяти, думаю, не стоит тратить время.

UPD: вот, подумал, что что-нибудь вроде foreach легко можно было бы распараллелить, да и производительность бы реально повысилась (главное — чтобы само дерево эти операции не модифицировали, иначе опять всякие блокировки).