devlog

특징트리의 모든 노드들은 오른쪽, 왼쪽 서브트리의 높이 차이를 {-1, 0, 1} 중 하나를 가짐노드 추가, 삭제 후 조건을 만족시키지 않는다면, 균형을 맞추는 작업을 진행한다. 노드 하나 씩 검사하며 만족하지 않는 노드가 발생한다면, 해당 노드에서 작업을 수행하면 된다.만족하지 않는 경우70에서 만족하지 않으므로 70을 기준으로 오른쪽 회전을 한다.60은 70이 원래 자신의 왼쪽 자식이 있었지만 비게 되었으므로 60을 70의 왼쪽 자녀로 해준다.노드의 삭제에서2번의 단계가 필요한 경우아래와 같은 경우 노랜 색만 집중을 해보면 60이 루트로 가야 완전 이진트리가 된다.1단계70을 기준으로 오른쪽으로 회전해 60을 70자리로 올려준다.2단계50을 기준으로 왼쪽 회전을 한다.이러면 완전 이진트리가 완성된다...

출처 : https://www.youtube.com/watch?v=bqkcoSm_rCsB tree아래와 같이 이진트리에서 확장해 자녀에 3개의 값을 저장하고 싶어 사용한 트리이다. 자녀를 최대 몇 개까지 가질 수 있게 할 것이냐가 중요하다.파라미터M = 각 노드의 최대 자녀 노두 수M-1 = 각 노도의 최대 key 수[M/2] = 각 노트의 최소 자녀 수 (루트랑 리프노드는 제외한다.)[M/2] - 1 = 각 노드의 최소 key 수  특징internal 노드의 key 수가 x라면 자녀 노드의 수는 언제나 x+1개이다.그러므로 아래와 같은 경우는 존재하지 못한다.즉 노드는 최소 하나의 key를 가지기 때문에, 몇 차 b tree인지 상관없이 최소 두 개의 자녀는 가진다.M이 정해지면 root를 제외하고는 ..

출처 : https://www.youtube.com/watch?v=2MdsebfJOyMnill 노드란존재하지 않음을 의미한다.자녀가 없을 때 자녀를 nill노드로 표현한다. 값이 있는 노드와 동등하게 취급한다.모든 nill노드는 블랙이다.레드 블랙 트리 특징루트 노드는 블랙, 모든 노드는 블랙 혹은 레드이다.레드가 연속할 수 없다.모든 Nill노드는 블랙이다.(리프노드)레드의 자녀는 모두 블랙이다.임의의 노드에서 nill노드까지의 블랙 노드의 수는 동일하다 (본인 제외)블랙 height = 노드 x에서 임의의 자손 nill까지 갈 때 경로의 모든 black의 수는 같다.부모와 두 자녀의 색을 바꾸어 주어도 5번 속성은 유지된다. 트리들의 삽입, 삭제하며 위 속성을 맞추다 보면 균형된 트리가 만들어진다...