3 replies to this topic

[ทรงธรรม]

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
char line[100]; /* buffer for input data */
int n; /* control for loop */
struct node {
	char *data; /* word for this tree */
	struct node *left; /* tree to the left */
	struct node *right; /* tree to the right */
};
struct node *root = NULL;
char *saveString();
void enter();
void scan();
void printTree();
struct node *findTree();
void deleteTree();
int deepChild();
struct node *percolateDown();
struct node *searchParent();
void complexDelete();
void complexDeleteR();
struct node *searchParentL();
int main(int argc, char *argv[]) {
	struct node *cur_node; /* node to delete */
	printf("Enter file name\n");
	fgets(line, sizeof(line), stdin);
	line[strlen(line) - 1] = '\0';
	scan(line);
	printTree(root);
	printf("Enter word to delete\n");
	fgets(line, sizeof(line), stdin);
	line[strlen(line) - 1] = '\0';
	cur_node = root;
	cur_node = findTree(cur_node, line);
	if (cur_node == NULL ) {
		printf("Don't find word");
	} else {
		printf("Find! word\n");
		printTree(root);
		deleteTree(cur_node, root);
		printTree(root);
	}
	return 0;
}
char *saveString(char *st) {
	char *newst; /* char array for copy */
	newst = malloc((unsigned) (strlen(st) + 1));
	if (newst == NULL ) {
		fprintf(stderr,"out of memory\n");
		exit(8);
	}
	strcpy(newst, st);
	return newst;
}
void enter(struct node **node, char *st) {
	int res; /* result of compare data with st */
	if ((*node) == NULL ) {
		(*node) = malloc(sizeof(struct node));
		if ((*node) == NULL ) {
			fprintf(stderr,"out of memory\n");
			exit(8);
		}
		(*node)->data = saveString(st);
		(*node)->left = NULL;
		(*node)->right = NULL;
	}
	res = strcmp((*node)->data, st);
	/* if already contain word return */
	if (res == 0) {
		return;
	} else if (res < 0) {
		enter(&(*node)->right, st);
	} else {
		enter(&(*node)->left, st);
	}
}
void scan(char *li) {
	char word[100]; /* char array for each word */
	int ch; /* temporary char and used int for EOF */
	FILE *in_file; /* file from user */
	in_file = fopen(li, "r");
	if (in_file == NULL ) {
		fprintf(stderr,"unable to open file %s\n",li);
		exit(8);
	}
	while (1) {
		while (1) {
			ch = fgetc(in_file);
			if (ch != ' ' || ch == EOF)
				break;
		}
		if (ch == EOF)
			break;
		word[0] = ch;
		for (n = 1; n < 100; ++n) {
			ch = fgetc(in_file);
			if (ch == ' ' || ch == EOF)
				break;
			word[n] = ch;
		}
		word[n] = '\0';
		enter(&root, word);
	}
	fclose(in_file);
}
void printTree(struct node *top) {
	if (top == NULL )
		return;
	printTree(top->left);
	printf("%s ", top->data);
	printTree(top->right);
}
struct node *findTree(struct node *cur, char *w) {
	int resu = 1;
	if (cur != NULL ) {
		resu = strcmp(cur->data, w);
		if (resu < 0) {
			return findTree(cur->right, w);

		} else if (resu > 0) {
			return findTree(cur->left, w);

		} else {
			return cur;
		}
	} else {
		return NULL ;
	}

}
void deleteTree(struct node *cur, struct node *sroot) {
	struct node *childl = NULL;
	struct node *childr = NULL;
	struct node *parent = NULL;
	printf("%s %s\n", cur->data, sroot->data);
	if (strcmp(sroot->data, cur->data) == 0) {
		if (sroot->left != NULL )
			childl = sroot->left;
		if (sroot->right != NULL )
			childr = sroot->right;
		if (childl == NULL && childr == NULL ) {/* if block 1 */
			parent = searchParentL(sroot,root);
			if(parent->left==sroot)
				parent->left = NULL;
			if(parent->right==sroot)
				parent->right = NULL;	
			free(sroot);
			sroot = NULL;
		} else if (childl == NULL ) {
			if(childr->left == NULL&&childr->right == NULL){	
			sroot->data = childr->data;
			free(childr);
			sroot->right = NULL;
			}else{
					complexDeleteR(childr,sroot);
			}
		} else if (childr == NULL ) {
			sroot->data = childl->data;
			if(childl->left==NULL&&childl->right==NULL)
				sroot->left = NULL;
			if(childl->left!=NULL){
				sroot->left = childl->left;
			}
			if(childl->right!=NULL){
				sroot->right = childl->right;
				if(childl->left==NULL)
				sroot->left = NULL;
			}
			free(childl);
			
		} else {/* block 1 childl&childr != NULL*/
			if (childl->left != NULL && childl->right != NULL ) {/* if block 2 */
				if (childr->left == NULL && childr->right == NULL ) {
					sroot->data = childr->data;
					sroot->right = NULL;
					free(childr);
					childr = NULL;
				} else if (childr->left == NULL ) {
					sroot->data = childr->data;
					sroot->right = childr->right;
					free(childr);
					childr = NULL;
				} else if (childr->right == NULL ) {
					sroot->data = childr->data;
					sroot->right = childr->left;
					free(childr);
					childr = NULL;
				}
			} else if (childl->left == NULL && childl->right == NULL ) {
				sroot->data = childl->data;
				sroot->left = NULL;
				free(childl);
				childl = NULL;
			} else if (childl->left == NULL ) {
				if(childl->right->left == NULL&&childl->right->right == NULL){
				sroot->data = childl->right->data;
				free(childl->right);
				childl->right = NULL;
				}else{
					complexDelete(childl,sroot);
				}
			} else if (childl->right == NULL ) {
				sroot->data = childl->data;
				sroot->left = childl->left;
				free(childl);
				childl = NULL;
			} else {/* childl & childr full *//* block 2 */
				complexDelete(childl,sroot);
			}/* end if block 2 */
		}/* end if block 1 */
	} else if (strcmp(sroot->data, cur->data) > 0) {
		deleteTree(cur, sroot->left);
	} else if (strcmp(sroot->data, cur->data) < 0) {
		deleteTree(cur, sroot->right);
	}
}
int deepChild(struct node *cur) {
	struct node *childl = NULL;
	struct node *childr = NULL;
	int deepcount = 0;
	int leftcount = 0;
	int rightcount = 0;
	if (cur->left != NULL )
		childl = cur->left;
	if (cur->right != NULL )
		childr = cur->right;
	if (childl == NULL && childr == NULL ) {
		return 0;
	} else {
		if (childl != NULL || childr != NULL )
			++deepcount;
		if (childl != NULL )
			leftcount = deepChild(childl);
		if (childr != NULL )
			rightcount = deepChild(childr);
		if (leftcount >= rightcount)
			deepcount += leftcount;
		else
			deepcount += rightcount;
		return deepcount;
	}
}
struct node *percolateDown(struct node *cur) {
	struct node *childr = NULL;
	if (cur->right != NULL )
		childr = cur->right;
	if (childr == NULL ) {
		return cur;
	} else {
		return (percolateDown(childr));
	}
}
struct node *searchParent(struct node *cur, struct node *ssroot) {
	struct node *childr = NULL;
	if (ssroot->right != NULL )
		childr = ssroot->right;
	if (childr == cur) {
		return ssroot;
	} else {
		return (searchParent(cur, childr));
	}
}
void complexDelete(struct node *childl, struct node *sroot) {
	struct node *pchild = NULL;
	struct node *schild = NULL;
	struct node *pchildl = NULL;
	int deepl = 0;
	int deepr = 0;
	/*deepl = deepChild(childl);
	 deepr = deepChild(childr);
	 if(deepl>=deepr)
	 pchild = percolateDown(childr);
	 else*/
	pchild = percolateDown(childl);
	schild = searchParent(pchild, childl);
	if (pchild->left != NULL ) {/* if block 3 */
		pchildl = pchild->left;
		if (schild != childl) {
			sroot->data = pchild->data;
			schild->right = pchildl;
			free(pchild);
			pchild = NULL;
		} else {/* schild == childl */
			sroot->data = pchild->data;
			childl->right = pchildl;
			free(pchild);
			pchild = NULL;
		}
	} else {/* block 3 pchild->left == NULL*/
		if (schild != childl) {
			sroot->data = pchild->data;
			schild->right = NULL;
			free(pchild);
			pchild = NULL;
		} else {/* schild == childl */
			sroot->data = pchild->data;
			childl->right = NULL;
			free(pchild);
			pchild = NULL;
		}
	}/* end if block 3 */
}
void complexDeleteR(struct node *childr, struct node *sroot){
	struct node *pchild = NULL;
	struct node *pchildl = NULL;
	struct node *schild = NULL;
	pchild = percolateDown(childr);
	if(pchild==childr){
		if (pchild->left != NULL ) {/* if block 3 */
			pchildl = pchild->left;
			sroot->data = pchild->data;
			sroot->left = pchildl;
			sroot->right = NULL;
			free(pchild);
			pchild = NULL;
		} else {/* block 3 pchild->left == NULL*/
			sroot->data = pchild->data;
			sroot->right = NULL;
			free(pchild);
			pchild = NULL;
		}/* end if block 3 */
	}else{
		schild = searchParentL(sroot,root);
		schild->left = childr;
		free(sroot);
		sroot = NULL;
	}
}
struct node *searchParentL(struct node *cur, struct node *sroot){
	struct node *childl = NULL;
	struct node *childr = NULL;
	int res =1;
	if(sroot->left!=NULL)
		childl = sroot->left;
	if(sroot->right!=NULL)
		childr = sroot->right;
	res = strcmp(sroot->data,cur->data);
	if(res<0){
		res = strcmp(childr->data,cur->data);
		if(res==0){
			return sroot;
		}else{
			return searchParentL(cur,childr);
		}
	}else if(res>0){
		res = strcmp(childl->data,cur->data);
		if(res==0){
			return sroot;
		}else{
			return searchParentL(cur,childl);
		}
	}
}

