이번 글에서는 한국어의 객체경어법에 대해 살펴보도록 하겠습니다. 이번 글은 고려대 정연주 선생님 강의를 정리했음을 먼저 밝힙니다. 그럼 시작하겠습니다.

객체경어법

객체경어법이란 문장 내의 목적어나 부사어를 높여서 존대를 실현하는 경어법의 한 종류입니다. 다음과 같이 주로 동사 서술어로 실현됩니다.

• 묻다, 말하다 - 여쭙다
• 보다, 만나다 - 뵙다
• 주다 - 드리다
• 데리고 - 모시고

객체경어법은 여격조사 ‘께’로 실현되기도 합니다.

언제 쓰이나

객체경어법은 다음과 같이 ‘화자보다 높은 객체’를 높이고자 할 때 쓰입니다.

(1) 언니가 아버지께 선물을 드렸다.

그러나 다음 예문은 비문입니다.

(2) (화자가 손자인 경우) *할아버지께서 아버지께 선물을 드렸다.

아버지는 화자보다 높은 객체라는 점에 주목한다면 (2) 또한 (1)처럼 객체경어법을 쓰지 않을 이유가 없습니다. 하지만 (1)은 아버지(객체)가 언니(주체)보다 높은 사람이지만, (2)는 아버지(객체)가 할아버지(주체)보다 낮은 사람이라는 점이 다릅니다. 객체높임은 ‘주체보다 높은 객체’를 높일 때 쓰인다는 것입니다.

다른 예문을 보겠습니다.

(3) (화자가 할아버지인 경우) ?철수야, 그거 어머니께 갖다 드려라.

(3)에서는 어머니(객체)가 철수(주체)보다 높기 때문에, 객체가 주체의 존대 대상이 됩니다. 하지만 객체높임의 동사인 ‘드리다’를 쓰면 어색합니다. 어머니(객체)는 할아버지(화자)의 손아랫사람이기 때문입니다. 즉 객체높임은 화자와 객체와의 관계도 고려된다는 이야기입니다.

요컨대 객체높임은 객체가 화자보다 높고, 객체가 주체보다 높은 (1)과 같은 상황에서 실현될 수 있습니다.

객체높임에서의 압존법

높여야 할 대상이지만 듣는 이가 더 높을 때 화자가 청자를 고려하여 주체의 공대를 줄이는 어법을 압존법(壓尊法)이라고 합니다. 객체높임에서도 압존법이 실현되는 경우가 있습니다. 객체높임이 실현된 예문을 먼저 보겠습니다.

나는 신문을 아버지께 갖다 드렸다.

위 예문에 해당하는 내용을 할아버지께 말씀드린다고 가정해 봅시다. 이 경우 아래처럼 이야기해야 자연스럽습니다. 아버지(객체)가 할아버지(청자)보다 아랫사람이기 때문에 청자를 고려해 공대를 줄인 것입니다.

할아버지, 신문을 아버지에게 갖다 주었습니다.

객체경어법의 특징

객체경어법은 현대국어에서 그 쓰임이 아주 한정되어 있습니다. 주체높임의 선어말어미 ‘-시-‘처럼 널리 쓰이는 형태소가 따로 없고 객체높임의 동사 몇 가지가 따로 있을 뿐입니다. 바꿔 말해 특수한 객체 존대형이 없는 용언에 대해서는 객체가 아무리 존귀한 인물이더라도 그에 대한 존대를 서술어 쪽에서는 표현할 방도가 없습니다. 예컨대 다음 예문의 할머니나 교장 선생님을 존대할 방법을 찾기가 마땅치 않습니다.

창호는 할머니를 몹시 따른다.

영희야, 교장 선생님께 빨리 가거라.

이번 글에서는 한국어의 주체경어법에 대해 살펴보도록 하겠습니다. 이번 글은 고려대 정연주 선생님 강의를 정리했음을 먼저 밝힙니다. 그럼 시작하겠습니다.

국어 경어법 체계

한국어 경어법은 예우의 대상에 따라 다음과 같이 세 가지로 구분됩니다.

• 주체경어법 : 동작이나 상태의 주체, 즉 한 문장의 주어를 높일 때
• 객체경어법 : 주체가 하는 행위가 미치는 대상을 높일 때
• 상대경어법/청자경어법 : 말을 듣는 사람을 높일 때

이 가운데 주체경어법과 객체경어법은 누구를 높여 대우하느냐, 그렇지 않느냐로 ‘이분’되는 속성을 가집니다. 반면 상대경어법은 청자를 어느 정도로 대우하느냐를 여러 등급으로 나누어 세분화합니다.

화자보다 높은 주체

주체경어법은 주체(주어)를 높이는 경어법의 일종입니다. 대개 주체가 화자보다 높을 때 쓰며 주로 선어말어미 ‘-시-‘로 실현됩니다. 다음 예문과 같습니다.

알겠습니다, 사장님. 과장님 들어오시는대로 연락을 드리겠습니다.

청자보다 낮거나 높은 주체

그러나 ‘-시-‘의 쓰임이 주체와 화자의 대비에서가 아니라 주체와 청자의 대비에서 결정되는 경우도 있습니다. 다음 예문을 보겠습니다.

(조부모 앞에서 손녀가) 할머니, 엄마 왔어요.

위 예문의 주체 ‘엄마’는 화자인 손녀의 손윗사람입니다. 평소 같은 경우라면 화자는 ‘-시-‘를 써서 존대해야 합니다. 하지만 이 문장은 주체를 높이지 않았는데도 자연스럽습니다. 청자인 ‘할머니’가 주체보다 높다는 점을 고려했기 때문입니다. 이처럼 높여야 할 대상이지만 듣는 이가 더 높을 때 화자가 청자를 고려하여 주체의 공대를 줄이는 어법을 압존법(壓尊法)이라고 합니다.

반대의 경우도 있습니다. 다음 예문을 보겠습니다.

