(self-balanced) Tree

algorithm & type 2016. 7. 21. 16:58

<Self-Balanced Tree>

B-Tree: 2개 이상의 child를 가짐..

ㅁ 2-3 B-Tree (I think - 2 max, 3 Node)

Every non-leaf node has either 2 or 3 children.
All leaves are at the same depth.
Information (keys and associated data) is stored only at leaves
부모는 leftMax, middleMax를 저장. (left children's Max, middle children's Max)

non-leaf nodes have 2 or 3 children (never 1 )
Insert Operations: (value k)
(2가지 예외)
- T is empty일 때, 싱글 node with k 생성.
- T is 1 node(m) 일 때 : (1 parent, 2 child node로)
=> 1.node(n)k포함 생성,
2.new 내부node (with n,m are child node) 생성
+ leftMax,middleMax 세팅.
(general)
- insert(T,k)

ㅁ 2-3-4 Tree : 3개의 data와 4개의 child node를 가질 수 있다.

<Self-Balanced Binary Tree>

Red-Black Tree: Ref1 ,

root는 블랙노드

레드노드(temp노드)가 항상 블랙child를 가짐.
삽입시에 레드노드를 삽입하는데, 레드-레드 될 경우 회전으로 해결.

특징: 최장거리 노드도 최단거리의 2배가 이하임.

AVL Tree: Refwiki - Height balanced 이진트리 - 각 two child간의 depth가 1 밖에 차이가 안남.
- depth가 좋으 므로 Red-Black Tree보다 탐색속도가 좋음.

- 특징: 4가지 회전 방식이 존재함 (할아버지 노드까지만 보면 됨)

LL/RR은 한번만 회전. LR/RL은 2번 회전.

Splay Tree

- self balanced이면서 속도도 빠름. 이 역시 위 둘과 같이 회전으로 balancing.

- 최근 access한 값을 다시 access 할 수 있도록 배치.

- cache나 gc에 자주 쓰임.

- zig (parent root, x is child) , zig-zig (p!=root, p,x 같은 방향), zig-zag (p!=root p,x다른 방향) case 존재.

[기본 회전 알고리듬] Ref

Root Pv C A B

Pivot = Root.OS  (O=Opposite side)     Pivot설정.                     
Root.OS = Pivot.RS  (R= Rotate side)     Pivot.RS를 1.detach                     
Pivot.RS = Root                          Pivot.RS를 2.Set                                    
Root = Pivot                           Root설정.

회전시 left,right가 계속 바뀌므로 java reflection을 쓰면 좋을 것 같네요.

left, right child를 이름으로 가져오게... reflection REF

Class aClass = MyObject.class
Field field = aClass.getField("someField");

//for node : MyObject node = new MyObject();
Object value = field.get(node);
field.set(node, value);

Cartesian Tree ref1txt

- Heap Tree와 비슷하게 min(or max)값이 제일 위에 있으나, complete tree가 아님.

- 한번 구성하면 끝날 듯( self balanced가 아님)

KD Tree : k dimensional Tree이다. left-child에 tree하나, right-child에 tree하나 가 관리되는데..
recurive하게 여러개의 tree가 계속 관리될 수 있다.

Huffman Tree: 압축알고리듬 허프만 코드- (확률빈도가 높은 char을 짧은 bit로 관리하는 코드 방식. )
를 생성할때 사용하는 binary Tree이다.

왼쪽이 0, 오른쪽이 1 간단하다. 빈도수가 낮은것부터 밑에서 tree를 만든다.

Heap Tree: complete binary tree (즉 포화트리에서 마지막 자식은 왼쪽노드부터 채움)

- heap Tree Java 알고리듬:

k 의 parent는 k/2; k의 2자식은 2k 와 2k + 1. (array로 구현하고 첫자리를 비움. array size는 2^(h+1) 이 되겠죠.)

최상위 root에는 최소값(Min Heap)이나 최대값(Max Heap)을 관리.

- complete binary tree는 배열로 관리 가능함. h로 관리되겠죠. 2^(h+1) -1 개가 max 노드개수임.

-Priority Queue 가 Heap으로 구현됨. (단, 이 때는 중복 허용)