คือ ผมเอง ลองไปแค่ file เดียวเอง ยังไม่ค่อย แน่ใจ เท่าไหร่

 

แต่ ที่รู้คือ tree นี่ยาก กว่า linked_list และ double linked_list เยอะ มาก ๆ

[CockRoachKiller]

1) scan()  can not handle new line and result in corrupted stack.   You should use fgets() or handle '\n' '\r' your self. 

 

Ex.

 

    for (n = 1; n < 100; ++n) {
            ch = fgetc(in_file);
            if (ch == ' ' || ch == EOF || ch == '\n' || ch == '\r')
                break;
            word[n] = ch;
        }

 

 

2) Program can not delete some node.   For example "C++" or "Redistributable" in these test file. 

 install.txt   843bytes   45 downloads

 

 

 

Attached Files

•  install.txt   843bytes   58 downloads

[ทรงธรรม]

1) scan()  can not handle new line and result in corrupted stack.   You should use fgets() or handle '\n' '\r' your self. 

 

Ex.

 

    for (n = 1; n < 100; ++n) {
            ch = fgetc(in_file);
            if (ch == ' ' || ch == EOF || ch == '\n' || ch == '\r')
                break;
            word[n] = ch;
        }

 

 

2) Program can not delete some node.   For example "C++" or "Redistributable" in these test file. 

