import java.util.
ArrayList;
import java.util.List;
public class TwoThreeTree {
// Node class representing a 2-node or 3-node
class Node {
List<Integer> keys = new ArrayList<>();
List<Node> children = new ArrayList<>();
Node(int key) {
keys.add(key);
}
Node(int key1, int key2) {
keys.add(key1);
keys.add(key2);
}
}
private Node root;
// Constructor to initialize the 2-3 tree
public TwoThreeTree() {
root = null;
}
// Insert method to insert a key into the tree
public void insert(int key) {
if (root == null) {
root = new Node(key);
} else {
root = insert(root, key);
}
}
// Recursive insert helper method
private Node insert(Node node, int key) {
// If the node is a leaf, we insert the key
if (node.children.isEmpty()) {
node.keys.add(key);
node.keys.sort(Integer::compareTo); // Sort the keys
if (node.keys.size() == 3) {
return split(node); // Split if the node overflows
}
return node;
}
// If the node is not a leaf, recurse into the appropriate child
if (key < node.keys.get(0)) {
node.children.set(0, insert(node.children.get(0), key));
} else if (node.keys.size() == 1 || key < node.keys.get(1)) {
node.children.set(1, insert(node.children.get(1), key));
} else {
node.children.set(2, insert(node.children.get(2), key));
}
// If a child splits, split the current node
if (node.keys.size() == 3) {
return split(node);
}
return node;
}
// Split a 3-node into two 2-nodes and push the middle key up
private Node split(Node node) {
Node newNode = new Node(node.keys.get(1)); // The middle key
Node parent = new Node(node.keys.get(0)); // The left key becomes the
parent key
if (node.children.size() > 0) {
// Split the children
parent.children.add(node.children.get(0));
parent.children.add(node.children.get(1));
newNode.children.add(node.children.get(2));
newNode.children.add(node.children.get(3));
}
parent.keys.add(node.keys.get(0)); // Move the left key up to parent
parent.children.add(newNode); // Add newNode as a child of parent
return parent;
}
// Search for a key in the 2-3 tree
public boolean search(int key) {
return search(root, key);
}
// Recursive search method
private boolean search(Node node, int key) {
if (node == null) return false;
// If the node is a leaf, search directly
if (node.children.isEmpty()) {
return node.keys.contains(key);
}
// Otherwise, determine which child to search
if (key < node.keys.get(0)) {
return search(node.children.get(0), key);
} else if (node.keys.size() == 1 || key < node.keys.get(1)) {
return search(node.children.get(1), key);
} else {
return search(node.children.get(2), key);
}
}
// Print the tree (for debugging purposes)
public void print() {
print(root, "", true);
}
// Print the tree in a formatted way
private void print(Node node, String indent, boolean last) {
if (node != null) {
System.out.println(indent + "+- " + node.keys);
indent += last ? " " : "| ";
if (!node.children.isEmpty()) {
for (int i = 0; i < node.children.size(); i++) {
print(node.children.get(i), indent, i == node.children.size() -
1);
}
}
}
}
public static void main(String[] args) {
TwoThreeTree tree = new TwoThreeTree();
tree.insert(10);
tree.insert(20);
tree.insert(30);
tree.insert(5);
tree.insert(15);
tree.insert(25);
System.out.println("Tree structure after insertions:");
tree.print();
System.out.println("Search for 15: " + tree.search(15)); // Should return
true
System.out.println("Search for 40: " + tree.search(40)); // Should return
false
}
}
