2-3-4树【数据结构与算法java】

2-3-4树

2-3-4树的介绍

本节将介绍2-3-4树的特征。在这之后会看到专题applet怎样模拟2-3-4树以及如何用Java语 言编写2-3-4树的程序。本章还会介绍2-3-4树和红-黑树的惊人的相似性。
图10.1展示了一棵小2-3-4树。每个菱形节点可以保存一个、两个或三个数据项。

图中上面的三个节点有子节点，底层的六个节点都是叶节点，没有子节点。2-3-4树中所有的 叶节点总是在同一层上。

名字的含义？
2-3-4树名字中的2、3和4的含义是指~个节点可能含有的子节点的个数。对非叶节点有三种 可能的情况：

• 有一个数据项的节点总是有两个子节点。
• 有两个数据项的节点总是有三个子节点。
• 有三个数据项的节点总是有四个子节点。

简而言之，非叶节点的子节点数总是比它含有的数据项多1。或者，用符号表示这个规则,设子节点链接的个数是L,数据项的个数是D,那么

L=D+1
1

这个重要的关系决定了 2-3-4树的结构。比较来说，叶节点没有子节点，然而它可能含有一个、 两个或三个数据项。空节点是不会存在的。

因为2-3-4树最多可以有四个子节点的节点，也可以称它为4叉树。

为什么不称2-3・4树为1-2-3-4树呢？它的节点不能像二叉树中那样只有一个子节点吗？因为二 叉树的每个节点最多有两个子节点，所以二叉树（第8章“二叉树”和第9章“红-黑树”讲过的） 可以称为二叉的多叉树。但是，二叉树和2-3-4树有…点不同（除了节点的最大子节点个数之外）。 二叉树中，节点最多有两个子节点的链接。它当然可以只有一个链接，指向它的左子节点或右了 节点。它的另一个链接可以是mill值。然而，在2-3-4树中，不允许只有一个链接。有一个数据项 的节点必须总是保持有两个链接，除非它是叶节点，在那种情况下没有链接。

如图10.2所示。有两个链接的节点称为2-节点，有三个链接的称为3-节点，有四个链接的称 为4-节点，但没有称为1-节点的节点。

2-3-4树的组织

为了方便起见，用从0到2的数字给数据项编号，用0到3给子节点链编号，如图10.2所示。 节点中的数据项按关键字值升序排列，习惯上从左到右升序（小数到大数）。

树结构中很重要一点就是它的链与自己数据项的关键字值之间的关系。二叉树中，所有关键字 值比某个节点值小的节点都在这个节点左子节点为根的子树上，所有关键字值比某个节点值大的节 点都在这个节点右子节点为根的子树上。2-3-4树中规则是一样的，还加上了以下几点：

• 根是childO的子树的所有子节点的关键字值小于key0。
• 根是childl的子树的所有子节点的关键字值大于key0并且小于key1。
• 根是child2的子树的所有子节点的关键字值大于key1并且小于key2。
• 根是child3的子树所有子节点的关键字值大于key2。

这种关系如图10.3所示。2-3-4树中一般不允许出现重复关键字值，所以不用考虑比较相同的 关键字值的情况。

回到图10.1中的树。所有的2-3-4树中，叶节点都在同一层（最底层）。上面层的节点一般都 不满；也就是说，它们可能只含有一个或两个数据项，而不是三个。

同样，注意树是平衡的。即使插入一列升序（或降序）排列的数据2-3-4树都能保持平衡。2-3-4 树的自我平衡能力取决于新节点的插入方式，后面将会看到。

搜索2-3-4树

查找特定关键字值的数据项和在二叉树中的搜索例程相类似。从根开始，除非査找的关键字值 就是根，否则选择关键字值所在的合适范围，转向那个方向，直到找到为止。

例如，在图10.1的树中查找关键字值为64的数据项，从根开始。在根节点査找没有找到。因为64比50大，所以转到childl=1,用60/70/80表示它。（记住childl是在右边，因为左边按数字标记 子节点和链接时是从0开始的。）在这个节点也找不到数据项，必须转向下一个子节点。这里，因 为64比60大且比70小，所以还是转到childl□这次就在62/64/66节点中找到了 64。

