avl redblack 차이

모든 노드는 RED or BLACK root 와 leaf(NIL)은 BLACK 노드가 RED이면 자식은 모두 BLACK (No Double Red) 각 노드로부터 그 노드의 자손인 리프로 가는 경로들은 모두 같은 수의 BLACK 노드를 포함 NIL을 하나의 객체로 고나리하면 하나의 노드로 관리하기에 메모리 절야 까능 삽입 시 연속된 RED 해결 Recoloring: 삽입된 노드의 부모의 형제 색깔이 RED Restructing : 삽입된 노드의 부모의 형제 색깔이 BLACK인 경우, NULL인 경우 삭제 시 RED는 그냥 삭제 BLACK의 경우 삭제 연산으로 트리 속성을 깨지 않도록 복잡도 Space : O(n) 삽입, 삭제, 검색 : O(logn) AVL vs RB 검색 : AVL > RB (AVL가 ..