多叉树:2-3-4树 博客分类： Tree

    平衡树多叉树,每个节点最多有4个子节点和3个数据项,2,3,4的含义是指一个节点可能含有的子节点的个数,效率比红黑树稍差.一般不允许出现重复关键字值.2-3-4树有以下特征:
    1、有一个数据项的节点总是有2个子节点(称为2-节点)
    2、有两个数据项的节点总是有3个子节点(称为3-节点)
    3、有三个数据项的节点总是有4个子节点(称为4-节点)

    简单的说,非叶节点的子节点树总是比它含有的数据项多1,叶节点可能含有一个,两个或三个数据项.空叶节点不存在.2-3-4树的规则如下:
    1、第一个子节点的关键字值小于父节点第一个数据项
    2、第二个子节点的关键字值小于父节点第二个数据项并大于第一个数据项
    3、第三个子节点的关键字值小于父节点第三个数据项并大于第二个数据项
    4、最后一个节点的关键字值大于父节点第三个数据项

插入操作:
    查找时没有碰到满节点时,插入很简单.找到合适的叶节点后,只要把新数据项插入进去就可以了.可能会涉及到在一个节点中移动一个或两个其他的数据项.如果节点已经满了,插入就变得复杂了.发生这种情况时,节点必须分裂以保持树的平衡.把要分裂节点中的数据项设为A,B,C
    1、创建一个新的节点,他是要分裂节点的兄弟节点,在要分裂节点的右边.
    2、数据项C移动到新节点中.
    3、数据项B移到要分裂节点的父节点中(如果要分裂的节点是根节点,就再创建一个新节点指             向根,并将要分裂的节点连接上去).
    4、要分裂节点的最右边的两个子节点连接到新的兄弟节上

删除操作:
    还是很蛋疼的操作,依然建议打作废标记...

最后,是关于红黑树的,虽然两种树看上去不一样,但是在数学上确实属于同构的,2-3-4树也能转化为一颗红黑树.
2-3-4树转化为红黑树规则:
    1、把每个2-节点转化为红黑树的黑色节点.
    2、把每个3-节点转化成一个子节点和一个父节点，子节点有两个自己的子节点，父节点 有另一个子节点，子节点涂成红色，父节点涂成黑色.
    3、把每个4-节点转化成一个父节点,两个子节点和四个孙子节点,子节点涂成红色,父节点涂成黑色.


tree代码:

public class Tree {
    private Node root;
    
    public Tree(){
        this.root = new Node();
    }
    
    /**
     * 查询数据项的值
     * @param key
     * @return
     */
    public Object find(int key){
        Item item = this.findItem(key);
        
        if(item != null && item.isValid()){
            return item.getValue();
        }else{
            return null;
        }
    }
    
    /**
     * 查询数据项
     * @param key
     * @return 
     */
    private Item findItem(int key){
        Node current = this.root;
        int index;
        
        while(true){
            if((index = current.findItem(key)) != -1){
                break;
            }else if(current.isLeaf()){
                return null;
            }else{
                current = this.getNextNode(current,key);
            }
        }
        
        return current.getItem(index);
    }
    
    /**
     * 插入一个新数据项
     * @param key
     * @param value 
     */
    public void insert(int key,Object value){
        Item item = this.findItem(key);
        
        if(item != null){
            item.setValid(true);
            item.setValue(value);
            return;
        }
        
        item = new Item(key, value);
        Node current = this.root;
        
        while(true){
            if(current.isFull()){
                //遇到数据项已满的节点,分裂
                this.split(current);
                //重新从上一级节点查询
                current = this.getNextNode(current.getParent(), key);
            }else if(current.isLeaf()){
                break;
            }else{
                current = this.getNextNode(current,key);
            }
        }
        
        current.insertItem(item);
    }
    
    /**
     * 删除数据项,这里还是采用最简单的打作废标记的办法
     * @param key 
     */
    public void remove(int key){
        Item item = this.findItem(key);
        
        if(item != null){
            item.setValid(false);
        }
    }
    
