B 트 리 의 정의, 삽입, 삭제

10499 단어 데이터 구조B 나무
B 트 리 기본 정의:
B 트 리 는 디스크 나 다른 직접 액세스 하 는 보조 저장 장 치 를 위 한 균형 검색 트 리 입 니 다.
한 그루 의 B 나 무 는 다음 과 같은 성질 을 가 진 뿌리 나무 이다.
1. 각 노드 x 는 아래 의 속성 이 있 습 니 다:
    a. x. n, 현재 노드 x 에 저 장 된 키워드 갯 수;
    b. x. n 개의 키워드 자체, x. key [1], x. key [2], x. key [x. n] 를 비 내림차 로 저장 합 니 다.
        x.key[1]<=x.key[2]<=...<=x.key[x.n]
    c. s. leaf 의 불 값 은 x 가 잎 결점 이면 true 이 고 내부 결점 이면 false 입 니 다.
2. 각 내부 결점 x 에는 x. n + 1 개의 아이 결점 을 가리 키 는 지침 도 포함 되 어 있다.잎 결점 에는 아이 가 없고, 그 아이의 지침 은 의미 가 없다.
3. 키워드 x. key [i] 는 각 하위 트 리 에 저 장 된 키워드 의 범 위 를 분할 합 니 다. 만약 k [i] 가 x. c [i] 를 뿌리 로 하 는 하위 트 리 에 저 장 된 키 를 임의로 사용한다 면,
    k1<=x.key[i]<=k2<=x.key[2]<=...<=x.key[x.n]<=k[x.n+1]
4. 모든 아이들 의 결점 은 같은 깊이, 즉 나무 높이 h 를 가지 고 있다.
5. 각 아이의 결점 에 포 함 된 키워드 의 개 수 는 지난 번 과 다음 번 이 며, B 트 리 라 고 불 리 는 최소 도수 t 로 고정 적 으로 표시 합 니 다.
    a.  뿌리 결점 을 제외 한 모든 결점 은 적어도 t 를 포함해 야 한다 - 1 개의 키 워드 를 가지 고 있 기 때문에 뿌리 결점 을 제외 하고 모든 내부 결점 에는 적어도 t 명의 아이 가 포함 되 어야 합 니 다.
    b. 각 노드 는 많아야 2t - 1 개의 키 워드 를 포함 할 수 있 기 때문에 각 내부 노드 는 많아야 2t 명의 아 이 를 포함 할 수 있다.내부 결점 이 2t - 1 키 워드 를 포함 할 때 우 리 는 이 결점 이 가득 하 다 고 말한다.
원본 코드 의 다운로드 링크 를 보 여 줍 니 다:http://download.csdn.net/detail/sky453589103/9041779
B 트 리 의 삽입 동작:
B 트 리 의 삽입 작업 을 진행 할 때 삽 입 된 노드 의 키워드 개수 가 2t - 1 을 초과 하 는 것 을 방지 해 야 합 니 다.만 결점 을 삽입 하려 면 분열 작업 을 해 야 한다.
전체 결점 을 각각 t - 1 개의 결점 을 포함 하 는 두 개의 결점 과 중간 에 있 는 키워드 로 나 누 어 줍 니 다. (아 이 를 잊 지 마 세 요.)
알고리즘 서론 에 서 는 편도 알고리즘 으로 분열 작업 을 합 니 다 (편도 알고리즘: 나무의 뿌리 부터 아래로 내 려 가 고 위로 돌아 가 는 작업 이 없습니다).
뿌리 부터 삽입 하고 길 을 따라 만 나 는 모든 만 결점 을 분열 시 키 면 삽 입 된 결점 이 만 결점 이 아니 라 는 것 을 보장 한다.
뿌리 결점 이 만 결점 일 때 는 뿌리 결점 을 분열 시 켜 새로운 뿌리 를 만들어 야 한다.
bool BSubTree::Insert(const KeyType key) {
  BSubTreeNodePtr r = _root;
  if (r->_MaxChildNum - 1 == r->_n) {
    BSubTreeNodePtr s = new BSubTreeNode(r->_MaxChildNum);
    s->Init();
    _root = s;
    s->_isleaf = false;
    s->_child[0] = r;
    Split(s, 0);
    return Insert_notfull(s, key);
  } else {
    return Insert_notfull(r ,key);
  }

  return false;
}

