tree

[자료구조] 트리, AVL 트리

AVL Tree (AVL은 발명자 세명의 이름에서 따왔다) 자가 균형 이진 탐색 트리. 이진 탐색 트리에서, 노드들이 삽입시 한쪽으로 편향되면 결국 탐색에서 O(N)의 시간이 걸리게 된다. * 그림 : 편향트리. 이진 탐색 트리의 편향트리를 극복하기 위해 재구성(회전, Rotate)을 통해 트리를 균형있게 만든다. AVL 트리는 다음과 같은 특징을 가진다. 이진 탐색 트리(BST)의 속성을 가진다. 왼쪽, 오른쪽 서브 트리의 높이차이가 최대 1이다. 삽입, 삭제 등 어떤 시점에서 높이 차이가 1보다 커지면 회전(Ratation)을 통해 균형을 맞춰 높이를 1로 맞춘다. AVL 트리는 높이를 logN으로 유지하기 떄문에 삽입, 검색 ,삭제의 시간 복잡도는 O(log N) 이다. AVL 트리는 균형이 무너졌..

[자료구조] 트리, 레드블랙 트리 (Red-Black-Tree)

Red-Black Tree Binary Search Tree를 기반으로 하는 자료구조. 동일한 노드의 개수일 때, depth를 최소화하여 시간 복잡도를 줄이는 것이 핵심 아이디어. 연산 삽입 insert : O(lon N) 조회 search : O(log N) 삭제 delete : O(log N) 정의 레드 블랙 트리는 다음의 성질들을 만족하는 BST(이진 탐색 트리) 이다. 모든 노드는 Red(빨강) or Black(검정) 의 색을 갖는다. 루트 노드는 검정색이다. 모든 리프 노드들은 검정색이다. 레드 노드의 자식은 모두 검정색이다 모든 리프 노드에서 Black Depth는 같다. 리프노드에서 루트 노드까지 가는 경로에서 만나는 검은색 노드의 개수가 같다. 각 노드에 대해서 노드로부터 descendan..

[자료구조] 트리와 이진트리, 이진탐색트리(BST)

트리 그래프와 트리, 그리고 BST 87 균형잡힌 트리 : AVL 트리, 레드블랙트리 88 트리는 스택이나 큐, 어레이 같은 선형 자료구조가 아닌 비선형 자료구조. 계층적 관계(hierarchical RelationShip)을 표현하는 자료구조 트리는 표현에 집중한다 무엇인가를 저장하고 꺼내야한다는 사고에서 벗어나 트리라는 자료구조를 보자 트리를 구성하고 있는 요소들 Node (노드) : 트리를 구성하는 각각의 요소 Edge (간선) : 트리를 구성하기 위해 노드와 노드를 연결하는 선 Root Node(루트 노드) : 최상위에 있는 노드 Leaf Node(Terminal Node, 단말 노드) : 하위에 자식 노드가 연결되어 있지 않은 노드 내부 노드(Internal Node, 비단말 노드) : 단말 노..