แหะ ๆ ผมไปแก้ เงื่อนไข มาแล้วครับ

 

เมื่อกี้ ผมใช้ interactive debugger ของ c free 5

 

แล้ว ทราบแล้วครับว่า เงื่อนไข ผมผิดไปจุดหนึ่ง ผมแก้มันดังนี้ ครับ

 

จาก if (childl->left != NULL && childl->right != NULL ) {/* if block 2 */

 

อันนี้ จาก function void deleteTree อะครับ

 

เป็น

 

if (childl->left != NULL && childl->right != NULL
            &&(childr->left == NULL || childr->right == NULL )) {/* if block 2 */

 

เพิ่มตัว ที่ขีดเส้นใต้ อะครับ เพราะมันจะได้ นำไปสู่เงื่อนไข ภายใจ block ของ if อันนี้ได้ อะครับ

 

ตอนที่ ผมลอง ใช้ C++ กับ Redistribute จริง ๆ มันไม่ใช่ ของ block นี้ อะครับ

 

แต่มันดันเข้ามา block นี้ เพราะ ผมตก บรรทัด ที่ขีดเส้นใต้

 

ซึ่งเป็นเงื่อนไข ไม่ให้ มันเข้า อะครับ แหะ ๆ

 

ก็ผมเปลี่ยน ตรง scan ตามที่ คุณ killer บอกแล้ว นะครับ ใช้ได้เลยครับ

 

ก็เปลี่ยนอันใหม่เป็น (แก้ 2 จุด)

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
char line[100]; /* buffer for input data */
int n; /* control for loop */
struct node {
	char *data; /* word for this tree */
	struct node *left; /* tree to the left */
	struct node *right; /* tree to the right */
};
struct node *root = NULL;
char *saveString();
void enter();
void scan();
void printTree();
struct node *findTree();
void deleteTree();
int deepChild();
struct node *percolateDown();
struct node *searchParent();
void complexDelete();
void complexDeleteR();
struct node *searchParentL();
int main(int argc, char *argv[]) {
	struct node *cur_node; /* node to delete */
	printf("Enter file name\n");
	fgets(line, sizeof(line), stdin);
	line[strlen(line) - 1] = '\0';
	scan(line);
	printTree(root);
	printf("Enter word to delete\n");
	fgets(line, sizeof(line), stdin);
	line[strlen(line) - 1] = '\0';
	cur_node = root;
	cur_node = findTree(cur_node, line);
	if (cur_node == NULL ) {
		printf("Don't find word");
	} else {
		printf("Find! word\n");
		printTree(root);
		deleteTree(cur_node, root);
		printTree(root);
	}
	return 0;
}
char *saveString(char *st) {
	char *newst; /* char array for copy */
	newst = malloc((unsigned) (strlen(st) + 1));
	if (newst == NULL ) {
		fprintf(stderr,"out of memory\n");
		exit(8);
	}
	strcpy(newst, st);
	return newst;
}
void enter(struct node **node, char *st) {
	int res; /* result of compare data with st */
	if ((*node) == NULL ) {
		(*node) = malloc(sizeof(struct node));
		if ((*node) == NULL ) {
			fprintf(stderr,"out of memory\n");
			exit(8);
		}
		(*node)->data = saveString(st);
		(*node)->left = NULL;
		(*node)->right = NULL;
	}
	res = strcmp((*node)->data, st);
	/* if already contain word return */
	if (res == 0) {
		return;
	} else if (res < 0) {
		enter(&(*node)->right, st);
	} else {
		enter(&(*node)->left, st);
	}
}
void scan(char *li) {
	char word[100]; /* char array for each word */
	int ch; /* temporary char and used int for EOF */
	FILE *in_file; /* file from user */
	in_file = fopen(li, "r");
	if (in_file == NULL ) {
		fprintf(stderr,"unable to open file %s\n",li);
		exit(8);
	}
	while (1) {
		while (1) {
			ch = fgetc(in_file);
			if (ch != ' ' || ch == EOF)
				break;
		}
		if (ch == EOF)
			break;
		word[0] = ch;
		for (n = 1; n < 100; ++n) {
			ch = fgetc(in_file);
			if (ch == ' ' || ch == EOF || ch == '\n' || ch == '\r')
				break;
			word[n] = ch;
		}
		word[n] = '\0';
		enter(&root, word);
	}
	fclose(in_file);
}
void printTree(struct node *top) {
	if (top == NULL )
		return;
	printTree(top->left);
	printf("%s ", top->data);
	printTree(top->right);
}
struct node *findTree(struct node *cur, char *w) {
	int resu = 1;
	if (cur != NULL ) {
		resu = strcmp(cur->data, w);
		if (resu < 0) {
			return findTree(cur->right, w);

		} else if (resu > 0) {
			return findTree(cur->left, w);

		} else {
			return cur;
		}
	} else {
		return NULL ;
	}

}
void deleteTree(struct node *cur, struct node *sroot) {
	struct node *childl = NULL;
	struct node *childr = NULL;
	struct node *parent = NULL;
	printf("%s %s\n", cur->data, sroot->data);
	if (strcmp(sroot->data, cur->data) == 0) {
		if (sroot->left != NULL )
			childl = sroot->left;
		if (sroot->right != NULL )
			childr = sroot->right;
		if (childl == NULL && childr == NULL ) {/* if block 1 */
			parent = searchParentL(sroot,root);
			if(parent->left==sroot)
				parent->left = NULL;
			if(parent->right==sroot)
				parent->right = NULL;	
			free(sroot);
			sroot = NULL;
		} else if (childl == NULL ) {
			if(childr->left == NULL&&childr->right == NULL){	
			sroot->data = childr->data;
			free(childr);
			sroot->right = NULL;
			}else{
					complexDeleteR(childr,sroot);
			}
		} else if (childr == NULL ) {
			sroot->data = childl->data;
			if(childl->left==NULL&&childl->right==NULL)
				sroot->left = NULL;
			if(childl->left!=NULL){
				sroot->left = childl->left;
			}
			if(childl->right!=NULL){
				sroot->right = childl->right;
				if(childl->left==NULL)
				sroot->left = NULL;
			}
			free(childl);
			
		} else {/* block 1 childl&childr != NULL*/
			if (childl->left != NULL && childl->right != NULL 
			&&(childr->left == NULL || childr->right == NULL )) {/* if block 2 */
				if (childr->left == NULL && childr->right == NULL ) {
					sroot->data = childr->data;
					sroot->right = NULL;
					free(childr);
					childr = NULL;
				} else if (childr->left == NULL ) {
					sroot->data = childr->data;
					sroot->right = childr->right;
					free(childr);
					childr = NULL;
				} else if (childr->right == NULL ) {
					sroot->data = childr->data;
					sroot->right = childr->left;
					free(childr);
					childr = NULL;
				}
			} else if (childl->left == NULL && childl->right == NULL ) {
				sroot->data = childl->data;
				sroot->left = NULL;
				free(childl);
				childl = NULL;
			} else if (childl->left == NULL ) {
				if(childl->right->left == NULL&&childl->right->right == NULL){
				sroot->data = childl->right->data;
				free(childl->right);
				childl->right = NULL;
				}else{
					complexDelete(childl,sroot);
				}
			} else if (childl->right == NULL ) {
				sroot->data = childl->data;
				sroot->left = childl->left;
				free(childl);
				childl = NULL;
			} else {/* childl & childr full *//* block 2 */
				complexDelete(childl,sroot);
			}/* end if block 2 */
		}/* end if block 1 */
	} else if (strcmp(sroot->data, cur->data) > 0) {
		deleteTree(cur, sroot->left);
	} else if (strcmp(sroot->data, cur->data) < 0) {
		deleteTree(cur, sroot->right);
	}
}
int deepChild(struct node *cur) {
	struct node *childl = NULL;
	struct node *childr = NULL;
	int deepcount = 0;
	int leftcount = 0;
	int rightcount = 0;
	if (cur->left != NULL )
		childl = cur->left;
	if (cur->right != NULL )
		childr = cur->right;
	if (childl == NULL && childr == NULL ) {
		return 0;
	} else {
		if (childl != NULL || childr != NULL )
			++deepcount;
		if (childl != NULL )
			leftcount = deepChild(childl);
		if (childr != NULL )
			rightcount = deepChild(childr);
		if (leftcount >= rightcount)
			deepcount += leftcount;
		else
			deepcount += rightcount;
		return deepcount;
	}
}
struct node *percolateDown(struct node *cur) {
	struct node *childr = NULL;
	if (cur->right != NULL )
		childr = cur->right;
	if (childr == NULL ) {
		return cur;
	} else {
		return (percolateDown(childr));
	}
}
struct node *searchParent(struct node *cur, struct node *ssroot) {
	struct node *childr = NULL;
	if (ssroot->right != NULL )
		childr = ssroot->right;
	if (childr == cur) {
		return ssroot;
	} else {
		return (searchParent(cur, childr));
	}
}
void complexDelete(struct node *childl, struct node *sroot) {
	struct node *pchild = NULL;
	struct node *schild = NULL;
	struct node *pchildl = NULL;
	int deepl = 0;
	int deepr = 0;
	/*deepl = deepChild(childl);
	 deepr = deepChild(childr);
	 if(deepl>=deepr)
	 pchild = percolateDown(childr);
	 else*/
	pchild = percolateDown(childl);
	schild = searchParent(pchild, childl);
	if (pchild->left != NULL ) {/* if block 3 */
		pchildl = pchild->left;
		if (schild != childl) {
			sroot->data = pchild->data;
			schild->right = pchildl;
			free(pchild);
			pchild = NULL;
		} else {/* schild == childl */
			sroot->data = pchild->data;
			childl->right = pchildl;
			free(pchild);
			pchild = NULL;
		}
	} else {/* block 3 pchild->left == NULL*/
		if (schild != childl) {
			sroot->data = pchild->data;
			schild->right = NULL;
			free(pchild);
			pchild = NULL;
		} else {/* schild == childl */
			sroot->data = pchild->data;
			childl->right = NULL;
			free(pchild);
			pchild = NULL;
		}
	}/* end if block 3 */
}
void complexDeleteR(struct node *childr, struct node *sroot){
	struct node *pchild = NULL;
	struct node *pchildl = NULL;
	struct node *schild = NULL;
	pchild = percolateDown(childr);
	if(pchild==childr){
		if (pchild->left != NULL ) {/* if block 3 */
			pchildl = pchild->left;
			sroot->data = pchild->data;
			sroot->left = pchildl;
			sroot->right = NULL;
			free(pchild);
			pchild = NULL;
		} else {/* block 3 pchild->left == NULL*/
			sroot->data = pchild->data;
			sroot->right = NULL;
			free(pchild);
			pchild = NULL;
		}/* end if block 3 */
	}else{
		schild = searchParentL(sroot,root);
		schild->left = childr;
		free(sroot);
		sroot = NULL;
	}
}
struct node *searchParentL(struct node *cur, struct node *sroot){
	struct node *childl = NULL;
	struct node *childr = NULL;
	int res =1;
	if(sroot->left!=NULL)
		childl = sroot->left;
	if(sroot->right!=NULL)
		childr = sroot->right;
	res = strcmp(sroot->data,cur->data);
	if(res<0){
		res = strcmp(childr->data,cur->data);
		if(res==0){
			return sroot;
		}else{
			return searchParentL(cur,childr);
		}
	}else if(res>0){
		res = strcmp(childl->data,cur->data);
		if(res==0){
			return sroot;
		}else{
			return searchParentL(cur,childl);
		}
	}
}

[CockRoachKiller]

Congratulation! It might still has a bug, but at least it's not an obvious one.   My suggestion for more extensive testing is

 

- try using the same data file to delete all nodes except some particular node.   For example, if you input "C+++".  You need to load data file and deleteNode one by one except "C++". At the end, if you have only C++ node, then your program work very well.     You might need to try other word to make sure. 

 

- use bigger data file > 1M.  

 

 

I don't know why you interest in tree.  To understand how it works, does not mean we have to write it.  I never ever need to use tree in any implementation.  For speed, "hash" is hard to beat, given enough memory.   For simplicity, "array" almost bug free.  You should notice that most language has build in these two already.   You need to have very large, > 100K items to see any significant different between tree and simple array search.    

 

Try modify you code like this  (only main)
 

 

#include <Windows.h>

#define NUMITEMS 1000
int main(int argc, char *argv[])
{

    struct node *cur_node; /* node to delete */
    char *strArray[NUMITEMS];
    char tmp[1024];
    int i,j;
    long start,end;

    for(i=0;i<NUMITEMS;i++){
        int r = rand();
        sprintf(tmp,"%d",r);
        enter(&root, tmp);
        strArray[i] = saveString(tmp);
    }
    start = GetTickCount();
    srand(1000);
    for(i=0;i<100;i++){
        sprintf(tmp,"%d",strArray[rand()%NUMITEMS]);
        cur_node = findTree(root, tmp);
    }
    printf("Tree find time=%d\n",GetTickCount() - start);
    start = GetTickCount();
    srand(1000);
    for(i=0;i<100;i++){
        sprintf(tmp,"%d",strArray[rand()%NUMITEMS]);
        for(j=0;j<NUMITEMS;j++){
            if(strcmp(strArray[j],tmp)==0){
                break;
            }
        }
    }
    printf("Array find time=%d\n",GetTickCount() - start);
}

 

 

 

 

 

 

The new main will create random string of integer for NUMITEMS, put them in your tree and my array strArray.   Then random search for 100 items by your tree and my array.   You will see no different in the time. You need to change NUMITEMS to 100K in order to see the different.    You can try 1M and if your program crash, you will learn something by finding a way to fix it. 

 

*you need to include Windows.h to use GetTickCount() or find another time function.

** GetTickCount() has resolution of 15ms.  So 0 or 15 is not significant due to measurement error.

*** See how easy we can create stupid array and have the same performance as your sophisticated tree for data < 100K.   The best part is, as computer get faster, this number get bigger also.  

Edited by CockRoachKiller, 10 September 2013 - 21:01.