(친구의 자식들에게) 아버지 들어오시면 아저씨한테 전화하시라고 해라.

위 예문의 화자는 문장의 주체와는 친구 관계이므로 ‘-시-‘를 써서 존대할 이유가 없습니다. 하지만 이 문장은 주체를 높였음에도 자연스럽습니다. 청자가 주체보다 손아랫사람이라는 점을 고려했기 때문입니다. 이처럼 한국어에서는 주체, 청자 사이의 위계를 섬세하게 고려해 존대의 의미를 드러냅니다.

아메리카노는 높임의 대상?

지금까지 설명한 예시는 높임의 대상을 직접 높이는 직접높임에 해당합니다. 그 반대로 한국어에서는 신체 부분, 안정적인 소유물, 가족 등 높임의 대상과 밀접한 관련을 지니고 있는 대상을 높여 존대의 의미를 드러내는 경우가 있습니다. 이러한 높임법을 간접높임이라고 합니다. 예문을 보겠습니다.

(ㄱ) 부장님은 머리가 하얗게 {세셨다 / *세었다}.

(ㄱ)의 서술어 ‘세다’의 직접적인 주체는 ‘머리’입니다. 엄밀히 따져보면 머리는 높임의 대상이 될 수 없습니다. 하지만 머리는 높임의 대상인 ‘선생님’과 밀접한 관련을 맺고 있습니다. 이 경우 ‘-시-‘를 쓰지 않으면 어색한 문장이 됩니다.

신체 부분, 안정적인 소유물, 가족 등이 아닌 명사(구)에 ‘-시-‘를 동반하는 경우도 있습니다. 다음 예문과 같습니다.

(ㄴ) 선생님은 버스 정류장이 {머셔서 / 멀어서} 불편하시겠어요.

버스 정류장은 높임의 대상이 아니지만 ‘-시-‘를 써서 존대해도 어색하지 않습니다. 버스 정류장을 높임의 대상인 ‘선생님’의 생활과 관계가 깊은 사실로 파악한다면 ‘머리’처럼 높여도 자연스러운 느낌을 주기 때문인 듯합니다. 하지만 ‘-시-‘를 써서 반드시 높여야 하는 ‘머리’의 예와 달리 굳이 존대하지 않아도 올바른 문장이 됩니다. 버스 정류장은 ‘머리’보다는 높임의 대상과 덜 밀접한 느낌을 주기 때문인 것 같습니다.

다른 예문을 보겠습니다.

(ㄷ) 고객님, 아메리카노가 {?나오셨습니다 / 나왔습니다}.

(ㄷ)에서 아메리카노에 ‘-시-‘를 써서 존대할 경우 어색합니다. 아메리카노는 높임의 대상인 ‘고객님’과 그다지 관련을 맺고 있지 않아서인듯 합니다.

그러나 높임의 대상과 맺는 관련성만으로 주체높임, 즉 ‘-시-‘의 쓰임을 설명하는 것은 다소 한계가 있는 것 같습니다. 아메리카노 또한 높임의 대상인 ‘고객님’과 그 정도는 약하지만 관련을 맺고 있다는 점에서, 머리나 버스 정류장의 예와 같이 존대하지 않아야 할 논리적인 근거가 부족하기 때문입니다.

이 경우 친구에게 해당 문장이 드러내는 상황을 전달한다고 가정하고 예문을 다시 살펴보겠습니다.

(1) 부장님이 머리가 하얗게 세셨더라.

(2) 선생님은 버스 정류장이 머셔서 불편하시겠더라.

(3) *고객님한테 아메리카노가 나오셨더라.

(ㄷ)과 (3)을 비교해서 보면, (ㄷ)은 청자가 화자의 눈앞에 있는 상황에서만 어색하나마 그 뜻이 통한다는 사실을 알 수 있습니다. (ㄱ)과 (ㄴ)의 ‘-시-‘가 주체 높임의 의미라면, (ㄷ)의 ‘-시-‘는 청자 높임의 의미를 드러내주기 때문인 것 같습니다.

화자의 태도

높임의 대상이 누구인지, 혹은 높임의 대상과 밀접한 관련을 맺는지 정도와 관계없이 화자가 사태를 파악하는 태도에 따라 ‘-시-‘를 쓸 수도 있고 뺄 수도 있습니다. 예문을 보겠습니다.

(가) 대통령이 공항에 도착했습니다.

(나) 대통령께서 공항에 도착하셨습니다.

위 예문과 같이 공적인 인물이나 역사적인 인물에 대해 방송과 같은 담화에서 대상을 객관화해서 기술할 때는 (가)처럼 ‘-시-‘를 붙이지 않습니다. 반면 존대 대상을 개인적인 관계로 파악하여 기술할 때는 (나)처럼 ‘-시-‘를 붙입니다.

주체높임법의 형식

주체경어법은 어휘, 문법적으로 실현됩니다. 어휘적 경어는 높임의 의미를 드러내는 어휘들로 실현되는 방식입니다. 이러한 명사에는 다음과 같은 예들이 있습니다. 이들은 주체경어뿐 아니라 다른 경어법에도 사용됩니다.

유표적 단어 : 진지, 말씀, 춘추, 댁, 생신, 부인

존칭접사 : 과장님, 형님, 아버님

존칭어근 : 귀사(貴社), 옥고(玉稿), 영식(令息)

동사의 예는 다음과 같습니다. 이들은 주체경어법에만 쓰입니다.

유표적 단어 : 별세하다, 서거하다, 승하하다, 돌아가다

보충법(‘-시-‘가 결합하면서 어간이 바뀜) : 먹다-잡수시다, 자다-주무시다, 있다-계시다

여기에서 ‘있다’를 높이면 ‘있으시다’가 되는 경우도 있습니다. 동사 ‘있다(stay)’의 존대형은 ‘계시다’이고, 형용사 ‘있다(be)’의 존대형은 ‘있으시다’입니다. 다음 예문과 같습니다.

할아버지께서 무슨 돈이 {있으시겠어요 / *계시겠어요}.

장관님의 말씀이 {있으시겠습니다 / *계시겠습니다}.

할아버지께서는 사랑방에 {*있으신다 / 계신다}.

문법적 경어는 주체높임이 조사, 어미 등 문법적 요소로 실현되는 경우를 가리킵니다. 존칭조사 ‘-께서’와 존칭 어미 ‘-시-‘로 실현됩니다. 하지만 ‘-께서’와 ‘-시-‘는 경어 강도 면에서 차이가 있습니다. 예문을 보겠습니다.

(A) {과장님이 오면 / *과장님께서 오면} 그 문제에 대해 여쭤 보자.

(B) {당신은 / *당신께서는} 언제 오셨소?

(A)에서처럼 ‘-께서’가 쓰인 문장은 ‘-시-‘가 없을 경우 비문이 됩니다. ‘-께서’로 표현하는 경어 강도라면 으레 ‘-시-‘가 요구됩니다. 경어 강도가 약한 ‘-시-‘는 (B)에서처럼 비상위자에게도 쓰일 수 있으나, 경어 강도가 강한 ‘-께서’는 비상위자에게는 쓰이기 어렵습니다.

이번 글에서는 최대엔트로피모델(Maximum Entropy model)의 파라메터 추정을 살펴보도록 하겠습니다. 이 글은 기본적으로 이곳을 참고하였습니다. 그럼 시작하겠습니다.

모델 정의

최대엔트로피 모델은 다음과 같이 정의됩니다.

위 식에서 $f$는 $x$와 $y$가 주어졌을 때 0 또는 1의 값을 반환하는 함수이며, $f_i(x,y)$는 자질벡터의 $i$번째 값을 나타냅니다. $λ$는 $f_i(x,y)$가 얼마나 중요한지 나타내는 가중치입니다. $Λ$는 그 요소가 ${λ_1, λ_2,…,λ_n}$인 가중치 벡터입니다.

최대우도추정

최대엔트로피모델 $P_Λ$에 대한 실제 데이터 분포(empirical distribution) $\widetilde{p}(x,y)$의 로그우도 함수는 다음과 같이 정의됩니다.

자질벡터와 데이터가 주어졌을 때 위 로그우도 함수를 최대화하는 파라메터 $Λ$를 찾는 것이 목적이 됩니다. ${ L }_{ \tilde { p } }$는 1차 도함수가 0인 지점에서 극값을 가지므로, 우리가 구하고자 하는 미지수인 $λ_i$에 대해 각각 편미분을 하여 정리하면 다음과 같습니다.

위 식에서 첫번째 항은 실제 데이터 분포에 대한 $f_i(x,y)$의 기대값입니다. 두번째 항은 모델 $P_Λ$에 대한 $f_i(x,y)$의 기대값입니다. 최적의 $λ_i$는 첫번째 항과 두번째 항이 정확히 같을 때 도출되므로, 최대우도추정은 실제 데이터의 확률분포와 모델이 예측하는 확률분포를 같게 만든다는 의미가 됩니다.

위 식은 딥러닝 모델의 손실함수인 크로스엔트로피(cross entropy)와 부호만 다를 뿐 정확히 같습니다. 크로스엔트로피는 두 확률분포 간 차이를 계산하는 함수입니다. 다시 말해 ‘우도의 최대화’와 ‘데이터-모델 두 확률분포 간 차이 최소화’가 본질적으로 동일한 의미를 지닌다는 겁니다.

파라메터 Λ 찾기

우리는 우도를 최대화하는 $Λ$를 구하고 싶습니다. 위 식을 보면 이러한 $Λ$를 구하려면 $P_Λ$를 알아야 합니다. 그런데 $P_Λ$를 계산하려면 $Λ$를 알아야 합니다. 돌고 도는 문제가 되는 셈이죠. 이같은 문제를 해결하기 위해 다음과 같이 새로운 파라메터 $Λ+Δ$를 설정해 보겠습니다.

[\Lambda +\Delta =\left{ { \lambda }{ 1 }+{ \delta }{ 1 },{ \lambda }{ 2 }+{ \delta }{ 2 },…{ \lambda }{ n }+{ \delta }{ n } \right}]

처음엔 우도를 최대화하는 $Λ$를 알 수 없으니 랜덤하게 값을 정해줍니다. $L_{ \tilde { p } }(Λ+Δ)-L_{ \tilde { p } }(Λ)$이 0 이상이라면 랜덤하게 정해준 $Λ$보다 $Λ+Δ$가 더 나은 파라메터라고 할 수 있을 것입니다. 몇 가지 수식 정리 과정을 거치면 $ L_{ \tilde { p } }(Λ+Δ)-L_{ \tilde { p } }(Λ)$의 하한(low-bound)은 다음과 같이 도출됩니다.

[\begin{align} { L }_{ \tilde { p } }(\Lambda +\Delta )-{ L }_{ \tilde { p } }(\Lambda )\ge &\sum _{ x,y }^{ }{ \tilde { p } \left( x,y \right) \sum _{ i }^{ }{ { { \delta }_{ i }f }_{ i }\left( x,y \right) } }+ \ &1-\sum _{ x }^{ }{ \tilde { p } \left( x \right) { P }_{ \Lambda }\left( y|x \right) \sum _{ i }^{ }{ \left( \frac { { f }_{ i }\left( x,y \right) }{ \sum _{ i }^{ }{ { f }_{ i }\left( x,y \right) } } \right) } } exp\left( { \delta }_{ i }\sum _{ i }^{ }{ { f }_{ i }\left( x,y \right) } \right) \end{align}]

