트리의 정의에 대해서..

녹차의 이미지

어디에 올릴 지 몰라서 자유게시판에 올려봅니다.
알고리즘 책 4권을 눈 앞에 펼쳐두고 보고 있는데, 트리의 정의가 책마다 다르며,
트리의 깊이라던지 높이 또한 다르더군요.

제가 알고 있는 트리의 정의는 무방향, 연결된, 사이클이 없는 그래프로 알고 있는데
일부 책에서는 루트가 존재해야 하며 뭐 이런 식으로 설명을 했네요.
그리고 깊이의 경우도 책 마다 정의가 다릅니다.

이 경우 높이가 4라는 책이 있는 반면, 3이라는 책이 있습니다.

과연 어떤 것이 맞는 걸까요? 인터넷을 찾아봐도 뭐 뒤죽박죽 입니다.
다만 우리 나라 사이트에서는 압도적으로 높이가 4라는 의견이 많습니다만
외국 사이트에서는 높이가 3이라는 게 많군요. 위키피디아에서도 그렇게 나오고요.

어떤 정의가 올바른 걸까요? 제가 배울 때는 높이가 4라고 배웠습니다. 잘못된 교재를 가지고 배운 건지 그런 생각이 드네요.

geneven의 이미지

트리가 무방향인가요?
트리는 언제나 부모 자식의 관계를 갖기 때문에 방향성이 있다고 알고 있었는데
무방향이라면 혹시 그래프용 자료구조중에 있는거 아닌가요?

gamdora의 이미지

높이가 4라는 건 vertex 기준이고,

높이가 3이라는 건 edge 기준······,

맞나요?

“무방향, 연결된, 사이클이 없는 그래프”는

어떤 vertex가 루트가 되든 상관이 없지요.

그 중 한 경우가 되면

부모·자식 관계가 확실해지므로 방향성이 생기는 게 아닌가요?

이것도 맞고 저것도 맞다는 식으로 조금 유연한 해석을 해봤습니다. :)

kksir의 이미지

::::::::::: Easy come, Different go.
::::::::: Http://www.geekstep.org

::::::::::: Easy come, Different go.
::::::::: Http://www.geekstep.org

녹차의 이미지

좀 더 찾아보니 일반적으로 부르는 트리는 것은 free tree를 생략해서 부르네요.
http://www.nist.gov/dads/HTML/freetree.html

그리고 루트가 존재하는 것은, rooted tree라고 부릅니다.
http://www.nist.gov/dads/HTML/rootedtree.html

rooted tree의 경우에는 부모 자식 간의 관계를 가지므로 방향성을 가진다고 위키피디아에 나오네요.
http://en.wikipedia.org/wiki/Binary_tree

알고리즘 책을 이것저것 찾아보니, 잘못된 내용이 담겨져 있는 책이 좀 많아 보입니다.
full binary tree와 perfect binary tree를 잘못 설명한 책도 보이구요.

위 그림에서 높이는 3이네요.