shopkeeper/korean_wiki_content_only_120125 huggingface dataset:
이후 다리우스 1세(Darius Hystaspis)가 페르시아 왕권을 장악하고, 페르시아를 조로아스터의 대리인으로 다스리게 될 때까지, 바빌론은 서아시아의 지배자로서 권위를 인정받게 된다. 다리우스는 정복자로서 바빌론에 입성하였다.
기원전 514년경 바빌론의 아라카(Arakha)가 다시 봉기하지만, 이때 방벽 일부가 파괴된다. 벨의 거대 사원인 에-사길라는 계속해서 보수되면서 바빌로니아의 상징으로 유지되지만, 마침내 바빌로니아의 새 수도 셀레우키아가 건설되면서 많은 인구들이 이동하게 되고, 바빌론 성은 석재로 이용되기 위해 손상되고 말았다.
지구의 날 또는 어스데이()는 1970년 4월 22일 미국의 상원의원 게이로 닐슨(, 1916년 6월 4일 – 2005년 7월 3일)이 하버드 대학생 데니스 헤이즈(, 1944년- )와 함께 1969년 1월 28일 캘리포니아 산타 바바라에서 있었던 기름유출 사고를 계기로 지구의 날 선언문을 발표하였고 행사를 주최한 것에서 비롯된 기념일이다. 행사에서 2000만 명 이상의 사람들이 행사에 참가해 연설을 듣고, 토론회를 개최하며, 환경을 깨끗이 하기 위한 실천적인 행동을 하였다. 특히, 뉴욕 5번가에서는 자동차의 통행을 금지시키고 60만 명 이상의 사람들이 센트럴파크에서 열리는 환경집회에 참여했다.
2025년 기준, 지구의 날은 55주년을 맞이했다
육장장이 행사.
2006년 지구의 날 서울조직위원회에 따르면 184개국 약 50,000여 개의 단체가 행사에 참여하였다.&lt;ref&gt;2006년 지구의날 서울조직위원회
레드-블랙 트리(red-black tree)는 자가 균형 이진 탐색 트리(self-balancing binary search tree)로서, 대표적으로는 연관 배열 등을 구현하는 데 쓰이는 자료구조다. 1978년 레오 귀바스(Leo J. Guibas)와 로버트 세지윅이 1972년 루돌프 바이어가 창안한 "대칭형 이진 B-트리"를 발전시켜 만들었다. 레드-블랙 트리는 복잡한 자료구조지만, 실 사용에서 효율적이고, 최악의 경우에도 상당히 우수한 실행 시간을 보인다: 트리에 n개의 원소가 있을 때 O(log "n")의 시간복잡도로 삽입, 삭제, 검색을 할 수 있다.
레드-블랙 트리는 이진 트리의 특수한 형태로서, 컴퓨터 공학 분야에서 숫자 등의 비교 가능한 자료를 정리하는 데 쓰이는 자료구조이다. 이진 트리에서는 각각의 자료는 '노드(node, 분기점)'에 저장이 된다. 자료를 트리 구조로 저장할 때, 노드들 중 최상위에 있는 노드를 루트 노드(root node)라고 부른다. 이진 트리에서 노드는 최대 두 개의 자식 노드를 가질 수 있다. 각각의 자식 노드도 역시 최대 두 개의 자식 노드를 가질 수 있으며, 이런식으로 계속 연결된다. 그러므로, 어떤 트리도 루트 노드로부터 그 트리에 속한 모든 노드에 도달할 수 있다.
어떤 노드에 자식 노드가 없다면, 그 노드를 리프 노드(leaf node)라고 부르는데, 말 그대로 트리의 맨 가장자리에 있기 때문이다. 트리의 노드 중 하나를 루트 노드로 하고 그 자신과 자식 노드들로 이루어진 트리도 동일하게 트리 구조를 가지는데, 이를 부분 트리(sub-tree)라고 한다. 레드-블랙 트리에서는 리프 노드들은 비어있고, 자료를 가지고 있지 않다.
레드-블랙 트리를 포함한 이진 탐색 트리는, 모든 노드에 대해 '자신이 가진 자료는 자신보다 오른쪽에 위치한 부분트리가 가지고 있는 모든 자료보다 작거나 같고, 자신보다 왼쪽에 위치한 부분트리가 가지고 있는 모든 자료보다 크거나 같다'라는 조건을 만족한다. 이런 특성 때문에 특정 값을 빠르게 찾아 낼 수 있으며, 각 구성원소(elements)간의 효율적인 in-order traversal이 가능하다.
용도와 장점.
레드-블랙 트리는 자료의 삽입과 삭제, 검색에서 최악의 경우에도 일정한 실행 시간을 보장한다(worst-case guarantees). 이는 실시간 처리와 같은 실행시간이 중요한 경우에 유용하게 쓰일 뿐만 아니라, 일정한 실행 시간을 보장하는 또 다른 자료구조를 만드는 데에도 쓸모가 있다. 예를 들면, 각종 기하학 계산에 쓰이는 많은 자료 구조들이 레드-블랙 트리를 기반으로 만들어져 있다.
레드-블랙 트리는 함수형 프로그래밍에서 특히 유용한데, 함수형 프로그래밍에서 쓰이는 연관 배열이나 집합(set)등을 내부적으로 레드-블랙 트리로 구현해 놓은 경우가 많다. 이런 구현에는 삽입, 삭제시 O(log n)만큼의 시간이 필요하다.
레드-블랙 트리는 2-3-4 트리와 등장변환이 가능하다(isometry). 다시 말해서, 모든 2-3-4 트리에는 구성 원소와 그 순서(order)가 같은 레드-블랙 트리가 최소한 하나 이상 존재한다는 말이다. 2-3-4 트리에서의 삽입, 삭제 과정은 레드-블랙 트리에서의 색 전환(color-flipping)과 회전(rotation)과 같은 개념이다. 그러므로 실제로는 잘 쓰이지 않지만 2-3-4 트리는 레드-블랙 트리의 동작 과정(logic)을 이해하는 데 많은 도움을 주기 때문에 많은 알고리즘 교과서들이 레드-블랙 트리가 나오기 바로 전에 2-3-4 트리를 소개하고 있다.
특성(Properties).
레드-블랙 트리는 각각의 노드가 "레드" 나 "블랙" 인 "색상" 속성을 가지고 있는 이진 탐색 트리이다. 이진 탐색 트리가 가지고 있는 일반적인 조건에 다음과 같은 추가적인 조건을 만족해야 유효한(valid) 레드-블랙 트리가 된다:
위 조건들을 만족하게 되면, 레드-블랙 트리는 가장 중요한 특성을 나타내게 된다: 루트 노드부터 가장 먼 잎노드 경로까지의 거리가, 가장 가까운 잎노드 경로까지의 거리의 두 배 보다 항상 작다. 다시 말해서 레드-블랙 트리는 개략적(roughly)으로 균형이 잡혀 있다(balanced). 따라서, 삽입, 삭제, 검색시 최악의 경우(worst-case)에서의 시간복잡도가 트리의 높이(또는 깊이)에 따라 결정되기 때문에 보통의 이진 탐색 트리에 비해 효율적이라고 할 수 있다.
왜 이런 특성을 가지는지 설명하기 위해서는, 네 번째 속성에 따라서, 어떤 경로에도 레드 노드가 연이어 나타날 수 없다는 것만 알고 있어도 충분하다. 최단 경로는 모두 블랙 노드로만 구성되어 있다고 했을 때, 최장 경로는 블랙 노드와 레드 노드가 번갈아 나오는 것이 될 것이다. 다섯 번째 속성에 따라서, 모든 경로에서 블랙 노드의 수가 같다고 했기 때문에 존재하는 모든 경로에 대해 최장 경로의 거리는 최단 경로의 거리의 두 배 이상이 될 수 없다.
트리 구조를 나타낼 때, 어떤 노드는 자식(child)를 하나만 가질 수 있고, 리프 노드는 데이터를 담을 수 있다. 레드-블랙 트리도 이와 같은 방법으로 나타내 볼 수 있지만, 그런 표현 방식으로는 레드-블랙 트리의 특성이 변하고, 알고리즘과 상충될 수 있다. 그래서, 이 문서에서는 "nil leaves" 나 "null leaves"를 사용하고 있는데, 이 "null leaf"는 위의 그림에서와 같이 자료를 갖지 않으며, 트리의 끝을 나타내는 데만 쓰인다. 트리 구조를 그림으로 표현할 때, 종종 이 "null leaf"를 생략하고 그리는 경우가 많은데, 그러면 그림상으로는 레드-블랙 트리의 특성을 만족하지 못하는 것처럼 보일 수 있으나 실제로는 그렇지 않다. 이렇게 함으로써, 모든 노드들은 설령 하나 또는 두개의 자식이 "null leaf" 일지라도, 두개의 자식(children)을 가지게 된다.
간혹 레드-블랙 트리를 노드가 아닌 붉은색 또는 검은색 선분(edge)으로 설명하기도 하는데, 실제로는 같은 이야기이다. 어떤 노드의 색은 노드와 그 부모를 연결하는 선분의 색에 대응되기 때문인데, 차이점이 있다면 레드-블랙 트리의 두 번째 속성에서 언급된 root node가 선분으로 설명할 경우 존재하지 않는다는 점이다.
레드-블랙 트리의 읽기 전용(read-only) 동작(탐색 등)은 이진 탐색 트리의 읽기 전용 동작의 구현을 변경하지 않아도 되는데, 이는 레드-블랙 트리가 이진 탐색 트리의 특수한 한 형태이기 때문이다. 그러나 삽입(insertion)과 삭제(removal)의 경우 이진 탐색 트리의 구현에 따른 동작만으로는 레드-블랙 트리의 특성을 만족하지 못한다. 다시 레드-블랙 트리의 특성을 만족하게 만들기 위해서는 O(log "n") 또는 amortized O(1)번의 색 변환과(실제로는 매우 빨리 이루어진다) 최대 3회의 트리 회전(tree rotation)이 필요하다(삽입의 경우 2회). 삽입과 삭제는 복잡한 동작이지만, 그 복잡도는 여전히 O(log "n")이다.
삽입(Insertion).
레드-블랙 트리의 삽입은 단순 이진 탐색 트리에서 하는 것과 같이 노드를 삽입하고, 색을 붉은색으로 정하는 것으로 시작한다. 그 다음 단계는, 그 주위 노드의 색에 따라 달라진다. 여기서 '삼촌 노드(uncle node)'를 도입할텐데, 이는 같은 높이에 있는 옆 노드(다시 말해, 사촌)의 부모 노드(삼촌)를 뜻한다. 여기서 레드-블랙 트리의 특성이 추가된다 :
삽입과 삭제 동작은 C언어로 만든 예제를 이용하여 자세히 설명한다. 삼촌 노드와 할아버지 노드는 다음과 같은 함수(function)에 의해 나타낼 수 있다:
struct node *grandparent(struct node *n)
if ((n != NULL) &amp;&amp; (n-&gt;parent != NULL))
return n-&gt;parent-&gt;parent;
struct node *uncle(struct node *n)
struct node *g = grandparent(n);
if (g == NULL)
return NULL; // No grandparent means no uncle
if (n-&gt;parent == g-&gt;left)
return g-&gt;right;
return g-&gt;left;
첫 번째 경우.
N 이라고 하는 새로운 노드가 트리의 시작(root)에 위치한다. 이 경우, 레드-블랙 트리의 첫 번째 속성(트리의 시작은 검은색이다)을 만족하기 위해서, N을 검은색으로 표시한다. 이 경우, 시작점으로부터 뻗어나가는 모든 경로에 검은색 노드를 하나 추가한 셈이 되기 때문에 레드-블랙 트리의 다섯 번째 속성(한 노드에서부터 뻗어나가는 모든 경로에 대해 검은색 노드의 수는 같다)은 여전히 유효하다.
void insert_case1(struct node *n)
if (n-&gt;parent == NULL)
n-&gt;color = BLACK;
insert_case2(n);
두 번째 경우.
새로운 노드의 부모 노드 P가 검은색이라면, 레드-블랙 트리의 네 번째 속성(붉은색 노드의 모든 자식 노드는 검은색이다)은 유효하다. 그러므로 두 번째 경우에도 이 트리는 적절한 레드-블랙 트리이다. 레드-블랙 트리의 다섯 번째 속성(한 노드에서부터 뻗어나가는 모든 경로에 대해 검은색 노드의 수는 같다)도 별 문제가 없는데, 이는 새로운 노드 N은 두개의 검은색 노드를 leaf node로 가지고 있기 때문이다. 비록 N이 붉은색 노드라고 해도 N이 들어간 자리에 원래 위치했던 노드의 색이 검은색이었으므로, N의 자식 노드에게서 시작되는 경로들은 모두 같은 수의 검은색 노드를 가지게 되고, 결과적으로 다섯 번째 속성은 유지되게 된다.
void insert_case2(struct node *n)
if (n-&gt;parent-&gt;color == BLACK)
return; /* Tree is still valid */
insert_case3(n);
세 번째 경우.
만약 부모 노드 P와 삼촌 노드 U가 모두 붉은색 노드라면, 레드-블랙 트리의 다섯 번째 속성(한 노드에서부터 뻗어나가는 모든 경로에 대해 검은색 노드의 수는 같다)을 유지하기 위해서, P와 U를 모두 검은색으로 바꾸고 할아버지 노드 G를 붉은색으로 바꾼다. 이렇게 함으로써 붉은색 노드인 N은 검은색 부모 노드를 가지게 된다. 그런데 이번에는 할아버지 노드 G가 레드 블랙 트리의 두 번째 속성(root node는 검은색이다)이나 네 번째 속성(붉은색 노드의 두 자식 노드는 검은색이다)을 만족하지 않을 수 있다(네 번째 속성은 G의 부모 노드가 붉은색일 경우 만족하지 않는다). 이를 해결하기 위해서 G에 대해 지금까지 설명한 첫 번째 경우부터 세 번째 경우까지를 재귀적으로(recursively) 적용한다. 이 작업은 삽입 과정 중에 발생하는 유일한 재귀 호출(recursive call)이며, 회전(rotation) 작업을 하기 전에 적용해야 한다는 것에 주의한다.(이는 일정한 횟수의 회전 작업만이 필요하다는 것을 증명한다.)
void insert_case3(struct node *n)
struct node *u = uncle(n), *g;
if ((u != NULL) &amp;&amp; (u-&gt;color == RED)) {
n-&gt;parent-&gt;color = BLACK;
u-&gt;color = BLACK;
g = grandparent(n);
g-&gt;color = RED;
insert_case1(g);
insert_case4(n);
네 번째 경우.
부모 노드 P가 붉은색인데, 삼촌 노드 U는 검은색이다; 또한 새로운 노드 N은 P의 오른쪽 자식 노드이며, P는 할아버지 노드 G의 왼쪽 자식 노드이다. 이 경우, N과 P의 역할을 변경하기 위해서 왼쪽 회전을 한다; 그 후, 부모 노드였던 P를 다섯 번째 경우에서 처리하게 되는데, 이는 레드-블랙 트리의 네 번째 속성(붉은색 노드의 모든 자식은 검은색 노드이다)을 아직 만족하지 않기 때문이다. 회전 작업은 몇몇 경로들 이 이전에는 지나지 않았던 노드를 지나게 하는데, 그럼에도 양쪽 노드가 모두 붉은색이므로, 레드-블랙 트리의 다섯 번째 속성(한 노드에서부터 뻗어나가는 모든 경로에 대해 검은색 노드의 수는 같다)을 위반하지 않는다.
void insert_case4(struct node *n)
if ((n == n-&gt;parent-&gt;right) &amp;&amp; (n-&gt;parent == g-&gt;left)) {
rotate_left(n-&gt;parent);
n = n-&gt;left;
} else if ((n == n-&gt;parent-&gt;left) &amp;&amp; (n-&gt;parent == g-&gt;right)) {
rotate_right(n-&gt;parent);
n = n-&gt;right;
insert_case5(n);
static void rotate_left(struct node *n)
struct node *c = n-&gt;right;
struct node *p = n-&gt;parent;
if (c-&gt;left != NULL)
c-&gt;left-&gt;parent = n;
n-&gt;right = c-&gt;left;
n-&gt;parent = c;
c-&gt;left = n;
c-&gt;parent = p;
if (p != NULL) {
if (p-&gt;left == n)
p-&gt;left = c;
p-&gt;right = c;
static void rotate_right(struct node *n)
struct node *c = n-&gt;left;
if (c-&gt;right != NULL)
c-&gt;right-&gt;parent = n;
n-&gt;left = c-&gt;right;
c-&gt;right = n;
if (p-&gt;right == n)
다섯 번째 경우.
부모 노드 P는 붉은색이지만 삼촌 노드 U는 검은색이고, 새로운 노드 N이 P의 왼쪽 자식 노드이고, P가 할아버지 노드 G의 왼쪽 자식 노드인 상황에서는 G에 대해 오른쪽 회전을 한다. 회전의 결과 이전의 부모 노드였던 P는 새로운 노드 N과 할아버지 노드 G를 자식 노드로 갖는다. G가 이전에 검은색이었고, P는 붉은색일 수밖에 없기 때문에, P와 G의 색을 반대로 바꾸면 레드-블랙 트리의 네 번째 속성(붉은색 노드의 두 자식 노드는 검은색 노드이다)을 만족한다. 레드-블랙 트리의 다섯 번째 속성(한 노드에서부터 뻗어나가는 모든 경로에 대해 검은색 노드의 수는 같다)은 계속 유지되는데, 이는 이전에 P를 포함하는 경로는 모두 G를 지나게 되고, 바뀐 후 G를 포함하는 경로는 모두 P를 지나기 때문이다. 바뀌기 전에는 G가, 바뀐 후에는 P가 P, G, N중 유일한 검은색 노드이다.
void insert_case5(struct node *n)
if (n == n-&gt;parent-&gt;left)
rotate_right(g);
rotate_left(g);
삽입 동작은 치환 작업인데, 이는 모든 호출(call)이 tail recursion이기 때문이다.
삭제(Removal).
이진검색트리에서 두 개의 non-leaf 자식 노드를 가진 노드 X를 삭제할 때, X의 왼쪽 서브트리에서 최댓값 또는 오른쪽 서브트리에서 최솟값을 갖는 노드 Y를 찾고, X에 Y의 값을 복사한다(여기에서처럼). 그리고 Y를 지운다.
이때 Y가 가진 non-leaf 자식 노드는 1개 이하이다. Y의 non-leaf 자식 노드가 2개라면, Y의 값은 최댓값/최솟값이 아닐 것이기 때문이다. ('non-leaf 자식 노드'라고 표현한 이유는, 레드-블랙 트리에는 leaf 노드가 어디든 붙을 수 있기 때문이다.) 따라서 삭제는 최대 한 개의 non-leaf 자식을 갖고 있는 노드를 삭제하는 문제로 치환할 수 있다. 그러므로, 본 문단에서는 한 개 이하의 non-leaf 자식 노드를 가진 노드를 삭제하는 방법만 다룬다.
M은 삭제하고자 하는 노드이고, C는 M의 선택된 자식 노드이다. 만약 M이 non-leaf 자식을 가질 경우, 해당 자식 노드가 C가 되고, 그렇지 않은 경우 두 leaf 노드 중 아무 노드가 C가 된다.
만약 M이 붉은 노드라면, C를 M대신 치환하면 된다. 이 상황은 M이 두 개의 leaf 자식을 갖고 있을 때에만 발생하는데, 왜냐하면 만약 M이 non-leaf 자식 노드와 leaf 자식 노드를 모두 가지는 경우 양쪽의 검은 노드 개수가 달라지기 때문이다. 삭제된 노드를 지나는 모든 path는 단순히 붉은 노드 하나만 없어지게 되고, 삭제된 노드의 부모와 자식 모두 검은 노드이므로, 특성 3(모든 leaf들은 검은 노드)과 특성 4(모든 붉은 노드는 두 개의 검은 자식 노드를 갖는다)는 여전히 유효하다.
또 다른 상황은 M이 검은 노드이고 C가 붉은 노드일 때이다. 검은 노드를 삭제해버릴 경우 특성 4에 위반될 수 있으므로, C를 검은 노드로 바꿔주면 된다.
복잡한 상황은 M과 C가 모두 검은색 노드일 때이다. 이 상황은 두 개의 leaf 자식을 갖고 있는 검은 노드를 지우는 상황에서만 발생하는데, 왜냐하면 M이 non-leaf 자식과 leaf 자식을 모두 가지는 경우, 양 쪽의 검은 노드 개수가 달라지기 때문이다. 이러한 경우 M을 자식 노드 C로 치환한다. 이후 설명부터는 C를 N, C의 형제 노드를 S, N의 새로운 부모를 P, S의 왼쪽/오른쪽 자식을 각각 SL, SR이라고 하겠다.
다음의 함수를 사용하여 형제 노드를 찾을 수 있다.
struct node *sibling(struct node *n)
return n-&gt;parent-&gt;right;
return n-&gt;parent-&gt;left;
우리는 다음의 코드를 통해 위에서 소개한 단계를 밟아나갈 수 있다. 여기서 codice_1함수는 codice_2를 codice_3의 자리에 대입하는 함수이다. 편의를 위해서, 이 섹션의 코드들은 null leaf들은 NULL 대신 실제 노드 객체로 표현할 것이라는 가정을 바탕에 두고 있다. 따라서 검은색 노드가 리프 노드를 표현한 것일 수 있다.("삽입"섹션에서 사용된 코드들은 양쪽 표현을 다 사용했었다.)
int is_leaf(struct node* n)
* LEAF라는 노드를 struct node* 형식으로 하나 만들어주고 사용하면 된다.
return (n == LEAF) ? 1 : 0;
void replace_node(struct node* n, struct node* child)
*앞에서 n의 부모가 NULL이 되는 경우를 delete_case에 오지 않게 미리 처리해주면 된다.
child-&gt;parent = n-&gt;parent;
if (n-&gt;parent-&gt;left == n)
n-&gt;parent-&gt;left = child;
else if (n-&gt;parent-&gt;right == n)
n-&gt;parent-&gt;right = child;
void delete_one_child(struct node *n)
* 선제조건: n이 최대 하나의 non-null 자식을 갖고 있음.
struct node *child = is_leaf(n-&gt;right) ? n-&gt;left: n-&gt;right;
if (n-&gt;color == BLACK) {
if (child-&gt;color == RED)
child-&gt;color = BLACK;
delete_case1(child);
free(n);
만약 N과 N의 원래 부모가 둘 다 검정이었다면, 부모를 삭제하는 것은 N을 지나는 path가 검은 노드 한 개를 덜 갖게 되므로 해서는 안된다. 이는 특성 5(특정 노드에서부터 leaf로 가는 모든 경로에서 같은 수의 검은 노드를 지난다.)를 위반하기 때문에, 트리는 재균형을 맞춰주어야 한다. 고려해보아야 할 몇몇 상황들이 있다:
Case 1: N 이 새로운 루트가 될때. 이 경우에는 더 할게 없다. 우리는 모든 경로에서 하나의 검은 노드를 삭제했고, 새로운 루트 노드는 검은색이므로 모든 특성이 보존된다.
void delete_case1(struct node *n)
if (n-&gt;parent != NULL)
delete_case2(n);
void delete_case2(struct node *n)
struct node *s = sibling(n);
if (s-&gt;color == RED) {
n-&gt;parent-&gt;color = RED;
s-&gt;color = BLACK;
delete_case3(n);
void delete_case3(struct node *n)
if ((n-&gt;parent-&gt;color == BLACK) &amp;&amp;
(s-&gt;color == BLACK) &amp;&amp;
(s-&gt;left-&gt;color == BLACK) &amp;&amp;
(s-&gt;right-&gt;color == BLACK)) {
s-&gt;color = RED;
delete_case1(n-&gt;parent);
delete_case4(n);
void delete_case4(struct node *n)
if ((n-&gt;parent-&gt;color == RED) &amp;&amp;
delete_case5(n);
void delete_case5(struct node *n)
if (s-&gt;color == BLACK) {
/* 이 문은 자명하다,
혹은 N의 부모노드의 왼쪽 자식의 왼쪽 자식으로 두기 위함. case 6에 넘기기 위해 */
if ((n == n-&gt;parent-&gt;left) &amp;&amp;
(s-&gt;right-&gt;color == BLACK) &amp;&amp;
(s-&gt;left-&gt;color == RED)) { /* this last test is trivial too due to cases 2-4. */
s-&gt;left-&gt;color = BLACK;
rotate_right(s);
} else if ((n == n-&gt;parent-&gt;right) &amp;&amp;
(s-&gt;right-&gt;color == RED)) {/* this last test is trivial too due to cases 2-4. */
s-&gt;right-&gt;color = BLACK;
rotate_left(s);
delete_case6(n);
void delete_case6(struct node *n)
s-&gt;color = n-&gt;parent-&gt;color;
if (n == n-&gt;parent-&gt;left) {
case 2를 통과하면 N과 S는 반드시 검은색 노드가 된다. case 2를 통과한 후에 남는 경우의 수는 아래와 같은데, 아래의 경우 모두 각각의 case에서 해결된다.
다시 이야기하지만, 함수 콜은 모두 tail recursion 을 이용하므로, 알고리즘은 in-place이다.
위의 알고리즘에서, 부모 노드에 대해 case 1으로 재귀하는 delete case 3을 제외하고는 모든 case에 대해 순서대로 chained되어 있다: 이 경우가 in-place 구현에서 유일하게 효과적으로 루프를 도는 case이다.(case 3에서 한 번의 회전 이후)
추가적으로, 자식 노드에 대해서는 tail recursion이 일어나지 않으므로, tail recursion 루프는 자식 노드에서부터 연결된 조상 노드들로 거꾸로 올라간다. case 1로 돌아가는 루프는 O(log "n")번을 넘지 않는다.("n"은 삭제 전에 트리에 존재하는 모든 노드의 개수) 만약 case 2에서 회전이 일어나면(case 1-3 루프 중에 유일한 회전), N의 부모노드는 회전 후 빨강으로 변하고, 루프에서 빠져나온다. 그러므로 이 루프 내에서는 회전은 기껏해야 한 번 있다. 루프를 빠져나오고 나서는 두 번 보다 많은 횟수의 추가적인 회전은 일어나지 않기 때문에 모두 합쳐서 3번보다 많은 수의 회전은 일어나지 않는다.
병렬 알고리즘 (Parallel algorithms).
아이템의 수에 비례하여 컴퓨터 프로세서를 이용할 수 있다면, 정렬되어 있는 아이템을 가지고 레드-블랙 트리를 만드는 병렬 알고리즘은 상수시간이나 formula_1시간으로 구현될 수 있다. 빠른 검색, 삽입, 삭제를 위한 병렬 알고리즘 또한 알려져 있다.
윌리엄 하비 카니(William Harvey Carney, 1842년 3월 28일 ~ 1908년 3월 20일)는 남북 전쟁에서 싸운 군인으로 아프리카계 미국인 처음으로 미국 의회 명예 훈장이 수여되었다. 노예로 태어난 그는 이후 남북 전쟁에서 매사추세츠 54 연대에 입대하였다. 그의 연대가 사우스캐롤라이나주에 있는 남군 보유의 와그너 요새에서 난간의 문장을 얻으면서 카니는 일찍이 유색 인종 기수들이 떨어진 후 미국의 깃발을 들었다. 그는 요새로 깃발을 들어 자신을 둘러싼 남성들을 집결하고 영감을 주었다. 자신의 부상에 불구하고, 그는 "얘들아, 난 나의 임무를 한 것 뿐이다; 낡은 깃발은 절대 땅에 닿지 않는다."라고 말했다.
버지니아주 노퍽에서 태어났다. 그의 부친 윌리엄 카니 1세는 지하철도에 노예화를 달아났다. 카니 1세는 자신의 가족의 자유를 사기 위하여 자신이 일을 하고 돈을 모았던 매사추세츠주에 정착하였다. 1850년대 후반 이제 자유의 몸이 된 카니 가족은 뉴베드퍼드로 이주하였다. 카니는 자신이 읽고 쓰는 것을 배운 수업을 들었다. 자신이 사역 참여에 대한 관심을 보였을 때 그는 미국 육군에 복무하는 데 요청으로서 남북 전쟁의 시작을 보았다. 카니는 "국가가 모든 사람을 부를 때 난 최고로 나의 하나님을 섬기고, 나의 국가와 나의 억압을 받은 형제들을 섬길 수 있었다."는 것을 언급하였다.
1863년 1월 1일 노예 해방 선언의 통과 후 매사추세츠 54 연대가 형성되었다. 매사추세츠주지사 존 앤드루는 전흑인 지원군 연대의 결성을 이끌었다. 노예제를 끝내는 도움을 구한 노예 폐지론자들은 군인 모집 노력의 지도자들이 되었다. 너무 많은 남성들이 육군에 복무하는 데 지원했기 때문에 2개의 연대들 - 매사추세츠 54 연대와 55 연대가 창조되었다. 백인 사령관들이 흑인 지원병들을 지도하고 훈련시켰다. 5월 훈련을 완료한 후, 그들은 전쟁에 참여하기 위하여 출발하였다.
54 연대는 그들이 마을을 습격하라는 명령을 받은 조지아주 대리언에 배치되었다. 그들의 장교들은 54 연대의 이용을 싸우기 보다는 약탈하거나 불태우는 것으로 비판하였다. 하지만, 연대는 곧 7월 16일 사우스캐롤라이나주 제임스아일랜드에서 자신들의 첫 전투에 참여하였다. 와그너 요새 전투가 이틀 후에 이어졌다. 로버트 굴드 쇼 대령의 지휘하에 54 연대는 7월 18일의 저녁에 요새에 행군한 5,000명의 북군을 지도하였다. 요새에서 1800명의 남군이 공격을 준비하였다. 북군의 함대는 그들의 방어력을 약화시키기 위해 하루를 통하여 대포 발사와 함께 요새를 폭행하였다. 54 연대가 요새에 도착했을 때 남군은 그들에게 총격을 가했다. 쇼는 연대의 진보를 조정하고 해자를 지나 요새로 이어지는 비탈길을 올라갔다.
전투가 격렬해지면서 쇼는 살해 되었으나 그의 연대는 지속적으로 싸웠다. 54 연대는 자신들의 600명의 군인들 중에 280명이 살해 되고, 상처를 입고, 포로 혹은 실종되면서 많은 사상자를 냈다. 더욱 많은 북군들이 몇시간 동안 지속된 전투에서 지속적으로 싸웠다. 결국적으로 북군은 전투로부터 강제로 철수하여 그 자리에서 남군의 보유를 중단할 수 없었다. 54 연대의 활동들은 더 많은 흑인 남성들이 입대하도록 영감을 주었다.
와그너 요새 전투가 열린 동안 카니는 중상을 입었다. 아직 그는 이전의 유색 인종 기수들이 떨어진 후, 미국의 깃발을 구했다. 카니는 "나는 나의 총을 던져버렸고, 색을 잡았고 기둥의 머리로 가는 길을 만들었다."면서 "난 나의 임무를 한 것 뿐이다; 낡은 깃발은 절대 땅에 닿지 않는다."고 선포하였다. 이 활동은 미국 육군의 군인들로서 자신들의 역할에 54 연대가 가져간 자부심을 보여주었고, 흑인 군인들의 용감과 군사 실력을 보였다. 자신의 부상의 이유로 카니는 1864년 퇴역하였고 매사추세츠주로 돌아왔다. 54 연대는 남은 전쟁 동안 지속적으로 싸워 사우스캐롤라이나주와 플로리다주에서 복무하였다.
1890년대 동안 남북 전쟁 25 주년 축제들이 미국 군인들의 영웅적 행위에서 관심을 증가시켰다. 이 일은 미국 의회 명예 훈장의 유입으로 이끌었다. 1897년 윌리엄 매킨리 대통령은 명예 훈장을 수여하기 위하여 규정을 검토하기 위해 육군에 의문하였다. 그들의 검토 후에, 육군은 상을 보증하기 위해 훈장 수상자들이 용감함과 대담함을 보여야 한다는 것을 결정하였다. 자신의 용맹으로 카니는 1900년 5월 23일 시어도어 루스벨트 대통령에 의하여 미국 의회 명예 훈장이 수여되었다. 이 상은 명예 훈장의 공로를 인정하는 데 아프리카계 미국인에 의한 첫 행동으로서 1863년 7월 18일 와그너 요새에서 카니의 노력을 표시하였다.
고향으로 돌아온 후, 카니는 수재너 윌리엄스에게 결혼하여 슬하 1녀를 두었다. 그는 이후에 뉴베드퍼드에서 첫 흑인 우편 배달부이자 미국 우정청에서 첫 문서화된 흑인 우편 배달부가 되었다. 미국 우정청으로부터 퇴직한 후, 그는 매사추세츠주 하원에서 사자(使者)를 지냈다.
그는 1908년 12월 9일 뉴베드퍼드에서 사망하여 오크 그로브 묘지에 안장되었다. 그의 추억은 북군에 복무한 흑인 군인들의 용기와 용맹의 표상으로 산다.
영화 《영광의 깃발》에서 모건 프리먼이 역을 맡은 존 롤린스 원사는 카니에 기초를 두었다.
대한불교천태종(大韓佛敎天台宗)은 대한민국에서 활동하는 교단(敎團)이다. 현재(2015) 종정은 김도용 대종사이며 역대 종정에는 1대 상월원각대조사, 2대 남대충 대종사이다. 종립대학인 금강대학교를 운영한다.
교단(敎團) 대한불교천태종(大韓佛敎天台宗)은 1967년 1월 24일 충청북도 단양군 영춘면 백자리 118 소재 구인사(救仁寺)에서 박상월(朴上月)이 중창하였고 법화사상계에 속한다. 석가모니불을 본존(本尊)으로 하고 천태대사 지의를 종조(宗祖)로, 대각국사 의천을 개창조로, 《법화경》을 소의경전(所依經典)으로 삼는다.
1945년 4월 20일 소백산에 구인사(救仁寺)를 창건하고 1966년 8월 천태종 대각불교를 창개(創開)하였다. 1969년 12월 포교원을 본종(本宗)으로 명칭을 변경하였다.
종단(宗團) 기구는 종정 아래 총무원감사원종의회와 그 밑에 4부를 둔다. 신도회 조직으로 전국중앙신도회와 그 아래 각 도시군 단위 지부지회가 결성되어 있으며, 어린이회, 학생회, 청년회 등 각 연령대의 신행단체와 신흥 불교 종단 중 신도 조직의 체계가 가장 잘 짜여 있고 방대(尨大)하다.
교화(敎化) 사업으로 1970년 1월 《천태종약전(天台宗略典)》을 발간했고 1971년 《천태종성전》이 간행했다. 포교(布敎) 사업으로 월별로 각지를 순회(巡廻)하면서 지부별(支部別)로 신도회 자체에서 정기(定期)로 법회를 개최(開催)하며. 주경야선(晝耕夜禪)을 수행(修行)하는 신조(信條)로 삼아 모든 재원(財源)은 자체 임야를 개간(開墾)하여 충당(充當)하고 당시 새마을사업에 앞장섰으며, 이후 계속하여 공익사업(公益事業)에 앞장선다. 육영사업으로 금강대학교를 설립하고 후세 교육에도 힘쓰고 있다.
《법화경》을 근본 교의(敎義)로 하고 선정(禪定)과 지혜의 조화를 종의(宗義)로 하는 신라의 천태종은 고려 때 대각국사 의천에 의거(依據)해 해동천태종으로 성립되었다. 이후 구산선문은 조계종(曹溪宗)으로 총칭(總稱)되면서 5교 9산이 5교 양종(兩宗: 조계종천태종)으로 일컬어졌다. 천태종의 성립으로 조계 9산은 큰 타격을 입어 겨우 종세(宗勢)를 유지했다. 천태종은 고려 말에 천태법사종(天台法事宗)과 천태소자종(天台疏字宗)으로 나뉘었고 조선 태종 7년(1407)에 재통합되었으며, 세종 6년(1424)에 조계종총남종(摠南宗)과 아울러서 선종(禪宗)으로 통합되고 선교 양종(禪敎兩宗)이란 이름이 나타나게 되었다.
근대의 특징이 될 만한 성질이나 경향이 있는 의미의 대한불교천태종(大韓佛敎天台宗)을 세운 사람은 박상월(朴上月)이다. 대한불교천태종(大韓佛敎天台宗)은 지의, 의천, 박상월(朴上月)을 종조(宗祖)라 칭(稱)한다.
소의경전(所依經典).
지역별 사찰 수.
함)
합계: 사찰 152개(2017년 기준)
합계: 사찰 3개(2019년 기준)
재단법인(財團法人).
재단법인(財團法人) '대한불교천태종(大韓佛敎天台宗)'은 애국 불교, 생활 불교, 대중 불교를 실현하려는 운동을 이용하여 부처의 교의(敎義)인 '상구보리(上求菩提)·하화중생(下化衆生)'을 실천하고 도리인 '생활 불법(佛法)'을 국민 누구에게나 체득하게 하여 건전(健全)하고 숭고(崇高)한 국민정신(國民精神)을 창달(暢達)케 하여 개인 완성과 불국(佛國) 건설을 실현(實現)하고자 1991년 4월 16일 설립(設立)된 문화체육관광부에서 소관(所管)하는 재단법인이다. 사무실(事務室)은 충북 단양군 영춘면 백자리 132-1에 있다.
의천(義天: 1055년 10월 30일(음력 9월 28일) ~ 1101년 10월 28일(음력 10월 5일))은 고려시대의 왕족 출신 승려, 작가이다. 자는 의천(義天), 속성은 왕(王), 이름은 석후(釋煦) 또는 후(煦)이며, 호는 우세(祐世), 흔히 대각국사(大覺國師)라는 시호로 부르기도 한다. 고려 문종(文宗)의 넷째 아들로서, 어머니는 인예태후(仁睿太后)이다. 순종, 선종, 숙종의 친동생이며, 추존왕 양헌왕의 이복 형이다. 대한불교천태종을 세운 한국 천태종의 중흥시조로서, 대한불교천태종에서 3대 종조 가운데 한 사람으로 추앙받고 있다. 개경 출신이다.
문종은 자신의 아들들 중 누가 승려가 될 것인가를 묻자, 그가 자원하여 승려가 되었다. 1065년 외삼촌인 경덕국사 난원(景德國師 爛圓)를 스승으로 하여 계를 받고 출가하여 승려가 되었다. 일찍이 요나라와 송나라를 방문, 순례하며 요 도종의 국사가 되고, 송나라를 방문해서는 각처의 불교 성지를 순례하고, 송나라의 고승들을 만나 강론을 듣고 돌아왔다. 이후 흥왕사, 흥원사(興圓寺), 해인사의 주지를 거쳐 다시 흥왕사의 주지가 되었다.
출생과 출가.
1055년 9월 28일 고려 제11대 왕인 문종과 그 왕비 인예왕후(仁睿王后)의 넷째아들로 태어났다. 본명은 석후(釋煦), 또는 후(煦)였는데, 그의 이름자 후가 송나라 철종(哲宗)의 본명 후와 같은 글자라 하여, 이름 대신 자(字)인 의천을 주로 사용하였다. 그가 11세되던 해에 부왕 문종이 왕자들을 불러 "누가 출가하여 복전(福田)이 되겠느냐."고 물었을 때, 그가 스스로 출가를 자원하였다 한다. 1065년 5월 14일에 경덕국사(景德國師)를 은사로 삼아 출가하여, 영통사(靈通寺)에서 공부하였다. 문종은 경덕국사 김난원을 불러서 불일사(佛日寺) 계단(戒壇)에서 직접 의천을 삭발하게 했다. 일찍이 출가하여 불교승려가 된 경덕국사 난원은 의천의 외할아버지 김은부의 아들로, 의천의 외삼촌이며 원혜왕후, 원성왕후의 친정 오라비가 된다.
1065년(문종 19) 왕사(王師) 난원(爛圓)이 의천의 머리를 깎아 승려가 되게 하였고, 그 뒤 영통사(靈通寺)에 있었으며, 13세에 우세(祐世)의 호를 받고 승통(僧統)이 되었다. 그해 10월 불일사(佛日寺)에서 구족계(具足戒)를 받았다. 그는 어려서부터 영특하였는데, 승려가 된 이후에도 학문에 더욱 힘을 기울여 대승과 소승의 경·율·론 삼장(三藏)은 물론, 유교의 전적과 역사서적 및 제자백가의 사상에 이르기까지 섭렵하지 않은 바가 없었다.
후에 경덕국사 난원이 입적하면서 그에게 법문(法門)을 계승하였다. 그는 승려이면서 불교학자로 당시 고려의 불교 종파에는 계율종(戒律宗), 법상종(法相宗), 열반종(涅槃宗), 법성종(法性宗), 원융종(圓融宗), 선적종(禪寂宗)이 있었는데, 의천은 평생 불교 계파와 육종(六宗) 및 신라시대의 선교양종을 두루 연구하여 불교학연구의 대가가 되었다. 또한 그는 외전(外典)인 육경(六經)과 칠략(七略) 등을 해석하여, 문종으로부터 '광지개종홍진우세승통(廣智開宗弘眞祐世僧統)'의 법호를 하사받았다.
요, 송 순방 활동.
그는 형인 순종과 선종과 숙종의 각별한 지우를 받았다. 그의 명성은 요나라에도 알려져 요나라 도종 천우황제의 초청을 받는다. 요 도종은 그에게서 계를 받아 국사와 사자(師資)의 인연을 맺고 그에게서 법문을 배웠으며, 요 도종은 그가 고려로 돌아간 이후에도 여러번 그에게 경책과 다향(茶香), 금백(金帛) 등을 보내왔다.
1084년(선종 1) 송나라 정원(淨源) 법사의 초청을 받고 왕에게 송나라에 가서 구법(求法)할 것을 청했으나 왕이 말리므로 남루한 옷차림으로 몰래 제자 수개(壽介)만 데리고 1085년 송나라로 떠나자 왕은 크게 놀라 관리와 제자 낙진(樂眞)혜선(慧宣)도린(道隣) 등으로 수행하게 했다. 의천은 몰래 제자 몇인을 대동하고 비밀리에 배편으로 송나라에 입국했지만, 소문이 알려져 송나라 철종은 특별히 주객낭중(主客郎中)인 양걸(楊傑)을 보내 의천을 수행, 인도하게 되었다. 이후 의천 일행은 송나라의 밀수(密水), 변하(汴河) 등을 순례하고, 변하에 도착하여 신전(宸殿)에서 철종을 접견하였다. 그리고나서 차례로 6종중(宗中)의 정정한 큰스님들이 있는 사찰을 방문, 즉 정원(淨源), 양연(懹璉), 택기(擇其), 혜림(慧琳), 종간(從揀)등 50여 인을 만나보았다. 이후 송나라 철종(哲宗)이 영접하여 계성사(啓聖寺)에 있게 하고, 화엄(華嚴) 법사 유성(有誠)으로 하여금 상종하게 하여, 현수(賢首)천태 양교의 판교동이(判校同異)유묘(幽妙)의 뜻을 문답하였다. 또 상국사(相國寺)의 원조선사와 흥국사 서천(西天)의 삼장(三藏) 천길상(天吉詳)을 찾아보고 주객원외랑(主客員外郞) 양걸(楊桀)을 대동하고 송나라 서울을 출발 금산(金山)의 불인(不印) 선사 요원(了元)에게 들리고, 항주(伉州)의 원공(源公) 법사를 찾아 혜인(慧因)에게 《화엄소초(華嚴疏鈔)》의 의심되던 것을 물었다.
흥왕사 주지.
그때 선종이 귀국을 청하자 자변(慈辨) 대사에게 천태종의 경론을 듣고, 천태산 지자(智者)대사의 부도(浮圖)에 예배, 발원문을 지어 천태종을 본국에 중흥할 것을 맹세했다. 또 영지(靈芝)의 대지(大智) 대사에게 계법을 받는 등 고승 50여 명을 만나 법요를 문답하였다. 중국 송나라를 순례중이던 의천에게 선종이 갑자기 본국으로 돌아오라고 요구하게 된 것은 문종이 직접 흥왕사(興王寺)를 창건하였지만, 문종 사후 오랫동안 흥왕사 주지 자리가 비어 있었다. 그리하여 선종은 의천을 귀국시켜 칙명(勅命)으로 흥왕사 주지로 임명하 강경(講經)과 선담(禪譚)의 법회를 지원하였다.
1086년(선종 3) 왕과 왕후의 영접을 받고 환국하여 석전(釋典)과 경서 1천 권을 바쳤으며, 흥왕사에 있으면서 그곳에 교장도감(敎藏都監)을 두게 하고, 요나라송나라일본에서 경서를 구입하고, 고서를 수집하여 《속장경》 4천 7백 40여 권을 간행하였다. 1094년(선종 11) 흥원사(興圓寺)의 주지로 있었고, 그 후 해인사(海印寺)흥왕사에 있다가 국청사(國淸寺)가 새로 세워지자 주지를 겸하고 처음으로 천태교를 강하였다. 흥왕사 주지로 재직 중 모후인 인예태후 이씨와 둘째 형인 선종이 승하하자 의천은 다시 해인사로 물러났다.
헌종이 즉위한 뒤에도 융숭하게 대접받았고, 헌종은 불교의 중흥을 시도하려고 해인사로 여러 차례 사람을 보내서 의천을 개경으로 오도록 했다. 헌종의 초빙으로 의천은 다시 흥왕사 주지를 맡게 되었다.
송나라의 승려와 불교학자들과 서신으로 사상교류를 하는 한편, 국내에서도 후학 양성에 힘을 기울였다. 숙종 때 주전론(鑄錢論)을 주장하여 사회경제 면에도 많이 공헌한 바 있고, 1098년(숙종 3) 왕자 징엄(澄儼)이 승려가 되자 그 스승이 되었다. 1097년 조카인 징엄을 제자로 받았다. 형인 숙종은 다시 자신의 다섯째 왕자 원명국사 징엄(圓明國師 澄儼, 1090∼1141)을 손수 삭발시켜 의천의 제자로 법통을 계승하게 하였다.
1101년(숙종 6) 국사(國師)로서 활동하던 중 총지사(總持寺)에서 입적하였다. 1101년 10월 3일 고려 숙종으로부터 국사로 책봉되었다. 그러나 병세는 깊어져, 10월 5일 문병 온 형왕(兄王) 숙종에게 "원한 바는 정도를 중흥하려 함인데 병마가 그 뜻을 빼앗았나이다. 바라옵건대 지성으로 불법을 외호하시와 여래께서 국왕, 대신에게 불법을 외호하라 하시던 유훈을 봉행하시오면 죽어도 유감이 없나이다"라는 유언을 남겼다. 당시 그의 나이 향년 47세, 법랍 36세였다.
서호(西湖)의 승려 혜소(惠素)는 국사의 고제로서 후에 행록(行錄) 10권을 선집하였으며, 태백산인(太白山人) 융응(戎膺)은 국사의 적사(嫡嗣)로 법해(法海)의 용문(龍門)이라 호하였다. 저서로는 &lt;신편제종교장총록&gt;3권, &lt;신집원종문류(新集圓宗文類)&gt;22권, &lt;석원사림(釋苑詞林)&gt;250권, 의천의 사후 그의 제자들이 그의 행적과 시 등을 모은 &lt;대각국사문집(大覺國師文集)&gt; 23권과 &lt;대각국사외집(大覺國師外集)&gt;13권, &lt;간정성유식론단과(刊定成唯識論單科)&gt;3권, &lt;천태사교의주(天台四敎儀註)&gt;3권 등이 있다. 그러나 이 저술들이 거의 실전, 없어지고 현재는 &lt;신편제종교장총록&gt;3권과 &lt;대각국사문집&gt;, &lt;대각국사외집&gt;의 낙장본, &lt;원종문류&gt;, &lt;석원사림&gt;의 일부, &lt;간정성유식론단과&gt; 등이 현전하여오고 있다.
그가 활동하던 당시 고려의 불교는 선종과 교종 양종의 대립이 심각하였고, 의천은 각 교단을 통합하여 고려 불교의 파벌갈등과 폐단을 바로잡아 교단을 정리하고, 불교의 가르침을 통해 흉흉해진 민심을 다잡고 올바른 국민사상을 확립시키려고 하였는데, 그러한 근본이념을 천태사상에서 발견하였던 것이다. 그에 대한 평가로는 불교전적을 정비하고, &lt;고려속장경&gt;을 간행하였으며, 송나라에 유학하여 새로운 문화를 수입하였고, 천태종을 세워 교단의 통일과 국가발전을 도모하는 등 많은 훌륭한 업적을 남겼다는 평이 있다.
아카드국(), 또는 아카드 제국()은 수메르 북부의 고대 도시인 아카드를 중심으로 성장한 고대 제국으로, 메소포타미아 최초의 제국이자 인류 최초의 제국으로 여겨진다. 아카드 제국 시기는 기원전 2334년 무렵부터 2154년 무렵까지 약 2백여 년으로 추측된다.
아카드인이 최초로 활동을 시작한 것은 기원전 2350년경 부터이다. 아카드의 왕인 사르곤은 수메르인의 도시국가들을 정복하여 메소포타미아 최초의 통일국가를 건설하였다. 아카드 왕국이 수립되면서 바빌로니아(남부 메소포타미아)의 북반부를 아카드, 남반부를 수메르라고 부르게 되었다.
수도는 아카드였으나, 그 소재지는 아직 밝혀지지 않았으며 역사학자들은 바그다드 인근으로 추정하고 있다. 사르곤은 56년간의 치세(治世) 동안 남쪽은 페르시아만에서 북쪽은 동지중해에 이르는 대제국을 형성하였는데, 궁병대(弓兵隊)를 중심으로 한 강력한 군대와 중앙 집권적 정치제도로 국가의 기초를 다졌다
하지만 아카드 제국의 200여년에 이르는 지배기간 동안 피지배 민족들을 차별하며 주변 국가들에게 수많은 전쟁들을 일으켜서 수많은 반란들이 일어났다. 특히 사르곤의 두 아들 시대에는 변경지방의 대규모 반란으로 고통을 받았지만, 제4대 왕 나람신은 반란을 진압하고 사르곤 시대의 제국을 회복하여 ‘아카드의 신(神), 사계(四界)의 왕’이라 일컬으며 신격화되었다. 그러나 얼마 못가서 국운이 점점 기울기 시작했고 결국 기원전 2150년경 이란고원에서 침입해온 구티족에 의해 멸망하였다. 이후 셈족은 다시는 국가를 세우지 못했다.
아카드인의 언어는 셈어의 동방군(東方群)에 속한다. 그들은 수메르인에게서 배운 설형문자(楔形文字)로 아카드어를 점토판에 써서 남겼으며, 수메르 문명을 셈화하여 후대에 전달하는 역할을 하였다.
예술면에서는 양식화된 수메르 예술에 사르곤기(期)라 불리는 새로운 면을 열어 많은 걸작을 남겼다. 특히 수사에서 발견된 나람신왕의 전승비(戰勝碑)와 니네베의 출토품으로서 사르곤왕을 나타낸 듯한 청동제 두부상(頭部像)은 유명하다.
제국은 도로를 통해 결속할 수 있었다. 그 도로를 따라 정기적인 우편 서비스가 있었으며 토지조사가 시작되었으며, 천문학적 관측과 지구적인 사건이 사르곤에 의해 만들어진 도서관에 기록되었다.
그 다음의 혼란기
1차 논리(一次論理, )는 원소에만 한정 기호를 가할 수 있고, 술어에는 한정 기호를 가할 수 없는 술어 논리이다. 명제 논리와 달리 변수에 대하여 한정 기호를 사용할 수 있으나, 2차 논리와 달리 변수들의 집합에 대하여 한정 기호를 사용할 수 없다. 1차 논리의 경우, (2차 논리와 달리) 괴델의 완전성 정리 · 콤팩트성 정리 · 뢰벤하임-스콜렘 정리와 같은 중요한 성질들이 성립한다.
이외에 1차 술어 논리, 1계 논리 등으로도 불린다. 간단히 술어 논리(predicate logic)라 하면 1차 논리를 가리키는 경우가 많다.
그렇다면, formula_10으로 정의되는 1차 논리 언어 formula_11는 특정한 문자열들의 집합이다. 이 문자열을 구성하는 문자 집합
이 기호들 가운데, formula_38 및 formula_39를 제외한 기호들을 논리 기호()라고 한다.
여기서 논리식 formula_54 및 그 속에 등장하는 변수 formula_21에 대하여, 만약 formula_54가 formula_64를 포함하지 않는다면, formula_21를 formula_54의 자유 변수()라고 하며, 그렇지 않다면 formula_21를 formula_54의 종속 변수()라고 한다.
공리와 추론 규칙.
1차 논리의 증명 이론은 다양한 방식으로 공리화할 수 있다. 예를 들어 다비트 힐베르트의 힐베르트 체계()나, 게르하르트 겐첸의 시퀀트 계산이나 자연 연역 등을 사용할 수 있다.
1차 논리를 힐베르트 체계를 사용하여 공리화하면, 다음과 같다. 우선, 편의상 다음과 같은 기호만을 사용한다고 하자.
이 경우, 다음과 같은 공리 기본꼴()들을 정의한다. 이 공리 기본꼴들에서 사용된 기호들은 다음과 같다.
과 일반화
가 있다. 이 밖에, 다음과 같은 명제 논리의 공리 기본꼴들이 사용된다.
위 공리 기본꼴들에서, formula_93는 논리식 formula_54에 등장하는 자유 변수 formula_21를 항 formula_77로 대체하여 얻는 논리식을 뜻한다. 예를 들어, 체의 언어에서
이다. 이때, 논리식 내부의 ‘formula_98’에서 formula_21가 치환되지 않는 이유는 이 부분에서는 formula_21가 종속 변수이기 때문이다.
의미론.
1차 논리의 의미론은 보통 모형으로 주어진다. 주어진 연산 집합 formula_2와 관계 집합 formula_6을 갖는 1차 논리 언어 formula_103가 주어졌다고 하자. 그렇다면, 이 언어의 모형은 집합 formula_104 및 각 formula_105항 연산 formula_24에 대하여 formula_25의 해석 formula_108 및 각 formula_31항 관계 formula_30에 대하여 그 해석 formula_111으로 구성된다. 이를 통해, formula_103의 문장 formula_54와 formula_103의 모형 formula_115에 대하여, formula_54가 formula_115에서 참인지 또는 거짓인지 여부를 정의할 수 있다. formula_54가 formula_115에서 참이라는 것은
보다 일반적으로, formula_103의 논리식 formula_54가 자유 변수 formula_123를 갖는다고 하자. 그렇다면, formula_103의 모형 formula_115 및 그 속의 formula_126개의 원소
가 주어졌을 때,formula_54가 formula_115에서 formula_130에 대하여 참인지 또는 거짓인지 여부를 정의할 수 있다. 이는
증명 이론.
비논리 기호를 포함하지 않는 1차 논리 문장들의 집합을 formula_132라고 하자. 그 가운데, 모든 모형에서 참인 문장들의 부분 집합
을 생각하자. 또한, formula_132 속에서, 위의 힐베르트 체계를 통해 증명할 수 있는 문장들의 집합을