插入

新的数据项总是插在叶节点里，在树的最底层。如果插入到有子节点的节点里，子节点的编号 就要发生变化以此来保持树的结构，这保证了节点的子节点比数据项多1。

2-3-4树中插入节点有时比较简单，有时相当复杂。无论哪一种情况都是从查找适当的叶节点开始的。

查找时没有碰到满节点时，插入很简单。找到合适的叶节点后，只要把新数据项插入进去就可以了。图10.4显示了数据项18插入到2-3-4树中的情形。

插入可能会涉及到在一个节点中移动一个或者两个其他的数据项，这样在新数据项插入后关键值仍保持正确的顺序。在这个例子里23右移为18腾出位置。

节点分裂

如果往下寻找要插入位置的路途中，节点己经满了，插入就变得复杂了。发生这种情况时，节 点必须分裂（split）o正是这种分裂过程保证了树的平衡。这里讨论的2-3-4树的是一种称为自顶向 下的（top-down） 2-3-4树，因为是在向下找到插入点的路途中节点发生分裂。

把要分裂节点中的数据项设为A、B和C。下面是分裂时的情况。（假设正在分裂的节点不是根; 后面会讲解根的分裂方法。）

• 创建一个新的空节点。它是要分裂节点的兄弟，在要分裂节点的右边。
• 数据项C移到新节点中。
• 数据项B移到要分裂节点的父节点中。
• 数据项A保留在原来的位置上。
• 最右边的两个子节点从要分裂节点处断开，连到新节点上。

图10.5中显示的是一个节点分裂的例子。另一种描述节点分裂的方法是说4-节点变成两个2-节点。

注意节点分裂是把数据向上和向右移动。正是这样的重新排列才可以保持树的平衡。

插入只需要分裂一个节点，除非插入路径上存在不止一个满的节点。这种情况就需要多重分裂。

根的分裂

如果一开始查找插入点时就碰到满的根时，插入过程更复杂一点：

• 创建新的根。它是要分裂节点的父节点。
• 创建第二个新的节点。它是要分裂节点的兄弟节点。
• 数据项C移到新的兄弟节点中。
• 数据项B移到新的根节点中。
• 数据项A保留在原来的位置上°
• 要分裂节点最右边的两个子节点断开连接，连到新的兄弟节点中。

图10.6显示了根分裂的过程。过程中创建新的根，比旧的髙一层。因此，整个树的高度就增加 了 1。另一种描述根分裂的方法是说4-节点变成三个2-节点。

顺着分裂的节点，继续向下查找插入点。图10.6中，关键值为41的数据项插入到合适的叶节 点里。

在下行路途中分裂

注意，因为所有满的节点都是在下行路途中分裂的，分裂不可能向回波及到树上面的节点。任 何要分裂节点的父节点肯定不是满的，因此该节点不需要分裂就可以插入数据项B。当然，如果父 节点的子节点分裂时它已经有两个子节点了，它就变满了。但是，这只是意味着下次查找碰到它时 才需要分裂。

图10.7显示的是空树中的一系列插入过程。有四个节点分裂了，两个是根，两个是叶节点.

2-3-4树的Java代码

本节讲述实现2-3-4树的Java程序。本节最后会显示完整的tree234.java程序。这个程序相当 复杂，类之间也彼此关联，所以需要详细阅读整个代码清单来明白程序是如何运作的。

程序中有四个类：Dataltem、Node. Tree234和Tree234App。下面依次来讨论它们。

Dataltem 类

Dataltem类的对象表示存储在节点中的数据项。实际生活中每个对象可以表示一个完整的员工 档案或目录的内容，但这里只有一条数据，long类型，与每个Dataltem对象关联。

这个类对象仅有的方法是初始化方法和显示方法。显示时在数据值前加上一个斜杠：/27。 (Node类中的显示例程会调用这个方法来显示节点中的所有数据项。)

Node 类

Node类包括两个数组：childAnay和itemArray。第一个数组有四个数据单元，保存节点可能会有的所有子节点的引用。第二个数组有三个数据单元，保存节点包含的Dataltem类型的对象的引用。