삽입 작업 의 보조 작업 은 루트 노드 에 삽입 되 지 않 았 을 때 이 보조 작업 으로 재 귀적 으로 삽입 해 야 합 니 다.
bool BSubTree::Insert_notfull(BSubTreeNodePtr pnode, const KeyType key) {
  unsigned int i = pnode->_n - 1;
  if (true == pnode->_isleaf) {
    //                key    
    //               ，          。
    while (i >= 0 && key < pnode->_key[i]){
      pnode->_key[i + 1] = pnode->_key[i];
      --i;
    }
    pnode->_key[i + 1] = key;
    ++pnode->_n;

    return true;
  } else {
    while (i >= 0 && key < pnode->_key[i]) {
      --i;
    }
    //         ，pnode->_key[i - 1] <= key <= pnode->_key[i]
    //  key <= pnode->_key[i] <= pnode->_child[i + 1]->key[0]<=
    //  pnode->_child[i + 1]->_key[pnode->_child[i]->_n - 1] <= pnode->key[i + 1]
    ++i;
    if (pnode->_MaxChildNum - 1 == pnode->_child[i]->_n) {
      //     key        
      //       key     _key[i]     _key[i]
      Split(pnode, i);
      //   i        ，  pnode->_key[i - 1] <= key <= pnode->_key[i]
      if(key > pnode->_key[i]) {
        ++i;
      }
    }
    return Insert_notfull(pnode->_child[i], key);
  }

B 나무의 분열 동작:
B 트 리 의 분열 작업 은 만 결점 의 후반 부 (t - 1 키워드, t 아이) 를 새로운 결점 에 직접 붙 이 고 중간 결점 (제 t 키워드, 첫 번 째 부터) 을 만 결점 의 부 결점 으로 옮 기 는 것 이다.시간 복잡 도 는 O (n) 이다.
BSubTreeNodePtr rightchild = new BSubTreeNode(pnode->_MaxChildNum);
  if (false == rightchild->Init()) {
    return false;
  }

  BSubTreeNodePtr leftchild  = pnode->_child[index];
  unsigned int t = leftchild->_MaxChildNum / 2;
  rightchild->_isleaf = leftchild->_isleaf;
  rightchild->_n = t - 1;
  //    leftchild， leftchild        rightchild
  for (unsigned int j = 0; j < t - 1; ++j) {
    rightchild->_key[j] = leftchild->_key[j + t];
  }
  if (!leftchild->_isleaf) {
    for (unsigned int j = 0; j < t; ++j) {
      rightchild->_child[j] = leftchild->_child[j + t];
    }
  }
  leftchild->_n = t - 1;
  //    index + 1          ，     pnode->key[index]      
  //     pnode->_child[index + 2] = pnode->nodep[index+ 1]
  for (unsigned int j = pnode->_n; j > index; --j) {
    pnode->_child[j + 1] = pnode->_child[j];
  }
  pnode->_child[index + 1] = rightchild;
  //    index         ，     pnode->key[index]       
  //     pnode->_key[index + 1] = pnode->_key[index]
  for (unsigned int j = pnode->_n - 1; j > index - 1; --j) {
    pnode->_key[j + 1] = pnode->_key[j];
  }
  //               。 
  pnode->_key[index] = leftchild->_key[t - 1];
  ++pnode->_n;

  return true;
}

B 트 리 삭제 동작:
B 트 리 의 삭제 작업 은 비교적 복잡 하 다.
B 트 리 의 삭 제 는 다음 세 가지 상황 을 포함한다.
1. 키워드 k 가 잎 노드 x 에 있 으 면 x 에서 삭제 합 니 다.
2. 만약 키워드 k 가 내부 결점 x 에 있다 면:
    a. x 의 왼쪽 형제 y 가 적어도 t 개의 키 워드 를 포함 하고 있다 면 y 를 뿌리 로 하 는 하위 트 리 에서 가장 큰 키 워드 를 찾 아 k1 을 재 귀적 으로 삭제 하고 k1 로 k 를 대체 합 니 다.
    b. 만약 에 x 의 형제 z 가 적어도 t 개의 키 워드 를 포함한다 면 z 를 뿌리 로 하 는 서브 트 리 에서 가장 작은 키 워드 를 찾 아 k1 을 재 귀적 으로 삭제 하고 k1 로 k 를 대체 합 니 다.
    c. 그렇지 않 으 면 좌우 형제 와 키워드 k 를 Y 에 합병 하면 Y 결점 에 2t - 1 개의 키워드 가 포함 되 고 x 도 z 를 가리 키 는 아 이 를 잃 게 된다.x 에서 z 를 가리 키 는 아 이 를 삭제 하고 z 의 메모 리 를 방출 하 며 Y 에서 k 를 재 귀적 으로 삭제 합 니 다.
3 키워드 k 가 현재 내부 노드 x 에 없 으 면 k 를 포함 하 는 하위 트 리 의 뿌리 x. c [i] 를 확인 합 니 다.만약 x. c [i] 의 키워드 개수 가 t - 1 이 라면 다음 두 가지 방법 으로 x. c [i] 에 키 워드 를 추가 해 야 합 니 다.
    a. x. [i] 는 t - 1 개의 키워드 만 있 지만 좌우 형제 가 적어도 t 개의 키 워드 를 포함 하고 있다 면 x 중의 한 키 워드 를 x. c [i] 로 내 려 가 x. c [i] 의 좌우 형제 중의 한 키 워드 를 x 로 올 리 고 해당 하 는 아이 지침 도 이동 해 야 합 니 다.
    b. x. c [i] 의 좌우 형제 가 t - 1 개의 키워드 만 있다 면 x. c [i] 를 그 중의 한 형제 와 합 쳐 새로운 결점 으로 만 듭 니 다.x 의 키 워드 를 새 노드 로 내 려 가서 아래로 이동 하 는 노드 를 새로운 노드 의 중간 키워드 라 고 합 니 다.
