정의
컴퓨터 과학에서 B- 트리는 데이터를 순서대로 유지하는 자체 균형 트리입니다. 이 데이터 구조를 통해 데이터 검색, 순차적 액세스, 데이터 삽입 및 삭제 작업이 로그 시간에 완료 될 수 있습니다.
왜 b- 트리를 소개합니까?
우선, 우리가 앞에서 소개 한 빨간색과 검은 색 트리를 포함하여 입력을 메모리 에 저장하는 내부 검색 트리 입니다.
B-Tree는 이전 밸런스 트리 알고리즘의 확장입니다. 디스크 또는 네트워크 에 저장된 기호 테이블에 대한 외부 검색을 지원합니다. 이 파일은 이전에 고려한 입력보다 훨씬 클 수 있습니다 (메모리에 저장하기 어려운).
컨텐츠는 디스크에 저장되므로 트리 깊이의 큰 깊이 (디스크 읽기 및 쓰기 속도가 제한됨)로 인해 디스크 I/O 읽기 및 쓰기가 너무 자주 읽어서 비효율적 인 쿼리 효율성으로 이어집니다.
그런 다음 나무의 깊이를 줄이는 것이 자연스럽게 중요합니다. 따라서 B- 트리, 다중 방향 검색 트리를 소개합니다.
특징
나무의 각 노드에는 대부분의 어린이가 포함됩니다 (m> = 2).
루트 노드 및 리프 노드를 제외하고 각 노드는 최소한 [Ceil (m/2)] 어린이 (여기서 Ceil (x)은 상한을 취하는 함수입니다);
루트 노드가 잎 노드가 아닌 경우, 어린이를위한 루트 노드는 2 명 이상이됩니다., 루트 노드는 리프 노드이며, 전체 트리는 하나의 루트 노드 만 있습니다);
모든 잎 노드는 동일한 레이어 (하단 층)에 나타나고 리프 노드는 외부 노드이며 컨텐츠, 즉 키와 값을 저장합니다 .
다른 노드는 내부 노드로, 인덱스, 즉 키와 다음으로 저장됩니다 .
내부 노드의 키워드 : k [1], k [2],…, k [m-1]; 및 k [i] <k [i+1];
내용 노드 옆에있는 포인터 : p [1], p [2],…, p [m]; 여기서 p [1]은 키워드가 k [1]보다 작은 하위 트리를 가리키고, p [m]은 키워드가 k [m-1]보다 큰 하위 트리를 가리키고, 다른 p [i]는 키워드 (k [i-1], k [i])를 가진 하위 트리를 가리킨다.
예 : (M = 3)
찾아 삽입하십시오
편의를 위해 여기에는 특수한 센티넬 키가 사용되는데,이 키는 다른 모든 키보다 작고 *로 표시됩니다.
처음에는 B- 트리에는 하나의 루트 노드 만 포함되며 루트 노드에는 초기화시 Sentinel 키 만 포함됩니다.
내부 노드의 각 키는 노드와 관련이 있습니다. 모든 키는이 노드와 관련된 키보다 크거나 같지만 다른 모든 키보다 작습니다.
이러한 규칙은 코드를 크게 단순화 할 수 있습니다.
암호
다운로드하려면 클릭하십시오.
이 코드 구현은 Sentinel 키를 소개하고 코드 출력은이를 제거합니다.
코드에 Sentinel 키가 장착 된 B- 트리 (이미지를 볼 수 있도록 이미지를 저장하면 단어가 더 명확 해집니다) :
코드 별 B- 트리 출력 (이미지를 로컬로 저장하면 단어가 명확 해집니다) :
공개 클래스 btree <키는 비슷한 <key>, value> {// b-tree 노드 당 최대 어린이 = m-1 // (2 이상이어야합니다) 개인 정적 최종 int m = 4; 개인 노드 루트; // b- 트리 개인 int 높이의 루트; // b- 트리 개인 int n의 높이; // b- 트리의 키-값 쌍의 수 // 헬퍼 b- 트리 노드 데이터 유형 개인 정적 최종 클래스 노드 {private int m; // 어린이 수 개인 입장 [] children = 새 입장 [M]; // 어린이 배열 // k children private node (int k) {m = k; }} // 내부 노드 : 키와 다음으로 만 사용하십시오 // 외부 노드 : 키와 값만 개인 정적 클래스 항목 {private 비교 키; 개인 물체 val; 개인 노드 다음; // 배열 항목을 반복하기위한 도우미 필드 공개 항목 (비슷한 키, 객체 val, 노드 Next) {this.key = 키; this.val = val; this.next = 다음; }} /*** 빈 B- 트리를 초기화합니다. */ public btree () {root = 새 노드 (0); } /***이 기호 테이블이 비어 있으면 true를 반환합니다. * @return {@code true}이 기호 테이블이 비어있는 경우; {@code false} 그렇지 않으면 */ public boolean isempty () {return size () == 0; } /***이 기호 테이블에서 키 값 쌍의 수를 반환합니다. * @return이 기호 테이블의 키-값 쌍의 수 */ public int size () {return n; } /***이 b- 트리의 높이를 반환합니다 (디버깅의 경우). * * @return이 b-tree의 높이 */ public int height () {return height; } /*** 주어진 키와 관련된 값을 반환합니다. * * * @param key 키 * @return 주어진 키와 관련된 값은 기호 테이블 * 및 {@Code NULL} 주어진 키와 관련된 값을 기호 테이블 * @Throws nullPointerException {@code key} 인 경우 {@code null} */ public value get (key = null) {key null) {nullpointerexcement (key null) {key null) null "); } 반환 검색 (루트, 키, 높이); } @SuppressWarnings ( "선택 취소") 개인 값 검색 (Node X, 키 키, int ht) {entry [] children = x.children; // 가장 낮은 잎 노드로의 외부 노드, 트래버스 if (ht == 0) {for (int j = 0; j <xm; j ++) {if (eq (key, children [j] .key)) {return (value) children [j] .val; }}} // 내부 노드는 다음 주소를 재귀 적으로 검색합니다 {for (int J = 0; }}} return null; } /** * 키가 이미 기호 테이블에있는 경우 키 값 쌍을 기호 테이블에 삽입하여 기상 값을 새 값으로 덮어 씁니다. * 값이 {@code null} 인 경우 기호 테이블에서 키를 효과적으로 삭제합니다. * * @param key 키 * @param val 값 * @throws nullpointerexception {@code key}가 {@code null} */ public void put (key key, value val) {if (key == null) {throw new nullpointerexception ( "key null이 아닌"); } 노드 u = 삽입 (루트, 키, val, 높이); // 분할 n ++ 후 생성 된 오른쪽 노드; if (u == null) {return; } // 루트 재구성 루트 노드 t = 새 노드 (2)를 분할해야합니다. T.Children [0] = 새 항목 (root.children [0] .key, null, root); T.Children [1] = 새로운 입장 (U.Children [0] .Key, NULL, U); root = t; 높이 ++; } 개인 노드 인서트 (노드 h, 키 키, value val, int ht) {int j; 항목 t = 새 항목 (키, val, null); // 외부 노드 외부 노드, 리프 노드이기도합니다. 트리의 바닥에서 내용 값은 (ht == 0) {for (j = 0; j <hm; j ++) {if (덜 (key, h.children [j] .key)) {break; }}} // 노드 내부의 내부 노드는 다음 주소 {for (j = 0; if (u == null) {return null; } t.key = U.Children [0] .key; t.next = u; 부서지다; }}} for (int i = hm; i> j; i-) {h.children [i] = h.children [i-1]; } h.children [j] = t; H.M ++; if (hm <m) {return null; } else {// 분할 노드 리턴 스플릿 (h); }} // 반본 노드 분할 (Node H)에서 분할 노드 {Node t = 새 노드 (m/2); hm = m/2; for (int j = 0; } return t; } /***이 b- 트리의 문자열 표현을 반환합니다 (디버깅의 경우). * * @return이 b- 트리의 문자열 표현. */ public String toString () {return tostring (루트, 높이 "") + "/ n"; } private String toString (node h, int ht, String Indent) {StringBuilder s = new StringBuilder (); 입장 [] 어린이 = H.Children; if (ht == 0) {for (int j = 0; }} else {for (int j = 0; } s.append (Tostring (children [j] .next, ht-1, Indent + "")); }} return s.toString (); } // 비교 함수 - 캐스트를 피하기 위해 키 대신 비교할 수 있도록 만듭니다. } private boolean eq (비슷한 k1, 비슷한 k2) {return k1.compareto (k2) == 0; } /*** 단위는 {@code btree} 데이터 유형을 테스트합니다. * * @param args 명령 줄 인수 */ public static void main (String [] args) {btree <string, String> st = new btree <String, String> (); St.Put ( "www.cs.princeton.edu", "128.112.136.12"); St.Put ( "www.cs.princeton.edu", "128.112.136.11"); St.put ( "www.princeton.edu", "128.112.128.15"); St.put ( "www.yale.edu", "130.132.143.21"); St.Put ( "www.simpsons.com", "209.052.165.60"); St.put ( "www.apple.com", "17.112.152.32"); St.put ( "www.amazon.com", "207.171.182.16"); St.Put ( "www.ebay.com", "66.135.192.87"); St.Put ( "www.cnn.com", "64.236.16.20"); St.put ( "www.google.com", "216.239.41.99"); St.Put ( "www.nytimes.com", "199.239.136.200"); St.Put ( "www.microsoft.com", "207.126.99.140"); St.Put ( "www.dell.com", "143.166.224.230"); St.put ( "www.slashdot.org", "66.35.250.151"); St.Put ( "www.espn.com", "199.181.135.201"); St.Put ( "www.weather.com", "63.111.66.11"); St.put ( "www.yahoo.com", "216.109.118.65"); System.out.println ( "cs.princeton.edu :" + st.get ( "www.cs.princeton.edu"); System.out.println ( "hardvardsucks.com :" + st.get ( "www.harvardsucks.com"); System.out.println ( "simpsons.com :" + st.get ( "www.simpsons.com")); System.out.println ( "apple.com :" + st.get ( "www.apple.com")); System.out.println ( "ebay.com :" + st.get ( "www.ebay.com")); System.out.println ( "dell.com :" + st.get ( "www.dell.com")); System.out.println ( "size :" + st.size ()); System.out.println ( "높이 :" + st.height ()); System.out.println (st); System.out.println (); }} 산출:
cs.princeton.edu : 128.112.136.12
hardvardsucks.com : null
simpsons.com : 209.052.165.60
Apple.com : 17.112.152.32
ebay.com : 66.135.192.87
dell.com : 143.166.224.230
크기 : 17
높이 : 2
www.amazon.com 207.171.182.16
www.apple.com 17.112.152.32
www.cnn.com 64.236.16.20
(www.cs.princeton.edu)
www.cs.princeton.edu 128.112.136.12
www.cs.princeton.edu 128.112.136.11
www.dell.com 143.166.224.230
(www.ebay.com)
www.ebay.com 66.135.192.87
www.espn.com 199.181.135.201
www.google.com 216.239.41.99
(www.microsoft.com)
www.microsoft.com 207.126.99.140
www.nytimes.com 199.239.136.200
(www.princeton.edu)
www.princeton.edu 128.112.128.15
www.simpsons.com 209.052.165.60
(www.slashdot.org)
www.slashdot.org 66.35.250.151
www.weather.com 63.111.66.11
(www.yahoo.com)
www.yahoo.com 216.109.118.65
www.yale.edu 130.132.143.21
위는이 기사의 모든 내용입니다. 모든 사람의 학습에 도움이되기를 바랍니다. 모든 사람이 wulin.com을 더 지원하기를 바랍니다.