이진 나무 구조 강윤섭 2008년 5월 23일.

Presentation on theme: "이진 나무 구조 강윤섭 2008년 5월 23일."— Presentation transcript:

1 이진 나무 구조 강윤섭 2008년 5월 23일

2 목차 이진 나무 구조란? 나무의 원소 나열 앞순위 나열 안순위 나열 뒷순위 나열 이진 검색 나무 구조 삽입 삭제 검색

3 이진 나무 구조 여러 개의 자료를 표현하는 자료구조 잎(Leaf)와 가지(Node)로 이루어짐.
가지가 언제나 2개의 작은 나무를 포함하는 경우에 이진 나무 구조(Binary tree)라고 함. type ‘a tree = Leaf | Node of ‘a tree * ‘a * ‘a tree

4 이진 나무 구조 – int tree Leaf Node (Leaf, 1, Leaf)
Node (Leaf, 1, Node(Leaf, 2, Leaf)) 1 1 2

5 이진 나무 구조 – int tree Node( Node(Leaf, 2, Leaf), , Node(Leaf, 3, Node(Leaf, 4, Leaf))) 1 2 3 4

6 앞순위 나열 나무 구조 Node (L, v, R) 이 주어졌을 때, v를 먼저 나열하고, 그 다음에 L의 원소, R의 원소 순으로 나열하는 방식. [2; 1; 4; 3; 5] 2 1 4 5 3

7 뒷순위 나열 나무 구조 Node (L, v, R) 이 주어졌을 때, L의 원소, R의 원소 순으로 먼저 나열하고 맨 나중에 v를 나열하는 방식. [1; 3; 5; 4; 2] 2 1 4 5 3

8 안순위 나열 나무 구조 Node (L, v, R) 이 주어졌을 때, L의 원소, v, 그리고 R의 원소 순으로 나열하는 방식.
[1; 2; 3; 4; 5] 2 1 4 5 3

9 preorder 이진 나무를 받아서 나무의 원소들을 앞순위 나열한 리스트를 계산하는 함수 preorder를 작성하라.
# preorder;; - : 'a tree -> 'a list = <fun> # preorder Leaf;; - : 'a list = [] # preorder (Node( Node(Leaf, 1, Leaf), 2, Node(Node(Leaf, 3, Leaf), 4, Node(Leaf, 5, Leaf))));; - : int list = [2; 1; 4; 3; 5]

10 postorder 이진 나무를 받아서 나무의 원소들을 뒷순위 나열한 리스트를 계산하는 함수 postorder를 작성하라.
# postorder;; - : 'a tree -> 'a list = <fun> # postorder Leaf;; - : 'a list = [] # postorder (Node( Node(Leaf, 1, Leaf), 2, Node(Node(Leaf, 3, Leaf), 4, Node(Leaf, 5, Leaf))));; - : int list = [1; 3; 5; 4; 2]

11 inorder 이진 나무를 받아서 나무의 원소들을 안순위 나열한 리스트를 계산하는 함수 inorder를 작성하라.
# inorder;; - : 'a tree -> 'a list = <fun> # inorder Leaf;; - : 'a list = [] # inorder (Node( Node(Leaf, 1, Leaf), 2, Node(Node(Leaf, 3, Leaf), 4, Node(Leaf, 5, Leaf))));; - : int list = [1; 2; 3; 4; 5]

