Tree

Contents

• tree는 0개 이상의 node의 집합이다.
• 노드의 수가 0개이면, tree는 비어있다(empty)라고 한다.
• 노드의 수가 1개 이상이면, 최상위(root)노드가 존재한다. 나머지 노드는 subtree라 한다.
• subtree의 루트는 전체 트리의 루트와 edge로 연결된다.

• T1, T2, ..., T3는 root인 r의 자식(child)라고 한다. r은 T1, T2,..의 부모(parent)가 된다. T1, T2는 서로의 sibling 라고 한다.
• node가 가지는 자식의 수를 단계(degree)라고 한다.
• degree가 0인 node를 잎(leaf)라고 한다.
• n1, n2, ..., nk인 일련의 노드들이 있고, ni가 ni+1의 부모노드일경우 이것을 path라고 한다.
• n1으로 부터 n2까지의 path가 존재하면 n1을 ancestor, n2를 decendent이라고 한다.
• 가장 긴 path의 길이를 트리의 높이(height)라고 한다.

• binary search tree: 모든 노드에서 left child < parent < light child를 만족하는 트리를 말한다. 가장 널리 사용되는 응용이다.
• expansion tree : 컴파일러가 표현을 해석하기 위해서 생성하는 tree다. 다음은 일반수식을 해석하기 위해서 생성된 expansion tree의 예이다.

• 깊이 우선 탐색(preorder) : left child->parent->right child 순으로 방문한다. 위의 binary tree의 경우 ++a*bc*+*defg 가 된다.
• 넓이 우선 탐색 (postorder) : left child->right child->parent child 순으로 방문한다. stack machine을 위한 compiler에서 code 생성을 위해서 사용한다.
• inorder: parent->left child->right child 순으로 방문한다. 일반적으로 수식을 표현하기 위해서 많이 사용한다. 위의 이진 트리의 경우 b*c+a+d*e+f*g 가된다.

search(x, T)
{
	if (T==null) 
		return null;
	else if(x<T.element)
		return search(x,T.left);
	else if (x>T.element)
		return search(x,T.right);
	else return T;
}

1. Internal Path Length D(n)을 tree에 있는 모든 노드들의 깊이의 합으로 정의한다. D(0)=D(1)=0 이다.
2. D(i)와 D(n-i-1)을 left와 right subtree의 Internal Path Length라고 하면, D(n) = D(i)+D(n-i-1)+(n-1)이다.
3. D(i)와 D(n-i-1)의 평균값이다. 그러므로 아래의 공식이 성립한다.

1. 이제 D(n)<4nlogn을 쉽게 정할 수 있을 것이다.

1. 자식 tree의 크기가 Best인 경우 n/2와 n/2로 나누어지고 worst인 경우 0과 n-1로 나누어짐진다.
2. 그러므로 평균적으로 n/4와 3n/4로 나누어진다고 가정할 수 있다.
3. 이중 가장 깊은 것(height가 가증큰)은 3n/4인 서브트리이므로
4. H(1) = 0, H(n)=1+H(3n/4) 이다.
5. 해서 H(n) = 2.4logn = O(long)을 유도할 수 있다.

Insert(x,T)
{
	if(T==null)
	{
		new T;
		T.element = x;
		T.left = t.right = null;
		else if (x<T.element) T.left = insert(x,T.left);
		else if (X>T.element) T.right = insert(x,T.right);
		else "이미 존재";
		return T;
	}
}

delete(x,T)
{
	if(T == NULL) "Error";
	if (x<T.element) T.left = delete(X,T.left);
	else if (X>T.element) T.right = delete(X,T.left);
	// 2 child
	else if (T.left && T.right)
	{
		// find min
		repl = T;
		while(repl.eft != null) repl = repl.left;
		T.element = repl.element;
		T.right = delete(T.element, T.right);
	}
	// 1 child
	else
	{
		tmp = T;
		if (T.left == null) repl = T.right;
		if (T.right == null) repl = T.left;
		free (tmp);
		return repl;
	}
}

1. N(h)를 높이가 h인 AVL에 존재할 수 있는 최소 노드의 갯수라고 정의하면
2. N(0) = 1, N(1) = 2 이다.
3. N(h) = N(h-1)+N(h-2)+1 이므로 아래의 공식이 성립된다.

1. 그러므로 h=log_1.618^n=O(logn) 이 된다.

single_rotate_left(n2)
{
	n1 = n2.left	
	n2.left = n1.right;
	n1.right = n2;
	n2.height = max(n2.left.height, n2.right.height)+1;
	n1.height = max(n1.left.height, n1.right.height)+1;
	return n1;
}

docuble_rotate_left(n3)
{
	n1 = n3.left
	n3.left = single_roate_right(n3.right);
	return single_roate_left(n3);
}

insert(x,T)
{
	if(T == NULL) new T;
	else if(x<T.element)
	{
		T.left = insert(x, T.left);
		if((T.left.height - T.right.height) == 2)
		{
			if (x<t.left.element) 
				T=single_roate_left(T);
			else
				T=double_roate_left(T);
		}
		else 
			T.height = max(T.left.height, T.right.height)+1;

	}
	else if (x>T.element)
	{
		// 위코드와 동일
	}
	else "Error";
	return T;
}