나무 - 2 - 3 - 4 나무, B 나무 (B + 나무, B - 나무)

목차

2 - 3 - 4 나무

B 나무

2 - 3 - 4 나무
2 - 3 - 4 나무의 특징:

밸 런 스 트 리 입 니 다.

각 노드 에 최대 세 개의 데이터 항목 을 저장 할 수 있다.

빈 노드 가 존재 하지 않 습 니 다.

잎 노드 는 데이터 항목 에 하위 노드 가 없 을 수 있다.

데이터 항목 을 삽입 할 때 데 이 터 는 항상 잎 노드 에 삽입 된다 는 점 이 중요 하 다.

비 엽 노드 에 있어 데이터 항목 이 있 는 노드 는 항상 두 개의 키 노드 가 있다.두 개의 데이터 항목 이 있 는 노드 는 항상 세 개의 키 노드 가 있다.세 개의 데이터 항목 이 있 는 노드 는 항상 네 개의 키 노드 가 있다.L: 하위 노드 의 개 수 를 나타 낸다.D: 데이터 항목 의 개 수 를 표시 합 니 다.비 엽 노드: L = D + 1;하위 노드 개수 = 데이터 항목 개수 + 1;

데이터 규칙 삽입:

한 노드 에 있어 오른쪽 데이터 항목 은 왼쪽 데이터 항목 보다 크다.

부자 노드 에 있어 첫 번 째 서브 노드 의 모든 데이터 항목 은 부모 노드 의 첫 번 째 데이터 항목 보다 작고 두 번 째 바이트 의 모든 데이터 항목 은 부모 노드 의 첫 번 째 데이터 항목 보다 크 며 부모 노드 의 두 번 째 데이터 항목 보다 작다.

삽입 할 때 노드 데이터 가 가득 차 서 분리 해 야 합 니 다.

효율: 붉 은 검 은 나무, 이 진 트 리 와 의 검색 효율 이 떨 어 지지 않 습 니 다.
코드:

/**
 * @ClassName DataItem
 * @Descriptionn     
 * @Author lzq
 * @Date 2019/6/20 14:43
 * @Version 1.0
 **/
public class DataItem {
    public long data;

    public DataItem(long dd) {
        this.data = dd;
    }

    public void show() {
        System.out.print("/"+data);
    }
}

/**
 * @ClassName TreeNode
 * @Description 2-3-4    
 * @Author lzq
 * @Date 2019/6/20 14:45
 * @Version 1.0
 **/
public class TreeNode {
    private static final int ORDER = 4;  //       
    private int numitems;  //           
    private TreeNode parent;  //     
    private TreeNode[] childArray = new TreeNode[ORDER];  //        
    private DataItem[] itemsArray = new DataItem[ORDER-1];  //     

    /**
     *     
     * @param child
     * @return
     */
    public TreeNode getChild(int child) {
        return childArray[child];
    }

    /**
     *      
     * @return
     */
    public TreeNode getParent() {
        return parent;
    }

    /**
     *           
     * @return
     */
    public boolean isLeaf() {
        //                    
        return childArray[0] == null;
    }

    /**
     *        
     * @return
     */
    public int getNumitems() {
        return numitems;
    }

    /**
     *        
     * @param index
     * @return
     */
    public DataItem getItem(int index) {
        return itemsArray[index];
    }

    /**
     *            
     * @return
     */
    public boolean isFull() {
        return numitems == (ORDER-1);
    }

    /**
     *        
     * @param childNum           
     * @param child         
     */
    public void connectChild(int childNum,TreeNode child) {
        childArray[childNum] = child;
        if(child != null) {
            child.parent = this;
        }
    }

    /**
     *      
     * @param childNum
     * @return
     */
    public TreeNode disConnectChild(int childNum){
        TreeNode temp = childArray[childNum];
        childArray[childNum] = null;
        return temp;
    }

    /**
     *                
     * @param key
     * @return
     */
    public int findItem(long key) {
        for (int i = 0; i < ORDER-1; i++) {
            if(itemsArray[i] == null) { //           ，     
                break;
            }else if(itemsArray[i].data == key){
                return i;  //       ，    
            }
        }
        return -1;  //   
    }

    /**
     *      
     * @param newIteam
     * @return
     */
    public int insertItem(DataItem newIteam) {
        numitems++;
        long newKey = newIteam.data; //         
        for (int i = ORDER-2; i >= 0;i--) {
            if(itemsArray[i] == null) {
                continue;
            }else {
                long temp = itemsArray[i].data;  //        
                if(newKey < temp) {
                    itemsArray[i+1] = itemsArray[i];  //    
                }else {
                    itemsArray[i+1] = newIteam;
                    return i+1;
                }
            }
        }
        itemsArray[0] = newIteam;
        return 0;
    }

    /**
     *        
     *          
     * @return
     */
    public DataItem removeIteam() {
        DataItem temp = itemsArray[numitems-1];  //         （        ）
        itemsArray[numitems-1] = null;
        numitems--;
        return temp;
    }

    /**
     *     
     */
    public void show() {
        for (int i = 0; i < numitems; i++) {
            itemsArray[i].show();
        }
        System.out.println("/");
    }
}

/**
 * @ClassName Tree234
 * @Description 2-3-4 
 * @Author lzq
 * @Date 2019/6/20 15:13
 * @Version 1.0
 **/
public class Tree234 {
    private TreeNode root = new TreeNode(); //   