注意itemArray中的数据项组成了有序数组。插入新数据项或删除原来的数据项时，它们还必 须继续保持有序的状态(见第2章“数组”中的讨论)。数据项需要移位腾出空间来按序插入新数 据项，或在删除某个数据项后前移以补上空着的数据单元。

这个类中还有表示节点中当前数据项个数的字段(numltems)和表示节点父节点的字段 (parent)。不一定必须设有这些字段，可以删掉它们来缩小节点，不过，留着它们可以使程序更清 楚，而且它们只是让节点增大了一点。

Node类提供了各种通用的方法来管理子节点和父节点的链接，以及检査节点是否为满和是否 为叶节点。其实主要的方法有findltem。、insertltem()和removeltem(),它们控制节点中的各个数据项。它们在节点中根据给定的关键字值查找数据项；在节点中插入新数据项，根据需要移动存在的 数据项；以及删掉数据项，再根据需要移动存在的数据项。不要把这些方法和后面Tree234类中的 find()和insert()方法混淆。

显示方法显示出了节点，用斜杠分割数据项，例如
Z27/56/89/, /14/66/,或/45/。

不要忘记Java中创建对象时，引用被自动初始化为null,数字初始化为0,所以Node类不需要构造方法。

Tree234 类

Tree234类的一个对象表示一棵完整的树。这个类只有一个字段：mot,类型是Node。所有操 作都从根开始，因此树的所有需要记录的字段就是根。

查找

根据给定关键字值査找数据项由find()方法执行。从根开始对每个节点调用节点的findltem()方法来看数据项是否在那里。如果是的话，它返回数据项在节点的数据项数组中的索引值。

如果find()方法在叶节点上并且没有找到数据项，查找就失败了，返回-1。如果在当前节点找不到数据项，并且当前节点不是叶节点，find()调用getNextChild()方法，找出下一步需要转向节点的那个子节点。

插入

除了找到满的节点就分裂节点之外，insert()方法开始的代码与find。类似。同样地，它假设没有失败；不断査找，一层一层深入地找下去，直到找到一个叶节点。这时把新的数据项插入到叶节 点中去。(叶节点中总会有空间；否则，叶节点就需要分裂。)

分裂

split()方法是这个程序中最复杂的方法。它会将要分裂的节点作为参数传入。首先，最右边的 两个数据项从节点中删掉并保存起来。然后断开最右边两个子节点的连接；它们的引用也保存起来。

建立一个新节点，叫newRight。它将置于被分裂节点的右边。如果要分裂的节点是根，还要再 创建一个新节点：新的根节点。

下一步，把要分裂节点连到它父节点的合适位置上去。父节点可能是已经存在的，或如果根分 裂时，父节点是新创建的根节点。设要分裂节点中的三个数据项是A、B和C。数据项B插入到它 的父节点中。如果有必要的话，父节点中已经存在的子节点先断开连接，再连接到右移一位的新的 位置上，为新的数据项和新的连接腾出位置。newRight节点连接到它的父节点上去。(参考图10.5 和 10.6)

现在关注newRight节点。数据项C插入到这个节点里，child2和child3——刚才从要分裂节点 处断开的两个子节点，连接到这个节点上。分裂就完成了，split()例程返回。

Tree234App 类

在Tree234App类中，main。方法把一些数据项插入到树中去。它还提供了基于字符的用户接口， 用户可以输入s来显示树，输入i来插入新的数据项，输入f来査找已经存在的数据项。下面是某个程序交互的例子：

输出并不是很直观，但已经显示岀了足够的信息可以画出树来。如上所示，首先是层数，根为 。层，后面是子节点的编号。显示算法是按照深度优先的顺序，所以先显示出根，然后是根的第一 个子节点，和以第一个子节点为根的子树，之后是第二个子节点和它的子树，依次类推。
上文输出的界面表示要插入两个数据项：20和10。第二个插入的数据项引起节点（根的childO） 分裂。图10.12展示了插入完成后的树，是最后输入’s’键的结果。

完整的tree234.java程序

清单10.1是完整的tree234.java程序，包括刚刚讨论过的所有的类。像大多数面向对象程序一 样，最容易的方法是先査看上层主要的类，然后再进一步关注面向细节的类。程序中这样的顺序是 Tree234App> Tree234> Node、Dataltemo

package tree234;

/**
 * @author CSDN@日星月云
 * @date 2022/11/1 23:18
 */
// tree234.java
// demonstrates 234 tree
//to run this program: C>java Tree234App

import java.io.*;

//〃//〃/〃///〃〃〃///〃///
class DataItem {

    public long dData;

    //
    public DataItem(long dd) { // constructor
        dData = dd;
    }


    public void displayItem() { // display item, format "/27"
        System.out.print("/" + dData);
    }

} // end class DataItem

//〃/〃〃〃//〃〃〃///〃
class Node {
    private static final int ORDER = 4;
    private int numItems;
    private Node parent;
    private Node childArray[] = new Node[ORDER];
    private DataItem itemArray[] = new DataItem[ORDER - 1];

    //
// connect child to this node
    public void connectChild(int childNum, Node child) {
        childArray[childNum] = child;
        if (child != null)
            child.parent = this;
    }

    //
// disconnect child from this node, return it
    public Node disconnectChild(int childNum) {
        Node tempNode = childArray[childNum];
        childArray[childNum] = null;
        return tempNode;
    }

    //

    public Node getChild(int childNum) {
        return childArray[childNum];
    }

    //
    public Node getParent() {
        return parent;
    }

    //

    public boolean isLeaf() {
        return (childArray[0] == null) ? true : false;
    }

    //
    public int getNumItems() {
        return numItems;
    }

    public DataItem getItem(int index) { // get DataItem at index
        return itemArray[index];
    }

    public boolean isFull() {
        return (numItems == ORDER - 1) ? true : false;
    }

    //

    public int findItem(long key) {// item (within node)
        for (int j = 0; j < ORDER - 1; j++) {// if found,
            // otherwise,
            if (itemArray[j] == null) //return -1
                break;
            else if (itemArray[j].dData == key)
                return j;
        }
        return -1;
    }// end findItem


    public int insertItem(DataItem newItem) {
        // assumes node is not full
        numItems++;// will add new item
        long newKey = newItem.dData;     //key of new item
        for (int j = ORDER - 2;j>=0; j--) {// start on right,

            //examine items
            if (itemArray[j] == null) // if item null,
                continue; // go left one cell
            else {// not null.
                // get its key
                long itsKey = itemArray[j].dData;
                if (newKey < itsKey) // if it 's bigger
                    itemArray[j + 1] = itemArray[j]; // shift it right
                else {
                    itemArray[j + 1] = newItem;    // insert new item
                    return j + 1; // return index to
                }

            }// end else (not null)


        } // end for // shifted all items
        itemArray[0] = newItem; // insert new item
        return 0;
    }// end insertItem()


    //
    public DataItem removeItem() {// remove largest item

        // assumes node not empty
        DataItem temp = itemArray[numItems - 1];// save item
        itemArray[numItems - 1] = null;  //disconnect it

        numItems--;    // one less item
        return temp;// return item
    }


    //
    public void displayNode() {    // format "24/56/74/"
        for (int j = 0; j < numItems; j++)
            itemArray[j].displayItem();//"/56"
        System.out.println("/");    // final "/"
    }
//
} // end class Node

// //
class Tree234 {
    private Node root = new Node();// make root node

    //
    public int find(long key) {
        Node curNode = root;
        int childNumber;
        while (true)
            if ((childNumber = curNode.findItem(key)) != -1)
                return childNumber;    // found it
            else if (curNode.isLeaf())
                return -1;    // can't find it
            else    // search deeper
                curNode = getNextChild(curNode, key);
    } // end while

