데니의 Techlog

JAVA로 구현한 링크트리스트 소스 코드는 다음과 같다. class Node { Object data; Node next_node; Node(Object obj) { this.data = obj; this.next_node = null; } } Node클래스다. 기본적으로 데이터가 들어갈 부분과 Next Node로 이루어져 있으며 어떤 데이터 타입이 들어올지 모르기 때문에 Object타입으로 클래스를 정의하였다. public class LinkedList { private Node head; private Node tail; private int size = 0; Linked List 클래스이다. head 노드와 tail 노드, 그리고 리스트의 크기를 나타내는 변수가 있다. 기본적으로 리스트 생성 시 노..

Binary Search Tree의 최악의 상황에 대해서도 균형된 시간 복잡도가 나올 수 있도록 새롭게 고안된 Balanced Binary Search Tree다. 즉, 최악의 경우 (한쪽에만 노드가 일렬로 정렬된 경우) 가 나오지 못하도록 제약 조건을 걸고 있다. [제약 조건] 1. Root Property : 루트 노드의 색은 검정(Black)이다. 2. External Property : 모든 외부 노드들은 검정(Black)이다. 3. Internal Property : 빨강(Red)노드의 자식은 검정(Black)이다. == No Double Red(빨간색 노드가 연속으로 나올 수 없다.) 4. Depth Property : 모든 리프노드에서 Black Depth는 같다. == 리프노드에서 루트노드..