bool BSubTree::Delete(BSubTreeNodePtr pnode, const KeyType key) {
  unsigned int i = 0;
  unsigned int t = pnode->_MaxChildNum / 2;
  for (; i < pnode->_n; ++i) {
    if (key >= pnode->_key[i]) {
      break;
    }
  }
  if (key == pnode->_key[i]) {
    if (true == pnode->_isleaf) {
      while (i < pnode->_n - 1) {
        pnode->_key[i] = pnode->_key[i + 1];
        --pnode->_n;
        ++i;
      }
      return true;
    } else {
      if (pnode->_child[i]->_n > t - 1) {
        BSubTreeNodePtr p = pnode;
        while (!p->_isleaf) {
          p = p->_child[p->_n];
        }
        pnode->_key[i] = p->_key[p->_n - 1];

        return Delete(p,  p->_key[p->_n - 1]);
      }
      else if (pnode->_child[i + 1]->_n > t  -1) {
        BSubTreeNodePtr p = pnode;
        while (!p->_isleaf) {
          p = p->_child[0];
        }
        pnode->_key[i + 1] = p->_key[0];

        return Delete(p ,p->_key[0]);
      }
      else {
        //                         ，        ?
        unsigned int index;
        unsigned int j = pnode->_child[i]->_n;
        pnode->_child[i]->_key[j] = pnode->_key[i];
        ++j;
        for (index = 0; index < pnode->_child[i + 1]->_n; ++index, ++j) {
          pnode->_child[i]->_key[j] = pnode->_child[i + 1]->_key[index];
        }
        pnode->_child[i]->_n += pnode->_child[i + 1]->_n + 1;
        delete pnode->_child[i + 1];
        for (index = i; index < pnode->_n - 1; ++index) {
          pnode->_key[index] = pnode->_key[index + 1];
          pnode->_child[index + 1] = pnode->_child[index + 2];
        }

        return Delete(pnode->_child[i], key);
      }
     
    }
  }
  else if (false == pnode->_isleaf){
    if (pnode->_child[i]->_n > t - 1) {
      return Delete(pnode->_child[i], key);
    } else {
      if (i - 1 >=0 && pnode->_child[i - 1]->_n > t - 1) {
        //              pnode->_child[i] ,
        //  pnode->_child[i - 1]->_key[pnode->_child[i - 1]->_n]       
        for (unsigned int temp = pnode->_child[i]->_n - 1; temp >= 0; --temp) {
          pnode->_child[i]->_key[temp + 1] = pnode->_child[i]->_key[temp];
          pnode->_child[i]->_child[temp + 2] = pnode->_child[i]->_child[temp + 1];
        }
        pnode->_child[i]->_child[1] = pnode->_child[i]->_child[0];
        pnode->_child[i]->_key[0] = pnode->_key[i];
        pnode->_child[i]->_child[0] = pnode->_child[i - 1]->_child[pnode->_child[i - 1]->_n];
        ++pnode->_child[i]->_n;
        pnode->_key[i] = pnode->_child[i - 1]->_key[pnode->_child[i - 1]->_n];
        --pnode->_child[i - 1]->_n;
      }
      else if (pnode->_child[i + 1]->_n > t - 1) {
        //              pnode->_child[i] ,
        //  pnode->_child[i + 1]->_key[pnode->_child[i + 1]->_n]       
        pnode->_child[i]->_key[pnode->_child[i]->_n] = pnode->_key[i];
        pnode->_child[i]->_child[pnode->_child[i]->_n + 1] =
          pnode->_child[i + 1]->_child[0];
        ++pnode->_child[i]->_n;
        pnode->_key[i] = pnode->_child[i + 1]->_key[0];
        for (unsigned int temp = 0; temp < pnode->_child[i + 1]->_n - 1; ++temp) {
          pnode->_child[i + 1]->_key[temp] = pnode->_child[i + 1]->_key[temp + 1];
          pnode->_child[i + 1]->_child[temp] = pnode->_child[i + 1]->_child[temp + 1];
        }
        pnode->_child[i + 1]->_child[pnode->_child[i + 1]->_n - 1] =
          pnode->_child[i + 1]->_child[pnode->_child[i + 1]->_n];
        --pnode->_child[i + 1]->_n;
      }
      else {
        //    pnode->_child[i]                 t - 1
        //    pnode->_child[i]         。
        pnode->_child[i]->_key[pnode->_child[i]->_n] = pnode->_key[i];
        pnode->_child[i]->_child[pnode->_child[i]->_n + 1] = pnode->_child[i + 1]->_child[0];
        for (unsigned int temp = i; temp < pnode->_n - 1; ++temp) {
          pnode->_key[temp] = pnode->_key[temp + 1];
          pnode->_child[temp + 1] = pnode->_child[temp + 2];
        }
        --pnode->_n;

        return Delete(pnode->_child[i], key);
      }
    }
  }
  else {
    return false;
  }

  return true;
}
데이터베이스에 대한 모든 의존성 조회
22.03.17 React-typescript

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage