해킹왕 양선규

RB Tree(Red Black Tree) - 이진 탐색 트리(BST) 기반의 self balanced tree - 삽입/삭제는 BST와 동일하지만, 삽입/삭제 후 RB Tree의 5가지 속성을 만족하기 위한 재조정 작업이 필요하다. - 스스로 좌/우 서브트리의 균형을 맞춘다 - 서브트리 간 height 차이는 최대 2이다. RB Tree의 속성 5가지 1. 모든 노드는 red 혹은 black 2. 루트 노드는 black 3. 모든 nil 노드는 black nil 노드 - 존재하지 않음을 의미하는 노드 - 자녀가 없을 때 자녀를 nil 노드로 표기함 - nil노드는 값이 있는 노드와 동등하게 취급 - RB트리에서 leaf노드는 nil노드이다. 4. red의 자녀는 모두 black이다 = red는 연속적으..

이진 탐색 트리(Binary Search Tree, BST) - 왼쪽 서브트리는 부모 노드보다 작고 오른쪽 서브트리는 부모 노드보다 큰 이진 트리 - BST의 최소값은 “트리의 가장 왼쪽”에 존재한다 - BST의 최대값은 “트리의 가장 오른쪽”에 존재한다 이진 탐색 트리의 삽입 - 아무것도 없는 트리라면 그냥 삽입한다. - 삽입할 노드를 루트 노드부터 하나씩 비교한다. 루트 노드보다 작다면 왼쪽, 크다면 오른쪽으로 간다. 빈 자리를 찾을 때 까지 반복한다. - 같은 값을 가지는 노드는 없다. 이진 탐색 트리의 삭제/검색 - 삭제를 하려면 검색부터 해야 한다. - 찾을 노드를 기준으로, 루트 노드부터 하나씩 비교한다. 삽입할 때처럼 루트 노드보다 작다면 왼쪽, 크다면 오른쪽으로 간다. 값이 같다면 해당 노..