위 식 우변을 $Β(Δ$|$Λ)$라고 치환해 보면 $L_{ \tilde { p } }(Λ+Δ)-L_{ \tilde { p } }(Λ)$의 하한은 $Β(Δ$|$Λ)$이 됩니다. $Λ$는 이미 랜덤하게 값을 정했기 때문에 이미 주어진 값입니다. 다시 말해 $Δ$만 알면 우도를 높일 수 있다고 기대할 수 있다는 이야기입니다. $Β(Δ$|$Λ)$는 1차 도함수가 0이 되는 지점에서 극값(최대값)을 가지기 때문에 우리가 구하고자 하는 미지수인 $δ_i$에 대해 각각 편미분을 하여 정리하면 다음과 같습니다.

[\begin{align} \frac { \partial Β \left( \Delta |\Lambda \right) }{ \partial { \delta }_{ i } } =&\sum _{ x,y }^{ }{ \tilde { p } \left( x,y \right) { f }_{ i }\left( x,y \right) } \ &-\sum _{ x }^{ }{ \tilde { p } \left( x \right) \sum _{ }^{ }{ { P }_{ \Lambda }\left( y|x \right) } { f }_{ i }\left( x,y \right) } exp\left( { \delta }_{ i }\sum _{ i }^{ }{ { f }_{ i }\left( x,y \right) } \right) \end{align}]

위 식을 보면 exp 안에 있는 미지수 $δ_i$를 제외하면 모두 주어진 상수값이어서 $δ_i$를 구할 수 있습니다. 지금까지 설명한 내용을 알고리즘 형태로 정리하면 다음과 같습니다.

1. $Λ={λ_1, λ_2,…,λ_n}$ 랜덤 초기화
2. $∂Β/∂δ_i=0$인 $δ_i$ 계산
3. $λ_i←λ_i+δ_i$
4. $Λ$가 수렴할 때까지 2, 3 반복

이와 같은 iterative scaling algorithm은 딥러닝에서 많이 쓰이는 그래디언트 디센트와 유사하다는 생각이 듭니다. 그래디언트 디센트는 주어진 데이터와 파라메터를 가지고 손실(loss)에 대한 그래디언트를 구해, 그래디언트의 반대 방향으로 파라메터를 업데이트합니다. 다만 iterative scaling algorithm은 ‘우도 최대화’, 그래디언트 디센트는 ‘손실 최소화’가 목적이기 때문에 파라메터를 업데이트할 때 각각 덧셈, 뺄셈을 해준다는 점에서 다른 것 같습니다.

이번 글에서는 Red-Black(RB) 트리에 대해 살펴보도록 하겠습니다. 이 글은 고려대 김선욱 교수님 강의와 위키피디아를 정리하였음을 먼저 밝힙니다. 그럼 시작하겠습니다.

concepts

RB 트리는 다음 다섯 가지 속성을 만족하는 이진탐색트리(Binary Search Tree)의 일종입니다.

1. 모든 노드는 빨간색, 검은색 둘 중 하나다.
2. 루트노드는 검은색이다.
3. 모든 잎새노드(NIL)는 검은색이다.
4. 어떤 노드가 빨간색이라면 두 개 자식노드는 모두 검은색이다. (따라서 빨간색 노드가 같은 경로상에 연이어 등장하지 않는다)
5. ‘각 노드~자손 잎새노드 사이의 모든 경로’에 대해 검은색 노드의 수가 같다.

RB 트리의 예는 다음 그림과 같습니다. 위 다섯가지 속성을 만족하고 있음을 확인할 수 있습니다.

노드의 높이 $h$는 해당 노드로부터 잎새노드에 이르는 가장 긴 경로의 엣지 수를 가리킵니다. 임의의 노드 $x$의 Black-height는 $x$부터 잎새노드에 이르는 경로상에 있는 검은색 노드의 수로 $bh(x)$라고 표기합니다. $x$가 검은색 노드일 경우 1을 빼주며 잎새노드(NIL)의 $bh$는 0입니다. $h$와 $bh$를 계산하는 예시는 다음과 같습니다.

insert

RB 트리의 삽입연산은 이진탐색트리의 삽입과 동일합니다. 그런데 삽입 후에도 RB 트리 다섯 가지 속성을 유지하고 있어야 합니다. 이 속성을 유지하기 위해 몇 가지 작업을 수행해 줍니다. (이진탐색트리의 연산을 기본으로 하되 이후 추가 작업을 수행해준다는 점에서 AVL 트리와 유사합니다)

삽입할 새 요소 $z$는 빨간색으로 둡니다. $z$와 검정색 부모노드를 공유하는 형제노드(sibling node)를 $y$라고 두겠습니다.

case1

(case 1-1) $y$가 빨간색이면서 $z$가 left child인 경우입니다. 아래 그림에서 $z$가 삽입되면서 빨간색 노드가 연이어 등장하게 됐습니다. RB 트리의 네 번째 속성에 위배된다는 이야기죠. 이 경우 노드의 색을 바꿔서 다시 칠해 줍니다.

(case 1-2) $y$가 빨간색이면서 $z$가 right child인 경우에도 색을 바꿔서 다시 칠해 줍니다.

case2, case3

(case2) $y$가 검은색이면서 $z$가 right child인 경우에도 빨간색 노드가 연이어 등장해 RB 트리의 네 번째 속성에 위배됩니다. case2인 경우 double rotation을 수행해 줍니다.

(case3) $y$가 검은색이면서 $z$가 left child인 경우에는 single rotation을 수행해 줍니다. single rotation과 double rotation 관련 자세한 내용은 이곳을 참고하시면 좋을 것 같습니다.

정리

시나리오별 rotation 수행은 다음과 같이 합니다. 삽입된 노드가 꺾여 있는 형태면 일단 rotation을 한 번 수행해 이것을 펴주고, 펴진 형태의 노드에 대해 rotation을 한 번 더 수행합니다. 이미 펴져 있는 형태로 노드가 삽입된 경우라면 rotation을 한 번만 수행합니다.

insert example

다음 숫자들을 차례대로 RB 트리에 삽입해 보겠습니다.

10, 85, 15, 70, 20, 60, 30, 50

