Node<E>* find(int key){ // key 값이 일치하는 Node를 찾는다. // 없는 경우, 해당 key를 삽입시 위치할 leaf노드를 반환. Node<E> *p = root; while (p->element != NULL) { if (p->key < key) p = p->right; elseif (p->key > key) p = p->left; else break; } return p; }
intdepth(int key){ Node<E> *p = root; int depth = 0; while (p->element != NULL) { if (p->key < key) { p = p->right; depth++; } elseif (p->key > key) { p = p->left; depth++; } else break; } return depth; }
intinsert(int key, E* e){ Node<E> *p = find(key); if (p->element != NULL) //이미 있는 경우 return0;
p->key = key; p->element = e; p->color = RED; p->left = newNode<E>(); p->left->parent = p; // 새로운 left 생성 및 연결 p->right = newNode<E>(); p->right->parent = p; // 새로운 left 생성 및 연결 remedy(p); // 무결점 검사 return1; }
voidremedy(Node<E> *p){ if (p == root) { p->color = BLACK; return; } if (uncle(p) == NULL) return; if (p->color == RED && p->parent->color == RED) { // 더블 레드 발생 if (uncle(p)->color == BLACK) { // restructuring Node<E> *a = grandparent(p); Node<E> *b = p->parent; Node<E> *c = p; if (a == NULL || b == NULL || c == NULL) return; if (p->parent->left == p) { if (grandparent(p)->left == p->parent) { // /형태 /* 서브 트리 */ //Node<E> *t1 = c->left; //Node<E> *t2 = c->right; Node<E> *t3 = b->right; //Node<E> *t4 = a->right;
// 1. 재배열 b->parent = a->parent; if (a != root) { if (a->parent->left == a) a->parent->left = b; else a->parent->right = b; } //b->left = c; b->right = a; a->parent = b;