이진 트리

Article on other languages:

• Двоично_дърво
• Binární_strom
• Binärbaum
• Binary_tree
• Duuma_arbo
• Árbol_binario
• Binääripuu
• Arbre_binaire
• עץ_בינארי
• Pohon_biner
• Tvíundartré
• Albero_binario
• 二分木
• Drzewo_binarne
• Árvore_binária
• Arbore_binar
• Двоичное_дерево
• Binárny_strom
• Dvojiško_drevo
• Бинарно_стабло
• Binärträd
• Бінарне_дерево
• 二叉树

	del.icio.us
	Digg
	Furl
	Reddit
	Rojo
	Add to OnlyWire

전산학에서 이진 트리 (binary tree)란 한 노드가 최대 두 개의 자식 노드를 가지는 트리를 뜻한다. 그래프 이론에서 그래프의 특별한 형태를 우리는 이진트리로서 표시한다.

이진 트리는 빈 트리이거나 하나의 자식노드 또는 왼쪽과 오른쪽 자식노드를 가진 루트노드로 구성되며, 이 자식 노드는 내부 노드가 될 수 있다.

루트노드에서 시작한 각 노드는 최대한 두개의 자식 노드를 가질수 있으며,그 자식노드는 정확히 왼쪽과 오른쪽노드로 분할할 수 있다.

특징

h(>=0)를 높이, n을 노드 수, i(>=0)를 레벨이라고 할 때 이진 트리는 다음과 같은 특징이 있다.

1. n = (외부노드 = 잎노드) + (내부노드).
2. (외부노드) = (내부노드) + 1.
3. (노드 on level-i) <= 2^i
4. h + 1 <= (외부노드) <= 2^h
5. log(외부노드) <= h
6. h + 1 <= (외부노드) <= 2^h

이진 트리

이 글은 컴퓨터에 관한 토막글입니다. 서로의 지식을 모아 알차게 문서를 완성해 갑시다.