    /**
     *      
     * @param key
     * @return
     */
    public int find(long key) {
        TreeNode cur = root;  //     
        int childNumber;

        while (true) {
            if((childNumber = cur.findItem(key)) != -1) {  //   
                return childNumber;
            }else if(cur.isLeaf()) { //         
                return -1;  //   
            }else {
                cur = getNextChild(cur,key); //       ，         
            }
        }
    }

    /**
     *         
     * @param cur
     * @param key
     * @return
     */
    private TreeNode getNextChild(TreeNode cur, long key) {
        int i;
        int numItems = cur.getNumitems();  //       
        for (i = 0; i < numItems; i++) {
            if(key < cur.getItem(i).data) {
                return cur.getChild(i);
            }
        }
        return cur.getChild(i);
    }

    /**
     *      
     * @param value
     */
    public void insert(long value) {
        TreeNode cur = root;
        DataItem temp = new DataItem(value);  //   

        //             
        while (true) {
            if(cur.isFull()) {  //        ，        
                split(cur);  //    
                cur = cur.getParent();  //              
                cur = getNextChild(cur,value); //        
            }else if(cur.isLeaf()) {  //                
                break;
            }else {
                cur = getNextChild(cur,value);
            }
        }
        cur.insertItem(temp);  //         
    }

    /**
     *     
     *       
     * @param thisNode
     */
    private void split(TreeNode thisNode) {
        DataItem itemB,itemC;
        TreeNode parent,child2,child3;
        int itemIndex;

        itemC = thisNode.removeIteam();  //               
        itemB = thisNode.removeIteam();  //      
        child2 = thisNode.disConnectChild(2);
        child3 = thisNode.disConnectChild(3);

        TreeNode newRight = new TreeNode();

        if(thisNode == root) {  //           
            root = new TreeNode();
            parent = root;
            root.connectChild(0,thisNode);
        }else {
            parent = thisNode.getParent();
        }

        itemIndex = parent.insertItem(itemB);
        int n = parent.getNumitems();

        for (int i = n-1;i > itemIndex;i--) {
            TreeNode temp = parent.disConnectChild(i);
            parent.connectChild(i+1,temp);
        }

        parent.connectChild(itemIndex+1,newRight);
        newRight.insertItem(itemC);
        newRight.connectChild(0,child2);
        newRight.connectChild(1,child3);
    }



    public void show() {
        print(root,0,0);
    }

    /**
     *     
     * @param node     
     * @param level   
     * @param childNum            
     */
    private void print(TreeNode node,int level,int childNum) {
        System.out.print("  ="+level+"\t      "+childNum+"    \t");
        node.show();

        int numItems = node.getNumitems(); //      
        for (int i = 0; i < numItems+1; i++) {
            TreeNode next = node.getChild(i);
            if(next != null) {
                print(next,level+1,i);  //     
            }else {  //       
                return;
            }
        }
    }
}

테스트 클래스:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * @ClassName TestDemo
 * @Description 2-3-4 
 * @Author lzq
 * @Date 2019/6/20 15:47
 * @Version 1.0
 **/
public class TestDemo {
    public static void main(String[] args) throws IOException{
        long value;
        Tree234 theTree = new Tree234();
        theTree.insert(50);
        theTree.insert(40);
        theTree.insert(60);
        theTree.insert(30);
        theTree.insert(70);
        while (true) {
            System.out.println("--------------------------");
            System.out.println("    (s)、  (i)    (f)");
            char choice = getChar();
            switch (choice) {
                case 's':
                    theTree.show();
                    break;
                case 'i':
                    System.out.println("       ");
                    value = getInt();
                    theTree.insert(value);
                    break;
                case 'f':
                    System.out.println("         ");
                    value = getInt();
                    int found = theTree.find(value);
                    if(found != -1) {
                        System.out.println("   "+value);
                    }else {
                        System.out.println("      "+value);
                    }
                    break;
                default:
                    System.out.println("    ");
                    break;
            }
        }
    }

    public static String getString() throws IOException{
        InputStreamReader isr = new InputStreamReader(System.in);
        BufferedReader br = new BufferedReader(isr);
        return br.readLine();
    }

    public static char getChar() throws IOException{
        return getString().charAt(0);
    }

    public static int getInt() throws IOException {
        return Integer.parseInt(getString());
    }
}

실행 결과:

--------------------------
    (s)、  (i)    (f)
s
  =0	      0    	/50/
  =1	      0    	/30/40/
  =1	      1    	/60/70/
--------------------------
    (s)、  (i)    (f)
i
       
35
--------------------------
    (s)、  (i)    (f)
s
  =0	      0    	/50/
  =1	      0    	/30/35/40/
  =1	      1    	/60/70/
--------------------------
    (s)、  (i)    (f)
i
       
45
--------------------------
    (s)、  (i)    (f)
s
  =0	      0    	/35/50/
  =1	      0    	/30/
  =1	      1    	/40/45/
  =1	      2    	/60/70/
--------------------------
    (s)、  (i)    (f)
f
         
40
   40
--------------------------
    (s)、  (i)    (f)
f
         
78
      78
--------------------------
    (s)、  (i)    (f)

B 나무
2 - 3 - 4 나무 중 한 노드 에 최대 4 명의 아이 만 있 을 수 있 습 니 다. 그러면 모든 아이 가 더 많 으 면 이것 이 바로 B 나무 입 니 다.
B 나무, B - 나무, B + 나무, B * 나무 사이 의 관계