두 갈래 정렬 트 리 - BST

1240 단어
제목: "이 진 정렬 트 리 - BST" 날짜: 2015 - 06 - 25 09: 08: 54 categories: 데이터 구조 태그: 데이터 구조
왜 BST 가 있어 야 돼 요?
  • 검색 용 순서 저장 이 가장 빠 르 지만 순서 저장 은 삽입 / 삭제 등 작업 에 적합 하지 않 습 니 다.
  • BST 는 완벽 하 게 찾 는 동시에 삽입 과 삭제 작업 을 할 수 있 고 로 이 루어 진다.

  • 정의.
  • Binary Sort Tree;
  • 이 진 트 리 라 고도 부른다.
  • 왼쪽 나무 에 있 는 모든 결점 의 값 은 뿌리 결점 의 값 보다 작다.
  • 오른쪽 나무 에 있 는 모든 결점 의 값 은 뿌리 결점 의 값 보다 크다.

  • 특성
  • 이 진 트 리 에서 각 노드 키 워드 는 입 니 다.
  • 중간 순서 로 BST 를 옮 겨 다 니 는 것 은 서열 이다.

  • 조작 하 다.
  • 삽입 작업 이 간단 하여 최종 적 으로 도 < 2 의 결점 이 된 아이;
  • 삭제 작업 은 두 가지 상황 으로 나 뉜 다.
  • 결점 을 삭제 하고 한 아이 만 있 으 면 왼쪽 / 오른쪽 트 리 전 체 를 결점 을 삭제 하 는 위치 로 이동 합 니 다.
  • 결점 을 삭제 하 는 데 두 아이 가 있 으 면 BST 에서 이 결점 을 옮 겨 다 니 는 또는 결점 을 삭제 하 는 위 치 를 대체 하거나 (또는 결점 을 삭제 하 는 왼쪽 하위 트 리 의 순서 로 옮 겨 다 니 는 결점 을 삭제 하거나 결점 오른쪽 하위 트 리 의 순서 로 옮 겨 다 니 는 결점 을 삭제 하 는 위치 대신).


  • BST
  • 위의 그림: 무질서 한 직렬 BFXDYAC 는 데이터베이스 나 파일 에 저장 할 수 있 습 니 다 . 우 리 는 프로그램 을 쓸 때 이 를 꺼 낸 다음 에 BST 로 구성 하고 마지막 에 BST 를 조작 할 수 있 습 니 다 .

  • 토론 판도
    taolun-BST

    좋은 웹페이지 즐겨찾기