Binary Search Trees(2)

Array Implementation

Binary Search Tree는 Array로 표현할 수 있다.

Binary Tree

위와 같은 Binary Tree는 다음과 같이 표현할 수 있다.

Array Implementation

현재 있는 position number를 r이라고 하자.

그렇다면 그 position의 parent와 child, sibling은 다음과 같다

• Parent(r) = floor((r-1)/2)
• Leftchild(r) = 2r+1
• Rightchild(r) = 2r+2
• Leftsibling(r) = r-1
• Rightsibling(r) = r+1

 

BST and Traversal

앞의 게시글에서 나왔던 Traversal들 중 inorder traversal를 BST에 적용하면 정렬이 된 순서로 element를 얻을 수 있다.

 

BST

Inorder Traversal

Inorder Traversal은 left subtree를 먼저 지나간다. BST에서 left subtree는 현재의 node보다 작은 값들만 존재하기에 첫 시작은 최솟값부터 시작할 것이다.

그 다음 현재 node는 right subtree보다 작지만 left subtree보다는 크기 때문에 left subtree에서 제대로 traversal를 하였다면 현재 노드의 순서는 적절한 위치에 올 것이고, 그 다음 right subtree를 traversal하기 때문에 BST에서 inorder traversal를 하게 되면 정렬된 순서의 values를 얻을 수 있다

 

 

 

출처 : 서울대학교 컴퓨터공학부 강유 교수님 자료구조 수업