트리의 정의에 대해서..
글쓴이: 녹차 / 작성시간: 일, 2007/07/01 - 11:36오전
어디에 올릴 지 몰라서 자유게시판에 올려봅니다.
알고리즘 책 4권을 눈 앞에 펼쳐두고 보고 있는데, 트리의 정의가 책마다 다르며,
트리의 깊이라던지 높이 또한 다르더군요.
제가 알고 있는 트리의 정의는 무방향, 연결된, 사이클이 없는 그래프로 알고 있는데
일부 책에서는 루트가 존재해야 하며 뭐 이런 식으로 설명을 했네요.
그리고 깊이의 경우도 책 마다 정의가 다릅니다.
이 경우 높이가 4라는 책이 있는 반면, 3이라는 책이 있습니다.
과연 어떤 것이 맞는 걸까요? 인터넷을 찾아봐도 뭐 뒤죽박죽 입니다.
다만 우리 나라 사이트에서는 압도적으로 높이가 4라는 의견이 많습니다만
외국 사이트에서는 높이가 3이라는 게 많군요. 위키피디아에서도 그렇게 나오고요.
어떤 정의가 올바른 걸까요? 제가 배울 때는 높이가 4라고 배웠습니다. 잘못된 교재를 가지고 배운 건지 그런 생각이 드네요.
Forums:
트리가
트리가 무방향인가요?
트리는 언제나 부모 자식의 관계를 갖기 때문에 방향성이 있다고 알고 있었는데
무방향이라면 혹시 그래프용 자료구조중에 있는거 아닌가요?
높이가 4라는 건 vertex
높이가 4라는 건 vertex 기준이고,
높이가 3이라는 건 edge 기준······,
맞나요?
“무방향, 연결된, 사이클이 없는 그래프”는
어떤 vertex가 루트가 되든 상관이 없지요.
그 중 한 경우가 되면
부모·자식 관계가 확실해지므로 방향성이 생기는 게 아닌가요?
이것도 맞고 저것도 맞다는 식으로 조금 유연한 해석을 해봤습니다. :)
음..
::::::::::: 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이네요.