삽입되는 새 노드의 색깔은 빨간색입니다. 그런데 10은 루트노드이므로 RB 트리의 1번 속성을 맞추기 위해 검정색으로 바꿔 줍니다. 다음과 같습니다.

85, 15를 삽입합니다. 그런데 빨간색 노드가 연이어 등장해 RB 트리의 4번 속성을 위반했네요. 그런데 새로 삽입된 15와 검은색 부모노드를 공유하는 형제노드(그림에는 안그려져 있지만 10의 왼쪽 자식노드는 검은색 NIL 노드입니다)가 검은색이고, 빨간색 두 노드가 꺾여져 있는 형태이므로 double rotation을 수행해 줍니다.

70을 삽입합니다. 빨간색 노드가 연이어 등장했습니다. 그런데 70과 검정색 부모를 공유하는 형제노드 10이 빨간색입니다. case1에 해당하므로 색을 15와 70은 빨간색, 10과 85는 검정색으로 다시 칠해 줍니다. 그런데 15는 루트노드이므로 검정색으로 그대로 놔둡니다.

20을 삽입합니다. 빨간색 노드가 연이어 등장했습니다. 그런데 20과 검정색 부모를 공유하는 형제노드 NIL(85의 right child)이 검정색입니다. 새로 삽입된 20이 노드 모양이 펴져 있는 형태이므로 case3에 해당하며 single rotation을 수행해 줍니다.

60을 삽입합니다. 빨간색 노드가 연이어 등장했습니다. 그런데 60과 검정색 부모를 공유하는 형제노드 85의 색이 빨간색입니다. case1에 해당하므로 70과 60의 색을 빨간색으로, 20과 85의 색을 검정색으로 다시 칠해 줍니다.

30을 삽입합니다. 빨간색 노드가 연이어 등장했습니다. 그런데 30과 검정색 부모를 공유하는 형제노드 NIL(20의 left child)이 검정색입니다. 그리고 꺾여 있는 형태로 case2에 해당합니다. double rotation을 수행합니다.

50을 삽입합니다. 빨간색 노드가 연이어 등장했습니다. 이번엔 조금 복잡하므로 차례대로 살펴보겠습니다.

• 50과 검정색 부모를 공유하는 형제노드 20이 빨간색입니다. case1에 해당합니다. 30과 50을 빨간색, 20과 60을 검정색으로 칠해 둡니다.
• 70, 30을 보니 빨간색 노드가 연이어 등장했습니다. 그런데 30과 검정색 부모를 공유하는 형제노드 10이 검정색입니다. 아울러 15, 70, 30이 꺾여져 있는 형태이므로 case2에 해당합니다. double rotaion을 수행해 줍니다.

delete

RB 트리에서 검정색 노드를 삭제할 때는 삭제 연산으로 RB 트리의 속성이 깨지지 않도록 해야 합니다. 이는 삽입 연산 때 고려했던 것과 유사한 방식으로 rotation을 구현함으로써 해결할 수 있습니다. 다만 빨간색 노드를 삭제할 때는 그냥 삭제를 수행하면 된다고 합니다.

계산복잡성

RB 트리 전체 높이를 $h$라고 할 때 삽입, 삭제, 검색 등 RB 트리의 계산복잡성은 $O(h)$입니다. 그런데 RB 트리의 노드 수가 $n$개라면 높이 상한은 $2\log{n+1}$이라고 합니다. 따라서 RB 트리의 계산복잡성은 $O(\log{n})$이 됩니다.

이번 글에서는 AVL 트리에 대해 살펴보도록 하겠습니다. 이 글은 고려대 김황남 교수님 강의와 위키피디아를 정리하였음을 먼저 밝힙니다. 파이썬 코드는 이곳을 참고하였습니다. 그럼 시작하겠습니다.

concepts

AVL 트리란 서브트리의 높이를 적절하게 제어해 전체 트리가 어느 한쪽으로 늘어지지 않도록 한 이진탐색트리(Binary Search Tree)의 일종입니다. 트리의 높이가 $h$일 때 이진탐색트리의 계산복잡성은 $O(h)$이기 때문에 균형된 트리를 만들어 $h$를 줄이고자 하는 발상에서 비롯됐습니다.

AVL 트리의 핵심 개념 가운데 하나가 Balance Factor(BF)입니다. 왼쪽 서브트리의 높이에서 오른쪽 서브트리의 높이를 뺀 것입니다. 두 서브트리의 높이가 같거나 잎새노드라면 BF는 0입니다(empty tree의 BF는 -1로 정의). 다음 그림을 보겠습니다.

위 이진탐색트리의 루트노드의 BF는 -1입니다. 왼쪽 서브트리의 높이는 1, 오른쪽은 2이기 때문입니다. 9의 BF는 1입니다. 9의 왼쪽 서브트리의 높이는 1, 오른쪽 서브트리는 존재하지 않아 0이기 때문입니다. 잎새노드인 3, 5, 7은 서브트리가 전혀 없기 때문에 BF는 0이 됩니다. BF가 클 수록 불균형 트리라고 할 수 있겠습니다.

AVL 트리는 요소를 삽입(insert)하거나 삭제(delete)하는 과정에서 서브트리를 재구성해 트리 전체의 균형을 맞춥니다. 삽입/삭제 연산시 BF가 일정 값 이상(보통 2) 혹은 이하(-2)로 바뀐 노드를 기준으로 그 서브트리들의 위치를 rotation하는 방식을 취합니다. rotation에는 두 가지 방식이 있는데 삽입 연산을 중심으로 살펴 보겠습니다.

single rotation

삽입 연산시 single rotation은 다음과 같은 방식으로 수행합니다. $U$는 주어진 이진탐색트리의 루트노드, $V$는 $U$의 왼쪽 자식노드, $Z$는 $U$의 오른쪽 서브트리입니다. $X$와 $Y$는 각각 $V$의 왼쪽, 오른쪽 서브트리를 가리킵니다. $X$, $Y$, $Z$의 높이가 모두 $h$라고 가정해 보겠습니다. 여기에서 $X$에 새로운 요소를 하나 추가해 보겠습니다. 이 경우 $V$와 $U$의 BF는 각각 1, 2가 됩니다.

