数据结构 - 树 - 2-3-4树

作者: faris_shi | 来源:发表于2018-02-17 02:53 被阅读48次

    1. 介绍

    2-3-4树 是平衡树,但不是二叉树,因为它可以有多个节点值,也可以有多个节点。它可以实现完美平衡

    2-3-4树的名字是根据子节点数来确定的。

    2-3-4树的key的种类:

    • 2-node: 一个key值,两个儿子节点。

    • 3-node: 两个key值,三个儿子节点。

    • 4-node: 三个key值,四个儿子节点。

    2-3-4树的子树:

    • 2-node: 左子树比key小,右子树比key大。

    • 3-node:左子树比第一个key小;中间子树比比第一个key大,比第二个key小;右子树比第二个key大。

    • 4-node:左子树比第一个key小;第二子树比比第一个key大,比第二个key小;第三子树比第二个key大,比第三个key小;右子树比第三个key大。

    2 类定义及属性

    public class TwoThreeFourTree<T extends Comparable<T>> {
    
        private static final int MAX_SIZE = 4;
    
        private TreeNode root;
    }
    

    2. 节点定义

    private static class TreeNode {
    
        int dataNum;
    
        int nodeNum;
    
        TreeNode[] nodes = new TreeNode[MAX_SIZE];
    
        Object[] datas = new Object[MAX_SIZE];
    
        public TreeNode(Object data) {
            dataNum++;
            datas[dataNum - 1] = data;
        }
    
        public void appendData(Object data, int index) {
            System.arraycopy(datas, index, datas, index + 1, dataNum - index);
            datas[index] = data;
            dataNum++;
        }
    
        public Object getMidData() {
            return datas[dataNum / 2];
        }
    
        public void appendNode(TreeNode node) {
            if (node == null) {
                return;
            }
            nodeNum++;
            nodes[nodeNum - 1] = node;
        }
    }
    

    3. 查找

    234树的查找类似于二叉查找树,根据data值得比较来递归所在的子树即可。

    • 比较要查找的值与data值数组,来判断在哪个子树中。
    • 获取对应的子树,继续递归查找
    public T max() {
        if (root == null) {
            return null;
        }
        TreeNode node = root;
        while (node.nodeNum != 0) {
            node = node.nodes[node.nodeNum - 1];
        }
        if (node.dataNum == 0) {
            return null;
        }
        return convert(node.datas[node.dataNum - 1]);
    }
    
    public T min() {
        if (root == null) {
            return null;
        }
        TreeNode node = root;
        while (node.nodeNum != 0) {
            node = node.nodes[0];
        }
        if (node.dataNum == 0) {
            return null;
        }
        return convert(node.datas[0]);
    }
    
    public TreeNode search(T data) {
        TreeNode node = root;
        while (node != null) {
            int i = 0;
            for (; i < node.dataNum; i++) {
                T temp = convert(node.datas[i]);
                int result = data.compareTo(temp);
                if (result == 0) {
                    return node;
                }
                if (result < 0) {
                    break;
                }
            }
            int index = (i == 0) ? 0 : (i + 1);
            node = (index < node.nodeNum - 1) ? node.nodes[index] : null;
        }
        return null;
    }
    
    public boolean contain(T data) {
        return search(data) != null;
    }
    

    4. 插入

    234树的插入相对比较复杂,一般情况下:

    • 向 2-node 插入一个元素,会将它变成 3-node。


    • 向 3-node 插入一个元素,会将它变成 4-node。


    但是我们无法向 4-node中继续插入元素了,所以我们需要进行转化,通常我们会将 4-node中中间的元素,放到它的父节点中,并进行分裂。

    但是如果它的父节点仍然是一个 4-node的话,就无法进行了。所以我们需要确保当前节点的父节点永远都不会是一个 4-node。

    下图为234树构建的全过程:

    public void insert(T data) {
        if (data == null) {
            throw new NullPointerException();
        }
        root = insert(data, root);
    }
    
    private TreeNode insert(T data, TreeNode node) {
        if (node == null) {
            node = new TreeNode(data);
            return node;
        }
        int i = 0;
        for (; i < node.dataNum; i++) {
            T temp = convert(node.datas[i]);
            int result = data.compareTo(temp);
            if (result == 0) {
                throw new IllegalArgumentException("cant has the same data : " + temp);
            }
            if (result < 0) {
                break;
            }
        }
        if (node.nodeNum == 0) {
            node = subInsert(data, node, i);
        } else {
            TreeNode subNode = node.nodes[i];
            subNode = insert(data, subNode);
            node.nodes[i] = subNode;
        }
        return node;
    }
    
    private TreeNode subInsert(T data, TreeNode node, int index) {
    
        if (node.dataNum < MAX_SIZE - 1) {
            node.appendData(data, index);
            return node;
        }
    
        TreeNode parent = new TreeNode(node.getMidData());
    
        TreeNode left = new TreeNode(node.datas[0]);
        left.appendNode(node.nodes[0]);
        left.appendNode(node.nodes[1]);
    
        TreeNode right = new TreeNode(node.datas[node.dataNum - 1]);
        right.appendNode(node.nodes[2]);
        right.appendNode(node.nodes[3]);
        right = insert(data, right);
    
        parent.appendNode(left);
        parent.appendNode(right);
    
        return parent;
    }
    

    相关文章

      网友评论

        本文标题:数据结构 - 树 - 2-3-4树

        本文链接:https://www.haomeiwen.com/subject/afrmtftx.html