12 preorder let rec preorder t = match t with | Node (l, v, r) -> v :: ((preorder (preorder r)) | Leaf -> [] ;;

13 postorder let rec postorder t = match t with | Node (l, v, r) -> (postorder (postorder [v] | Leaf -> [] ;;

14 inorder let rec inorder t = match t with | Node (l, v, r) -> (inorder (inorder r) | Leaf -> []

15 이진 검색 나무 나무 구조 Node (L, v, R) 이 주어졌을 때, L에는 v보다 작은 원소만, R에는 v보다 큰 원소만 들어가 있는 나무 구조. 여러 개의 자료 중에 원하는 것을 빠르게 찾아낼 수 있다. x <x >x

16 삽입 나무 구조 Node (L, v, R) 에 새 원소 x를 추가하기. x가 v보다 크면 R에, v보다 작으면 L에 넣는다.
v와 x가 같으면 추가하지 않는다. v <v >v x

17 insert 이진 검색 나무에 새 원소를 추가하는 함수 insert를 작성하라.
# insert;; - : 'a tree -> ‘a -> 'a tree = <fun> # insert Leaf 1;; - : int tree = Node (Leaf, 1, Leaf) # insert (Node (Node(Leaf, 1, Leaf), 3, Node(Node(Leaf, 5, Leaf), 6, Leaf))) 4;; - : int tree = Node (Node (Leaf, 1, Leaf), 3, Node (Node (Node (Leaf, 4, Leaf), 5, Leaf), 6, Leaf))

18 insert let rec insert t x = match t with | Node (l, v, r) -> if x = v then t else if x < v then Node(insert l x, v, r) else Node(l, v, insert r x) | Leaf -> Node(Leaf, x, Leaf) 18 18

19 찾기 나무 구조 Node (L, v, R) 에서 원소 x를 찾기.
x가 v보다 크면 R에서, v보다 작으면 L에서 x를 찾는다. v와 x가 같으면 찾았다고 보고한다. (Some x) 못 찾은 경우에는 없다고 보고한다. (None) type ‘a option = Some of ‘a | None

20 search 이진 검색 나무에서 값을 찾는 함수 search를 작성하라.
# search;; - : 'a tree -> ‘a -> 'a option = <fun> # search Leaf 1;; - : int option = None # search (Node (Node(Leaf, 1, Leaf), 3, Node(Node(Leaf, 5, Leaf), 6, Leaf))) 5;; - : int option = Some 5

21 search let rec search t x = match t with | Leaf -> None | Node (l, v, r) -> if v = x then Some x else if v > x then search l x else search r x ;;

22 검사 나무 구조 Node (L, v, R) 이 정상적인 이진 검색 나무 구조인지 검사한다. v
L은 이진 검색 나무이며, L의 모든 원소는 v보다 작다. R은 이진 검색 나무이며, R의 모든 원소는 v보다 크다. Leaf 하나뿐인 나무 구조는 정상적인 이진 나무 구조이다. v <v >v

23 check_smaller & check_larger
주어진 이진 나무의 원소들이 모두 어떤 값보다 작으면서 이진 검색 나무 구조의 조건을 만족하는지 검사하는 함수 check_smaller와 더 큰지 검사하는 check_larger를 작성하라. 모든 원소가 x보다 작은 이진 검색 나무 Node(L, v, R)은 아래의 조건을 만족한다. v는 x보다 작다. L은 이진 검색 나무이며, L의 모든 원소는 v보다 작다. R은 이진 검색 나무이며, R의 모든 원소는 v보다 크다. R은 이진 검색 나무이며, R의 모든 원소는 x보다 작다. 단, Leaf는 이진 검색 나무이다.

24 check_smaller & check_larger
let rec check_smaller t x = (내용) and check_larger t x = (내용) ;; # check_smaller;; - : 'a tree -> 'a -> bool = <fun> # check_larger;; - : 'a tree -> 'a -> bool = <fun> # check_smaller (Node (Node (Leaf, 1, Leaf), 3, Node (Leaf, 5, Leaf))) 6;; - : bool = true # check_smaller (Node (Node (Leaf, 1, Leaf), 3, Node (Leaf, 5, Leaf))) 4;; - : bool = false

25 check_smaller & check_larger
let rec check_smaller t x = match t with | Leaf -> true | Node (l, y, r) -> y < x && check_smaller l y && check_larger r y && check_smaller r x and check_larger t x = match t with | Leaf -> true | Node (l, y, r) -> y > x && check_smaller l y && check_larger r y && check_larger l x ;;

26 check 주어진 이진 나무가 이진 검색 나무 구조의 조건을 만족하는지 검사하는 함수 check을 작성하라. 이진 검색 나무 Node(L, v, R)은 아래의 조건을 만족한다. L은 이진 검색 나무이며, L의 모든 원소는 v보다 작다. R은 이진 검색 나무이며, R의 모든 원소는 v보다 크다. 단, Leaf는 이진 검색 나무이다. # check;; - : 'a tree -> bool = <fun>

27 check let check t = match t with | Leaf -> true | Node (l, v, r) -> check_smaller l v && check_larger r v ;;