    /**
     * 分裂节点
     * @param node 
     */
    private void split(Node node){
        Item C = node.removeItem();
        Item B = node.removeItem();
          
        /**
         * 新建一个兄弟节点,在要分裂的节点右边,把最后一个数据项移到新节点,
         * 并把要分裂节点的右边两个子节点挂到新节点上
         */
        Node right = new Node();
        right.insertItem(C);
        right.connect(0, node.disconnect(2));
        right.connect(1, node.disconnect(3));
        
        /**
         * 将要分裂节点的中间一个数据项移动到其父节点(如果要分裂节点是根节点
         * ,就新建一个节点并指向根)
         */
        Node parent = node == this.root ? new Node() : node.getParent();
        if(node == this.root){
            parent.connect(0, node);
            this.root = parent;
        }
        
        int index = parent.insertItem(B);
        int n = parent.getItemSize();
        
        for(int i=n-1;i>index;i--){
            parent.connect(i + 1,parent.disconnect(i));
        }
        
        parent.connect(index + 1, right);
    }
    
    /**
     * 查找下一个节点
     * @param node
     * @param key
     * @return 
     */
    private Node getNextNode(Node node,int key){
        for(int i=0;i<node.getItemSize();i++){
            if(node.getItem(i).getKey() > key){
                return node.getChild(i);
            }
        }
        
        return node.getChild(node.getItemSize());
    }
}

node代码:

public class Node {
    private Item[] itemArray;
    private Node[] childArray;
    private Node parent;
    private int itemSize;
    
    public Node(){
        this.itemArray = new Item[3];
        this.childArray = new Node[4];
        this.itemSize = 0;
    }
    
    /**
     * 连接子节点
     * @param num 子节点所在位置:0,1,2,3
     * @param child 子节点
     */
    public void connect(int num,Node child){ 
        this.childArray[num] = child;
        
        if(child != null){
            child.parent = this;
        }
    }
    
    /**
     * 断开子节点连接并返回子节点
     * @param num 子节点所在位置:0,1,2,3
     * @return 断开的子节点
     */
    public Node disconnect(int num){
        Node node = this.childArray[num];
        this.childArray[num] = null;
        
        return node;
    }
    
    public Node getChild(int num){
        return this.childArray[num];
    }
    
    public boolean isLeaf(){
        return this.childArray[0] == null;
    }
    
    public boolean isFull(){
        return this.itemSize == 3;
    }
    
    /**
     * 通过key查找节点中数据项的下标
     * @param key
     * @return 下标,如果没有找到返回-1
     */
    public int findItem(int key){
        for(int i=0;i<this.itemSize;i++){
            if(this.getItem(i).getKey() == key){
                return i;
            }
        }
        
        return -1;
    }
    
    /**
     * 将新数据项插入节点并返回下标
     * @param item 数据项
     * @return 下标
     */
    public int insertItem(Item item){
        this.itemSize++;
        
        for(int i=this.itemSize-2;i>=0;i--){
            Item compare = this.getItem(i);
            
            if(compare.getKey() > item.getKey()){
                this.itemArray[i + 1] = compare;
            }else{
                this.itemArray[i + 1] = item;
                return i + 1;
            }
        }
        
        this.itemArray[0] = item;
        
        return 0;
    }
    
    /**
     * 删除并返回最后一个数据项
     * @return 删除的数据项
     */
    public Item removeItem(){
        Item item = this.itemArray[this.itemSize - 1];
        this.itemArray[this.itemSize - 1] = null;
        this.itemSize--;
        
        return item;
    }
    
    public int getItemSize(){
        return this.itemSize;
    }
    
    public Item getItem(int index){
        return this.itemArray[index];
    }
    
    public void setParent(Node parent){
        this.parent = parent;
    }
    
    public Node getParent(){
        return this.parent;
    }
}

item代码:

public class Item {
    private int key;
    private Object value;
    private boolean valid;
    
    public Item(){};
    
    public Item(int key,Object value){
        this.key = key;
        this.value = value;
        this.valid = true;
    }
    
    public int getKey() {
        return key;
    }

    public Object getValue() {
        return value;
    }

    public void setValue(Object value) {
        this.value = value;
    }
    
    public boolean isValid() {
        return valid;
    }

    public void setValid(boolean valid) {
        this.valid = valid;
    }
}