이야기박스

스플레이 트리트리의 노드가 탐색 또는 갱신을 위해 접근된 후, 스플레이되는 이진 탐색 트리를 말합니다. * 노드가 스플레이 된다 = 노드를 루트로 이동시킨다 - 사용되는 환경에 따라 재조정되는 방식==> 트렌드를 반영하는 이진트리라 할 수 있습니다. 스플레이 트리의 장점1. 구현이 단순합니다. ( AVL 트리 같은 경우는, 균형을 유지하기 위해 복잡했는데 스플레이 트리는 이것이 필요 없습니다. ) 2. 탐색, 삽입, 삭제에 O(log n)의 실행시간을 제공합니다. 3. 각 항목에 대한 접근빈도가 불균등한 사전에 사용하면 유리합니다.( locality의 개념을 생각하시면 되겠습니다. ) 스플레이 하는 시점1. 탐색 - 키가 발견되면, 그 노드를 스플레이- 발견되지 않으면, 실패한 외부노드의 부모노드를 스플..

알고리즘 카테고리의 AVL 트리 게시글의 내용으로 코드 작성하였습니다. 최대한 트리 모양으로 출력하려고 했는데, UI 프로그램을 쓰지않고 콘솔로 하려니 어렵군요.좀 비슷하게 흉내내 봤는데, 조금만 트리가 커지면 깨집니다.그러니까 크게 믿지말고 참고만 하고 쓰세요. ( 트리 모양 출력 부분 ) 출력을 제외한 AVL 트리 로직은 맞을 거에요 (아마 ㅎㅎ) 코드 - AVL.h #pragma once #include #include #include #include using namespace std; // 노드 정보 typedef struct Node { Node *parent = nullptr; Node *leftc = nullptr; Node *rightc = nullptr; int data = NULL; ..

AVL Tree이진 탐색 트리의 경우, 운이 나빠 편향트리가 형성이 되면 O(n)의 시간복잡도를 가지게 됩니다.그렇기에 좌우 높이차가 1이 넘지 않는 트리를 만드는데, 이것이 AVL 트리입니다. 주의할 점삽입, 삭제가 이루어지는 경우, AVL 트리의 균형속성이 파괴될 수 있습니다. 이런 경우, 불균형을 찾아서 해소해주어야 합니다. 때문에 두가지 필요한 매서드가 있습니다.1. 균형검사 (balance check)2. 개조 (restructure) 회전 : 회전 요령은 자동차 핸들을 생각하시면 됩니다.L - 반시계 방향으로 회전R - 시계 방향으로 회전 단일회전 이중회전 모든 회전 후 ** 개인적 견해 : LL, RR, LR, RL 이렇게 정의를 하는데, 개인적으로는 그냥 이해하고 하는 것이 더 쉽다.이 용..

RAID 0- 스트라이프(Stripe)- 두 개 이상의 하드 디스크를 병렬로 연결하여 하나의 하드 디스크처럼 이용- 예 : 데이터 123456을 하드디스크 A, B에 저장--> A : 1 3 5 저장--> B : 2 4 6 저장 - 사용 이유--> 원형 판이 돌아갈 때, 너무 빠르기 때문에 인접하게 저장되지 않음--> 그렇기 때문에 각기 다른 판에 저장하며 지연 시간을 최소화 함--> 속도 개선이 생김 - 두 개를 연결했다고 속도가 두배가 되는 것은 아님 (대략 1.5배) RAID 1- Mirror- 두 개 이상의 하드디스크를 병렬로 연결하여 똑같은 복사본 생성- 에러 발생시 하드 디스크를 교체함으로서 해결 RAID 0+1(01) , 1+0(10)- stripe + mirror- 둘의 장점을 어느정도 구..

안녕하세요~ 알고리즘 탐색 부분으로 넘어왔습니다. 알고리즘 게시판에서 이진 검색을 포스팅 했는데요 이건 트리 ADT를 이용하여 검색하는 코드를 작성하였습니다. ○ 코드 특징 - 중복을 허용하지 않음 - 이진 트리 형식 - 완전 이진트리는 아닙니다. - 모듈화가 잘되어 있지 않습니다. (대충대충.. 멘붕상태로 함.. ) ○ 코드 - BinaryTree.h #pragma once #include using namespace std; class BinaryTree { BinaryTree *leftc; BinaryTree *rightc; int data; public: BinaryTree(); BinaryTree(int elem); void setChild(BinaryTree *child); int getDat..

얼핏보면 분할통치법을 쓸것 같지만 아닙니다!분할 통치법은 양쪽으로 나눈 후, 모두 다루고 다시 합치지만이진 탐색 트리는 양쪽으로 나눈 후 한쪽은 안씁니다!! ㅎㅎ합치지도 않구요 !! ㅎㅎ 이진 탐색 트리의 핵심key (left child) O(n)최선의 경우 - 좌우 대칭인 경우 --> O(log n) 코드는 코드 게시판에 올릴게요~

§ n log n 은 어떻게 나오는 것일까 정렬은 하는 과정은 완전 이진트리 형태의 결정트리(Decision Tree) 형태로 표현할 수 있습니다.--> 비교를 수행 후, 결과에 따라 좌우 부트리 중 한쪽 부트리로만 순회하는 형태 n개의 잎이 존재하는 포화이진트리의 높이는 최소 log (n+1) 인 것은 다들 아시겠죠그렇다면 n! 개의 잎이라면? log n! ==> 어떠한 비교 알고리즘도 최소 log(n!) 시간을 소요 한다는 것을 알 수 있습니다.이를 수학적으로 유도하면 log(n!) = log( n * (n-1) * (n-2) *....* 3 * 2 * 1 )>= log(n * (n-1) * .... * (n/2) )>= log( (n/2) * (n/2) * (n/2) *...* (n/2) ) = l..

귀찮아서 미루고 미루다, 이제야 작성하네요이걸로 정렬은 끝나고 다른 알고리즘들을 다루어야겠습니다 ㅎㅎ정렬 알고리즘 전체 코드는 코드 게시판가면 있어요 (c++로 작성했음) § 퀵 정렬 (Quick Sort) 퀵 정렬 또한 분할통치법을 이용한 알고리즘입니다.퀵 정렬의 핵심은 피벗(Pivot) 입니다. 여기서 피벗이란?기준점입니다.무조건 이걸 피벗으로 써야한다! 하는 기준은 없고, 각자 편한대로 정해주시면 됩니다.단, 피벗에 따라 수행시간에 차이가 생길 수 있으니 그건 고려하면서.. 간단히 말하면 퀵 정렬은 이 피벗을 기준으로 작은 것은 왼쪽으로, 큰 것은 오른쪽으로 몰아 넣는 방식입니다. ○ 과정1. 분할 (divide)- LT (피벗보다 작은 원소들)- EQ (피벗과 같은 원소들)- GT (피벗보다 큰 ..