$U$는 ‘BF가 2 이상, 2 이하일 때 rotation을 실시한다’는 조건에 부합합니다. $U$의 왼쪽 자식노드인 $V$를 기준으로 single rotation을 아래와 같이 실시해 줍니다. 기존 트리 구조에서 $Z$를 잡아 당겨 내려서 $V$를 새로운 루트노드로 만드는 겁니다. 요소 하나가 추가된 $X$의 높이만 $h+1$이고 나머지는 모두 $h$인 점을 감안하면 rotation 실시 후의 $U$, $V$의 BF는 각각 0, 0이 되어 균형 트리를 이룹니다.

single rotation을 일반화한 그림은 다음과 같습니다.

요소 하나 추가하는 데 이렇게까지 복잡하게 할 필요가 있을까 싶기도 합니다. 하지만 AVL 트리는 기본적으로 이진탐색트리라는 점에 유의해야 합니다. 삽입 연산을 수행하더라도, 부모노드는 왼쪽 자식노드보다 크거나 같고, 오른쪽 자식노드보다는 작거나 같다는 성질이 깨지지 않도록 해야 한다는 이야기입니다.

구체적인 예를 들어 볼까요. 아래 트리에서 0.8을 삽입해 보겠습니다. 0.8은 5보다 작으므로 3과 비교하고, 3보다 작으므로 1과 비교하고, 1보다 작고 1의 자식노드가 없습니다. 따라서 0.8이 들어갈 위치는 1의 왼쪽 자식노드가 됩니다. 기존의 이진탐색트리라면 여기에서 삽입 연산을 마칩니다.

하지만 서브트리 $X$에 0.8이 추가되면서 $V$와 $U$의 BF는 각각 1, 2이 됐습니다. $V$를 기준으로 rotation을 해줍니다. 이를 수행한 결과는 상단 우측 그림과 같습니다. 우선 모든 노드의 BF가 1 이하여서 균형을 이루고 있는 점을 확인할 수 있습니다.

이번엔 rotation 수행 결과로 이진탐색트리 속성이 깨졌는지 여부를 살펴볼까요? ‘중위탐색(inorder traverse) 결과가 정렬된 리스트를 이룬다’는 이진탐색트리의 기본 속성을 활용해 보겠습니다. 중위탐색은 왼쪽 서브트리-노드-오른쪽 서브트리 순으로 순회하는 방식입니다. 상단 우측 그림을 중위탐색으로 읽은 결과 요소 하나를 추가했는데도 이진탐색트리의 속성을 만족하고 있음을 살펴볼 수 있습니다.

0.8, 1, 3, 4, 5, 8

single rotation은 rotation을 한 차례 수행해 위와 같이 원하는 결과를 얻을 수 있는 경우를 가리킵니다. 삽입 연산의 single rotation은 다음 두 가지 경우에 $V$($U$의 자식노드, BF 절대값이 1이하)를 중심으로 실시합니다. ($U$는 BF의 절대값이 2 이상이면서 새 노드와 가장 가까운 조상 노드)

• $V$가 $U$의 왼쪽 자식노드, $V$의 왼쪽 서브트리에 새 노드 삽입 : $V$를 기준으로 right rotation
• $V$가 $U$의 오른쪽 자식노드, $V$의 오른쪽 서브트리에 새 노드 삽입 : $V$를 기준으로 left rotation

left/right rotation를 직관적으로 나타낸 그림은 각각 다음과 같습니다.

single rotation의 파이썬 구현

left rotation의 파이썬 코드는 다음과 같습니다.

    def lrotate(self):
        # 현재 트리의 기존 root를 A라고 두자
        A = self.node
        # 기존 root의 right child를 B라고 두자
        B = self.node.right.node
        # B의 left child(위 그림에서 베타)를 T라고 두자
        T = B.left.node
        
        # B를 새로운 root로 지정
        self.node = B
        # A를 root(B)의 새로운 left child로 지정
        B.left.node = A
        # T(위 그림에서 베타)를 A의 새로운 right child로 지정
        A.right.node = T

right rotation은 위의 반대로 수행하면 됩니다.

    def rrotate(self):
        A = self.node
        B = self.node.left.node
        T = B.right.node
        
        self.node = B
        B.right.node = A
        A.left.node = T

double rotation

rotation 한 차례만으로 원하는 삽입 결과를 내지 못하는 케이스가 존재합니다. 다음 두 가지 경우 double rotation을 수행해 줍니다. ($U$는 BF의 절대값이 2 이상이면서 새 노드와 가장 가까운 조상 노드, $V$는 $U$의 자식노드이면서 BF 절대값이 1이하)

• $V$가 $U$의 왼쪽 자식노드, $V$의 오른쪽 서브트리에 새 노드 삽입
• $V$가 $U$의 오른쪽 자식노드, $V$의 왼쪽 서브트리에 새 노드 삽입

아래 그림과 같은 트리 구조에서 $B$에 새로운 요소를 추가한다고 가정해 보겠습니다 (동그라미는 노드, 세모는 서브트리를 가리킵니다) 이렇게 되면 요소 하나를 삽입한 후의 $U$, $V$, $W$의 BF는 각각 2, -1, 1이 됩니다. 따라서 $U$를 루트노드로 하는 서브트리가 재구성 대상이 되겠습니다.

그런데 $V$는 $U$의 왼쪽 자식노드이고, 새 노드는 $V$의 오른쪽 서브트리에 추가됐으므로 double rotation을 수행해 줍니다. 여기에서 $W$는 $V$의 오른쪽 자식노드입니다. 다음과 같습니다.

