package com.ys.tree.twothreefour;
public class Tree234 {
    private Node root = new Node() ;
    /*public Tree234(){
        root = new Node();
    }*/
    //查找關(guān)鍵字值
    public int find(long key){
        Node curNode = root;
        int childNumber ;
        while(true){
            if((childNumber = curNode.findItem(key))!=-1){
                return childNumber;
            }else if(curNode.isLeaf()){//節(jié)點(diǎn)是葉節(jié)點(diǎn)
                return -1;
            }else{
                curNode = getNextChild(curNode,key);
            }
        }
    }
    public Node getNextChild(Node theNode,long theValue){
        int j;
        int numItems = theNode.getNumItems();
        for(j = 0 ; j < numItems ; j++){
            if(theValue < theNode.getItem(j).dData){
                return theNode.getChild(j);
            }
        }
        return theNode.getChild(j);
    }
    //插入數(shù)據(jù)項(xiàng)
    public void insert(long dValue){
        Node curNode = root;
        DataItem tempItem = new DataItem(dValue);
        while(true){
            if(curNode.isFull()){//如果節(jié)點(diǎn)滿數(shù)據(jù)項(xiàng)了，則分裂節(jié)點(diǎn)
                split(curNode);
                curNode = curNode.getParent();
                curNode = getNextChild(curNode, dValue);
            }else if(curNode.isLeaf()){//當(dāng)前節(jié)點(diǎn)是葉節(jié)點(diǎn)
                break;
            }else{
                curNode = getNextChild(curNode, dValue);
            }
        }//end while
        curNode.insertItem(tempItem);
    }
    public void split(Node thisNode){
        DataItem itemB,itemC;
        Node parent,child2,child3;
        int itemIndex;
        itemC = thisNode.removeItem();
        itemB = thisNode.removeItem();
        child2 = thisNode.disconnectChild(2);
        child3 = thisNode.disconnectChild(3);
        Node newRight = new Node();
        if(thisNode == root){//如果當(dāng)前節(jié)點(diǎn)是根節(jié)點(diǎn)，執(zhí)行根分裂
            root = new Node();
            parent = root;
            root.connectChild(0, thisNode);
        }else{
            parent = thisNode.getParent();
        }
        //處理父節(jié)點(diǎn)
        itemIndex = parent.insertItem(itemB);
        int n = parent.getNumItems();
        for(int j = n-1; j > itemIndex ; j--){
            Node temp = parent.disconnectChild(j);
            parent.connectChild(j+1, temp);
        }
        parent.connectChild(itemIndex+1, newRight);
        //處理新建的右節(jié)點(diǎn)
        newRight.insertItem(itemC);
        newRight.connectChild(0, child2);
        newRight.connectChild(1, child3);
    }
    //打印樹節(jié)點(diǎn)
    public void displayTree(){
        recDisplayTree(root,0,0);
    }
    private void recDisplayTree(Node thisNode,int level,int childNumber){
        System.out.println("levle="+level+" child="+childNumber+" ");
        thisNode.displayNode();
        int numItems = thisNode.getNumItems();
        for(int j = 0; j < numItems+1 ; j++){
            Node nextNode = thisNode.getChild(j);
            if(nextNode != null){
                recDisplayTree(nextNode, level+1, j);
            }else{
                return;
            }
        }
    }
    //數(shù)據(jù)項(xiàng)
    class DataItem{
        public long dData;
        public DataItem(long dData){
            this.dData = dData;
        }
        public void displayItem(){
            System.out.println("/"+dData);
        }
    }
    //節(jié)點(diǎn)
    class Node{
        private static final int ORDER = 4;
        private int numItems;//表示該節(jié)點(diǎn)有多少個(gè)數(shù)據(jù)項(xiàng)
        private Node parent;//父節(jié)點(diǎn)
        private Node childArray[] = new Node[ORDER];//存儲(chǔ)子節(jié)點(diǎn)的數(shù)組，最多有4個(gè)子節(jié)點(diǎn)
        private DataItem itemArray[] = new DataItem[ORDER-1];//存放數(shù)據(jù)項(xiàng)的數(shù)組，一個(gè)節(jié)點(diǎn)最多有三個(gè)數(shù)據(jù)項(xiàng)
        //連接子節(jié)點(diǎn)
        public void connectChild(int childNum,Node child){
            childArray[childNum] = child;
            if(child != null){
                child.parent = this;
            }
        }
        //斷開與子節(jié)點(diǎn)的連接，并返回該子節(jié)點(diǎn)
        public Node disconnectChild(int childNum){
            Node tempNode = childArray[childNum];
            childArray[childNum] = null;
            return tempNode;
        }
        //得到節(jié)點(diǎn)的某個(gè)子節(jié)點(diǎn)
        public Node getChild(int childNum){
            return childArray[childNum];
        }
        //得到父節(jié)點(diǎn)
        public Node getParent(){
            return parent;
        }
        //判斷是否是葉節(jié)點(diǎn)
        public boolean isLeaf(){
            return (childArray[0] == null)?true:false;
        }
        //得到節(jié)點(diǎn)數(shù)據(jù)項(xiàng)的個(gè)數(shù)
        public int getNumItems(){
            return numItems;
        }
        //得到節(jié)點(diǎn)的某個(gè)數(shù)據(jù)項(xiàng)
        public DataItem getItem(int index){
            return itemArray[index];
        }
        //判斷節(jié)點(diǎn)的數(shù)據(jù)項(xiàng)是否滿了（最多3個(gè)）
        public boolean isFull(){
            return (numItems == ORDER-1) ? true:false;
        }
        //找到數(shù)據(jù)項(xiàng)在節(jié)點(diǎn)中的位置
        public int findItem(long key){
            for(int j = 0 ; j < ORDER-1 ; j++){
                if(itemArray[j]==null){
                    break;
                }else if(itemArray[j].dData == key){
                    return j;
                }
            }
            return -1;
        }
        //將數(shù)據(jù)項(xiàng)插入到節(jié)點(diǎn)
        public int insertItem(DataItem newItem){
            numItems++;
            long newKey = newItem.dData;
            for(int j = ORDER-2 ; j >= 0 ; j--){
                if(itemArray[j] == null){//如果為空，繼續(xù)向前循環(huán)
                    continue;
                }else{
                    long itsKey = itemArray[j].dData;//保存節(jié)點(diǎn)某個(gè)位置的數(shù)據(jù)項(xiàng)
                    if(newKey < itsKey){//如果比新插入的數(shù)據(jù)項(xiàng)大
                        itemArray[j+1] = itemArray[j];//將大數(shù)據(jù)項(xiàng)向后移動(dòng)一位
                    }else{
                        itemArray[j+1] = newItem;//如果比新插入的數(shù)據(jù)項(xiàng)小，則直接插入
                        return j+1;
                    }
                }
            }
            //如果都為空，或者都比待插入的數(shù)據(jù)項(xiàng)大，則將待插入的數(shù)據(jù)項(xiàng)放在節(jié)點(diǎn)第一個(gè)位置
            itemArray[0] = newItem;
            return 0;
        }
        //移除節(jié)點(diǎn)的數(shù)據(jù)項(xiàng)
        public DataItem removeItem(){
            DataItem temp = itemArray[numItems-1];
            itemArray[numItems-1] = null;
            numItems--;
            return temp;
        }
        //打印節(jié)點(diǎn)的所有數(shù)據(jù)項(xiàng)
        public void displayNode(){
            for(int j = 0 ; j < numItems ; j++){
                itemArray[j].displayItem();
            }
            System.out.println("/");
        }
    }
}