10.선택트리, 숲, 이진트리개수 11.이진탐색트리(BS),Splay,AVL,BB

선택트리

 

승자트리 

 - 각 노드가 두 자식노드의 작은값을 갖는 완전이진트리

- 작은 값이 승자가 되어 올라가는 토너먼트와 유사

- 루트값이 트리에서 가장 작은 값이 됨

 

11이 삭제가되면 24가 22랑 겨뤄서 작은값이 올라오면 된다.

 

 

 

패자트리

-루트노드위에 최상위 0번 노드를 놓음 - 최종승자를 저장함

-잎 노드들이 각 리스트의 head를 가리킴

-트리의 각 내부노드에는 승자가 아닌 패자를 저장함

-패자를 부모노드에 저장(큰값) 승자는 부모의 부모노드로 올라가서 다시 경쟁)

-루트에는 마지막 패자(두번째 작은 값)를 저장하고 최종승자(가장 작은값)를 0번 노드에 저장

 

두개 비교해서 작은애가 승자니까 큰값은 적고 작은애를 올려보냄 즉  한번 더올라감(부모의 부모로)

 

0번 노드에 최소값이 있으므로 이 값을 제거하여 전체리스트에 저장함

제거된 값을 가지고있던 4번 리스트의 헤드에 있던 24를 올려서  바로 22인 부모와 비교함

 

패자트리가 승자트리보다 프로그래밍이 효율적이다.

 

 

숲

- 분리된 트리 모임

- 0개 이상의 분리된 트리 집합

 

 

 

 

 

 

 

이진트리개수

 

 

 

11강.

 

BS트리(이진탐색트리)

 

 

 

 

 

Splay 트리 - 자주 탐색하는 키를 가진 노드를 트리의 루트에 가깝게 놓는다.

 

BS트리의 탐색성능을 높이려면 균형이 잘 맞아야함 그래서 균형을 잘 맞추자는 얘기

각 노드에 대해 왼쪽 과 오른쪽 서브트리가 가능한 한 같은 수의 노드를 갖게 한다.

 

AVL트리-  왼쪽서브트리높이와 오른쪽서브트리높이가 최대 1차이

 

BB트리-

Q3

트리의 무게는 무엇인가 ?

 

1

차수가 2인 노드의 갯수

2

루트부터 입 노드까지의 경로에 존재하는 노드의 갯수

3

트리에 속한 잎 노드의 개수

4

같은 부모에 대한 자식의 높이 차이