• 첫번째 : $W$를 중심으로 left rotation 수행 ($A$를 잡아 당겨 내리는 과정)
• 두번째 : $W$를 중심으로 right rotation 수행 ($D$를 잡아 당겨 내리는 과정)

요소 삽입 후 서브트리들 가운데 $C$의 높이만 $h-1$이고 나머지는 모두 $h$인 점을 감안하면 double rotation 수행 후 $U$, $V$, $W$의 BF는 각각 -1, 0, 0이 되어서 균형을 이룹니다. 다음 그림과 같습니다.

구체적인 예를 들어보겠습니다. 하단 좌측그림과 같은 트리에 3.5를 추가한다고 가정해 봅시다. 3.5는 5보다 작으므로 3과 비교하고, 3보다 크므로 4와 비교하고, 4보다는 작고 4의 자식노드가 없습니다. 따라서 3.5가 들어갈 위치는 4의 왼쪽 자식노드가 됩니다. 기존의 이진탐색트리라면 여기에서 삽입 연산을 마칩니다.

하지만 3.5가 추가되면서 $V$와 $U$의 BF는 각각 -1, 2가 됐습니다. $U$를 루트노드로 하는 서브트리가 재구성 대상입니다. 그런데 $V$는 $U$의 왼쪽 자식노드이고, 새 노드(0.8)는 $V$의 오른쪽 서브트리에 추가됐므로 double rotation을 수행해 줍니다. $W$를 중심으로 left rotation을 수행한 뒤 다시 $W$를 중심으로 right rotation을 합니다. 이렇게 트리를 재구성하면 $W$가 루트노드가 됩니다.

이를 수행한 결과는 상단 우측 그림과 같습니다. 삽입이 우리가 원하는 대로 됐는지 볼까요? 우선 모든 노드의 BF가 1 이하여서 균형을 이루고 있는 점을 확인할 수 있습니다. 상단 우측 그림의 트리를 중위탐색으로 읽은 결과는 다음과 같습니다. 정렬된 순서대로 출력돼 이진탐색트리의 속성을 만족하고 있음을 살펴볼 수 있습니다.

1, 3, 3.5, 4, 5, 8

시나리오별 rotation

지금까지 설명한 내용을 네 개 시나리오별로 정리하면 다음과 같습니다. ($U$는 BF의 절대값이 2 이상인 노드)

• 시나리오1 : $U$의 왼쪽 자식노드의 왼쪽 서브트리 $A$에 새 노드 삽입 : single right rotation
• 시나리오2 : $U$의 왼쪽 자식노드의 오른쪽 서브트리 $B$에 새 노드 삽입 : double rotation(left-right)
• 시나리오3 : $U$의 오른쪽 자식노드의 왼쪽 서브트리 $C$에 새 노드 삽입 : double rotation(right-left)
• 시나리오4 : $U$의 오른쪽 자식노드의 오른쪽 서브트리 $D$에 새 노드 삽입 : single left rotation

이를 구현한 파이썬 코드는 다음과 같습니다.

    def rebalance(self):
        # 현재 노드(루트)~잎새노드에 이르는 경로의
        # 모든 노드에 대해 Balance Factor 업데이트
        self.update_heights(False)
        self.update_balances(False)
        
        # 현재 노드(루트, 위 그림에서 U)의 BF 절대값이 2 이상이면
        # 불균형트리이므로 rotation 수행
        while self.balance < -1 or self.balance > 1:
            # U의 Balance Factor가 2 이상이면
            # U의 왼쪽 서브트리 높이가 오른쪽보다 크므로
            # 시나리오1 혹은 시나리오2에 해당
            if self.balance > 1:
                # U의 왼쪽 자식노드의 왼쪽 서브트리보다
                # 오른쪽 서브트리의 높이가 클 경우 시나리오2에 해당
                # 우선 single left rotation
                if self.node.left.balance < 0:
                    self.node.left.lrotate()
                    # rotation이 됐으므로 BF 업데이트
                    self.update_heights()
                    self.update_balances()
                # U의 왼쪽 자식노드의 왼쪽 서브트리가
                # 오른쪽 서브트리보다 높이가 클 경우 시나리오1에 해당
                # single right rotation (시나리오2도 이 작업 수행)
                self.rrotate()
                # rotation이 됐으므로 BF 업데이트
                self.update_heights()
                self.update_balances()

		   # U의 Balance Factor가 -1 이하이면
            # U의 오른쪽 서브트리 높이가 왼쪽보다 크므로
            # 시나리오3 혹은 시나리오4에 해당
            if self.balance < -1:
			   # U의 오른쪽 자식노드의 오른쪽 서브트리보다
                # 왼쪽 서브트리의 높이가 클 경우 시나리오3에 해당
                # 우선 single right rotation
                if self.node.right.balance > 0:
                    self.node.right.rrotate()
                    # rotation이 됐으므로 BF 업데이트
                    self.update_heights()
                    self.update_balances()
                # U의 오른쪽 자식노드의 왼쪽 서브트리보다
                # 오른쪽 서브트리보다 높이가 클 경우 시나리오4에 해당
                # single left rotation (시나리오2도 이 작업 수행)
                self.lrotate()
                # rotation이 됐으므로 BF 업데이트
                self.update_heights()
                self.update_balances()

삽입/삭제 연산

AVL 트리의 삽입 연산은 기본적으로 이진탐색트리와 동일합니다. 다만 마지막에 우리가 이미 정의해놓은 rebalance 함수를 호출하는 과정 하나가 다를 뿐입니다.

    def insert(self, key):
        tree = self.node
        newnode = Node(key)

        # empty tree일 경우
        if tree == None:
            # 새 값(key)을 empty tree의 루트(node)에 넣음
            self.node = newnode
            # 이 루트의 left/right에 새 empty tree 선언
            self.node.left = AVLTree()
            self.node.right = AVLTree()
            debug("Inserted key [" + str(key) + "]")

        # 현재 보고 있는 node가 비어있지 않고
        # 새 값이 현재 node의 값보다 작으면
        # 왼쪽 서브트리에 삽입 (재귀함수 호출)
        elif key < tree.key:
            self.node.left.insert(key)

        # 새 값이 현재 node의 값보다 크면
        # 오른쪽 서브트리에 삽입 (재귀함수 호출)
        elif key > tree.key:
            self.node.right.insert(key)

        else:
            debug("Key [" + str(key) + "] already in tree.")

        # 현재 노드(루트)에 대해 rebalancing
        # 재귀함수 형태로 호출되므로 트리 전체의 루트~새 잎새노드
        # 경로의 모든 노드에 대해 계산을 수행하게 됨
        self.rebalance()