    //insert a DataItem
    public void insert(long dValue) {
        Node curNode = root;
        DataItem tempItem = new DataItem(dValue);
        while (true) {
            if (curNode.isFull()) { // if node full,
                split(curNode);//spit it
                curNode = curNode.getParent();//back up
                //search once
                curNode = getNextChild(curNode, dValue);
            } // end if(node is full)

            else if (curNode.isLeaf()) // if node is leaf,
                break;//go insert
                // node is not full, not a leaf; so go to lower level
            else
                curNode = getNextChild(curNode,dValue);
        }//end while
        curNode.insertItem(tempItem);//insert new DataItem
    } // end insert()

    //

    public void split(Node thisNode) {//split the node

        // assumes node is full
        DataItem itemB, itemC;
        Node parent, child2, child3;
        int itemIndex;

        itemC = thisNode.removeItem();//remove items from
        itemB = thisNode.removeItem();//this node
        child2 = thisNode.disconnectChild(2);// remove children
        child3 = thisNode.disconnectChild(3); // from this node
        Node newRight = new Node();


        if (thisNode == root) {
            root = new Node();//make new root
            parent = root;//root is our parent
            root.connectChild(0, thisNode);
        } else // this node not the root
            parent = thisNode.getParent();//get parent
        //

        // deal with parent
        itemIndex = parent.insertItem(itemB); // item B to parent
        int n = parent.getNumItems();//total items?


        for (int j = n - 1; j > itemIndex; j--) {//move parent's connections
            Node temp = parent.disconnectChild(j); //one child
            parent.connectChild(j + 1, temp);    //to the right
        }

        // connect newRight to parent
        parent.connectChild(itemIndex + 1, newRight);
        // deal with newRight


        newRight.insertItem(itemC);//item C to newRight
        newRight.connectChild(0, child2); // connect to 0 and 1
        newRight.connectChild(1, child3); // on newRight
    } // end split()
//


    // gets appropriate child of node during search for value

    public Node getNextChild(Node theNode, long theValue) {
        int j;
        // assumes node is not empty, not full, not a leaf
        int numItems = theNode.getNumItems();
        for (j = 0; j < numItems; j++) {    // for each item in node
            // are we less?
            if (theValue < theNode.getItem(j).dData)
                return theNode.getChild(j);// return left child
        }// end for	// we're greater, so
        return theNode.getChild(j);//return right child
    }

    public void displayTree() {
        recDisplayTree(root, 0, 0);
    }

    private void recDisplayTree(Node thisNode, int level,
                                int childNumber) {
        System.out.print("level=" + level + " child=" + childNumber + " ");
        thisNode.displayNode();    // display this node

        // call ourselves for each child of this node
        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;
        }
    } // end recDisplayTree()
//
} // end class Tree234


class Tree234App {
    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.print("Enter first letter of ");
            System.out.print("show, insert, or find: ");
            char choice = getChar();
            switch (choice) {
                case 's':
                    theTree.displayTree();
                    break;
                case 'i':
                    System.out.print("Enter value to insert: ");
                    value = getInt();
                    theTree.insert(value);
                    break;
                case 'f':
                    System.out.print("Enter value to find:");
                    value = getInt();
                    int found = theTree.find(value);
                    if (found != -1)
                        System.out.println("Found " + value);
                    else
                        System.out.println("Could not find " + value);
                    break;
                default:
                    System.out.print("Invalid entry\n");
            }// end switch
        }// end while
    } // end main()

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

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

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


} // end class Tree234App

/**
 * Enter first letter of show, insert, or find: s
 * level=0 child=0 /50/
 * level=1 child=0 /30/40/
 * level=1 child=1 /60/70/
 *
 * Enter first letter of show,insert,or find:f
 * Enter value to find: 40
 * Found 40
 *
 * Enter first letter of show, insert, or find: i
 * Enter value to insert: 20
 *
 * Enter first letter of show, insert, or find: s
 * level=0 child=0 /50/
 * level=1 child=0 /20/30/40/
 * level=1 child=1 /60/70/
 *
 * Enter first letter of show, insert, or find: i
 * Enter value to insert: 10
 *
 * Enter first letter of show, insert, or find: s
 * Level=0 child=0 /30/50/
 * level=1 child=0 /10/20/
 * level=1 child=1 /40/
 * level=1 child=2 /60/70/
 *
 */

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356