삭제 연산도 이진탐색트리와 동일합니다. 다만 삭제 후에 Balance Factor가 깨진 노드가 있을 수 있으니 이를 위해 rebalance를 해 줍니다.

insert example

다음 숫자들을 순서대로 넣어 AVL 트리를 구축해 보겠습니다.

3, 2, 1, 4, 5, 6, 7, 16, 15, 14

1까지는 잎새노드에 붙이는 방식으로 삽입하면 됩니다.

그런데 1을 삽입하고 보니, 루트노드인 3의 왼쪽 서브트리 높이는 2, 오른쪽은 0이어서 BF는 2가 됐습니다. 루트노드를 기준으로 rotation을 수행해야 합니다. 그런데 2 노드는 루트노드의 왼쪽 자식노드이고, 새 노드(1)는 2 노드의 왼쪽 서브트리에 추가됐으므로 single rotation(right)을 수행해 줍니다. 다음과 같습니다.

4, 5를 순서대로 붙여 줍니다. 다음과 같습니다.

그런데 5을 삽입하고 보니, 루트노드의 BF는 -2입니다. 3 노드의 BF도 -2입니다. AVL 트리에서는 둘 중에 3 노드(BF가 2 이상이고 잎새노드로부터 가장 가까운 노드)를 기준으로 rotation을 수행합니다. 그런데 4는 3의 오른쪽 자식노드이고, 5는 3의 오른쪽 서브트리에 삽입됐으므로 single rotation(left)를 수행해 줍니다. 다음과 같습니다.

6을 삽입합니다.

6을 삽입하고 보니 루트노드의 BF가 -2입니다. 4 노드는 루트노드의 오른쪽 자식노드이고, 새 노드(6)는 4 노드의 오른쪽 서브트리에 삽입됐으므로 루트노드를 기준으로 single rotation(left)를 수행해 줍니다. 다음과 같습니다.

7을 삽입합니다.

7을 삽입하고 보니 5 노드의 BF가 -2입니다. 6은 5 노드의 오른쪽 자식노드이고, 새 노드(7)는 5 노드의 오른쪽 서브트리에 삽입됐습니다. 따라서 5 노드를 기준으로 single rotation(left)를 수행해 줍니다. 다음과 같습니다.

16과 15를 삽입합니다.

15를 삽입하고 보니 7 노드의 BF가 -3입니다. 16은 7 노드의 오른쪽 자식노드이고, 새 노드(15)는 16 노드의 오른쪽 서브트리에 삽입됐습니다. 따라서 7 노드를 기준으로 double rotation을 수행해 줍니다. 다음과 같습니다.

14를 삽입합니다.

14를 삽입하고 보니 6 노드의 BF가 -2입니다. 15는 6 노드의 오른쪽 자식노드이고, 새 노드(14)는 15 노드의 왼쪽 서브트리에 삽입됐습니다. 따라서 6 노드를 기준으로 double rotation을 수행해 줍니다. 다음과 같습니다.

계산복잡성

AVL 트리의 계산복잡성을 분석해 보겠습니다. 우선 삽입 연산부터 살펴보겠습니다.

AVL 트리는 이진탐색트리의 일종입니다. 이진탐색트리 삽입 연산의 계산복잡성은 트리의 높이가 $h$일 때 $O(h)$입니다. 그런데 AVL 트리는 여기에 추가로, 삽입 후에 Balance Factor를 계산하고, BF의 절대값이 2 이상이면서 새 잎새노드와 가장 가까운 조상노드에 대해 rotation을 수행해 줍니다.

BF 계산 대상은 새 잎새노드~루트노드에 이르는 경로의 모든 노드들이므로 $O(h)$만큼의 계산량이 필요합니다. AVL 트리(이진탐색트리)가 기본적으로 연결리스트로 구현되고, rotation 연산은 부모-자식 간의 관계만 변경해 주면 되기 때문에, single이든 double이든 계산복잡성은 $O(1)$입니다. 따라서 AVL 트리 삽입 연산의 계산복잡성은 BF 계산과 rotation 연산을 고려하더라도 $O(h)$가 됩니다.

AVL 트리 삭제 연산 역시 이진탐색트리와 동일한 $O(h)$입니다. AVL 트리는 여기에 더해 삭제 후에 BF를 계산하고, BF가 높아 균형이 깨진 노드에 대해 rotaion을 수행합니다. 각각 $O(h)$, $O(1)$이 추가됩니다. 따라서 AVL 트리 삭제 연산 역시 BF 계산과 rotation 연산을 고려하더라도 $O(h)$가 됩니다.

요컨대 AVL 트리 삽입/삭제 연산은 트리의 높이 $h$에 의존적이라는 이야기입니다. AVL 트리 노드 수가 $n$개일 때 높이 $h$의 하한은 $2\log_2{n}$이라고 합니다. 따라서 AVL 트리의 계산복잡성은 $O(h)=O(\log{n})$이 됩니다. 이는 $O(n)$인 이진탐색트리보다 낮은 것입니다. rotation 같은 복잡한 과정을 거쳐 트리의 높이를 줄여 계산량을 감소시키는 데 성공한 셈이죠.

전체 코드

파이썬 전체 코드는 이곳에 있습니다. 저도 저장 용도로 남깁니다.