前段时间学习算法，讲到如何implement 2-3 search tree.
把自己写的algorithm那上来大家分享下。
// REMARKS: Implement a 2-3 search tree
//
//-----------------------------------------
import java.util.*;
import java.io.*;
public class TwoThreeTree
{
public static void main(String [] args)
{
// the text file name
String fileName = "TwoThreeInsert.txt";
String fileName2 = "TwoThreeSearch.txt";
String command = "insert"; //the insert command
String command2 = " search"; // the search command
Tree newTree = new Tree(); //creat a empty 2-3 tree
//call method to insert the data to the 2-3 tree
insertAndSearch(newTree,fileName,command);
//call method to search the data in 2-3 tree
insertAndSearch(newTree,fileName2,command2);
}
//------------------------------------------------------
// insertAndSearch(Tree newTreee, String fileName, String command)
//
// PURPOSE: open a file and follow the command to do the insert operation
// or do the search operation. eg:if the command equals to
// "insert",this method do the insertion.
// INPUT PARAMETERS:
// Tree newTree: the 2-3 tree
// String fileName: the string, which is the name of the file
// String command: string, which is the order.
// OUTPUT PARMETERS:
// VOID
//------------------------------------------------------
public static void insertAndSearch(Tree tree,String Name,String order)
{
int data;
String word;
FileReader theFile;
BufferedReader in;
try
{
theFile = new FileReader(Name);
in = new BufferedReader( theFile );
//read the first line
word = in.readLine();
while ( word != null )
{
data = Integer.parseInt(word);
// if the command is insert.do the insertion
if(order.equals("insert"))
tree.insert(data);// call the insert method
// do the searching
else
{
System.out.println("Searching number "+data);
tree.searchData(data); // call the search method
}
//read the next line
word = in.readLine();
}
in.close();
}
catch( IOException ex )
{
System.out.println( "I/O error: " + ex.getMessage() );
}
}
}
public class Tree
{
// to indicate the large data in the node is empty
static final int MIN = Integer.MIN_VALUE;
//------------------------------------------------------
// Node Class
//
// PURPOSE: inner class, hold data and links
// to the next node in the list.
//------------------------------------------------------
public class Node
{
// private data field
private int smallData;
private int largeData;
private Node leftChild;
private Node middleChild;
private Node rightChild;
//------------------------------------------------------
// Node()
//
// PURPOSE: 2-3 search Tree Node constructor
// INPUT PARAMETERS:
// int small: integer, the smaller data in the node
// int large: integer, the larger data in the node
// Node left: Node type, the left child of the current node
// Node middle: Node type, the middle child of the current node
// Node right: Node type, the right child of the current node
//------------------------------------------------------
public Node(int small,int large,Node left,Node middle,Node right)
{
smallData = small;
//if the large data in the node is empty,pass in the "MIN" to
//indicate it is empty, only for this program.
largeData = large;
leftChild = left;
middleChild = middle;
rightChild = right;
}
}
private Node root; // the root of the tree
//------------------------------------------------------
// Tree()
//
// PURPOSE: Tree constructor, creat a empty 2-3 tree
//------------------------------------------------------
public Tree()
{
root = null; //initial the tree root
}
//------------------------------------------------------
// searchData(int newData)
//
// PURPOSE: to search the data in the 2-3 tree, to check whether
// the given data is in the tree, either it is found or not,
// print out the message to tell the result
// INPUT PARAMETERS:
// int newData : integer, the given data which need be checked
// OUTPUT PARAMETERS:
// VOID
//------------------------------------------------------
public void searchData(int newData)
{
Node temp = root;
//show whether found or not,initial to false means not found
boolean result = false;
//goes to while loop if the root is not null
while(temp != null && !result)
{
//if the large data in the node is empty,just
//compare with the small data
//if the data equals to MIN. means data value is empty
if(temp.largeData == MIN)
{ //if data is bigger than the small data in the node
// goes to the right child of the current node
if(newData > temp.smallData)
{
temp = temp.rightChild;
}
//if data is smaller than the small data in the node
//goes to the left child of the current node
else if(newData < temp.smallData)
{
temp = temp.leftChild;
}
//if the data eaquals the data in the node
//set the result to true and exit the loop
else if(newData == temp.smallData)
{
result = true;
}
}
//if the large data in the node is not empty
else if(temp.largeData != MIN)
{
//if the data value is between the 2 data in the node
//goes to the middle child of the current node
if(newData > temp.smallData && newData < temp.largeData)
{
temp = temp.middleChild;
}
//if data is bigger or equals to the the large data
else if(newData >= temp.largeData)
{
//if it equals, set result to ture
if(newData == temp.largeData)
result = true;
//goes to the right child of the current node
else
temp = temp.rightChild;
}
//if data is smaller or equals to the small data
else if( newData <= temp.smallData)
{
//if it equals, set result to true
if(newData == temp.smallData)
result = true;
//goes to the left child of the current node
else
temp = temp.leftChild;
}
}
}
//if result is true, print the data was found
if(result)
System.out.println("the number "+newData+" is found!\n");
//print out the data was not found
else
System.out.println("the number "+newData+" is NOT found!\n");
}
//------------------------------------------------------
// findNodeInsert(int newData)
//
// PURPOSE: to find the leaf node to hold the data
// INPUT PARAMETERS:
// int newData : integer, the given data
// OUTPUT PARAMETERS:
// temp1: Node type,the correct node need to hold the data
//------------------------------------------------------
public Node findNodeInsert(int newData)
{
Node current = root;// initial the current node point to the node
Node previous = null;
//when the current points to the leaf node's children(null), stop!
//the previoud points to the leaf node, return the previous
while(current != null )
{
previous = current;// set the previous point to current
//if the large data in the current node is empty
if(current.largeData == MIN)
{
//if data is bigger than the small data in the node
//current goes to the right child of the current node
if(newData > current.smallData)
{
current = current.rightChild;
}
//goes to the left child of the current node
else if(newData < current.smallData)
{
current = current.leftChild;
}
}
//the large data in the current node is not empty
else if(current.largeData != MIN)
{
//if the data is between the 2 data in the node
//goes to middle child
if(newData>current.smallData && newData current.largeData)
{
current = current.rightChild;
}
//the data is smaller than the small data in the node
//goes to the left child of the node
else if( newData < current.smallData)
{
current = current.leftChild;
}
}
}
return previous;
}
//------------------------------------------------------
// insert(int newData)
//
// PURPOSE: to insert the given data to the 2-3 tree
// INPUT PARAMETERS:
// int newData: integer, the given data
// OUTPUT PARAMETERS:
// VOID
//------------------------------------------------------
public void insert(int newData)
{
Node temp;
int tempData;
//if the root is null, set the data in the root
if(root == null)
{
Node newNode = new Node(newData,MIN,null,null,null);
root = newNode;
}
//it is not empty tree
else
{
//call the mehod to find the leaf node to insert the data
temp = findNodeInsert(newData);
//if the leaf Node's large data is empty
if(temp.largeData == MIN)
{
//do the comparision with newData and small data in
//the node, put the larger one at he large data position
//of the node
if(newData < temp.smallData)
{
temp.largeData = temp.smallData;
temp.smallData = newData;
}
else if( newData > temp.smallData)
{
temp.largeData = newData;
}
}
//if the larger data in the node is not empty
//do the comparsion,put the middle value to the newData
//and call the split method to split the node and keep
//the tree in shape.
else if(temp.largeData != MIN)
{
if(newData > temp.largeData)
{
tempData = temp.largeData;
temp.largeData = newData;
newData = tempData;
}
else if(newData < temp.smallData)
{
tempData = temp.smallData;
temp.smallData = newData;
newData = tempData;
}
split(temp,newData);//call the split method
}
}
}
//------------------------------------------------------
// split(Node n, int newData)
//
// PURPOSE: split the nodes and store the data in the node
// keep the tree in shape
// INPUT PARAMETERS:
// Node n: Node type ,current node need be split at the beginning
// int newData: integer, current integer need be stored
// OUTPUT PARAMETERS:
// VOID
//------------------------------------------------------
public void split(Node n, int newData)
{
Node parent;
int tempData;
Node temp;
Node n1,n2,newNode;
//if the node n is root of the tree, just split this node
//in 2 parts, and creat a new node, store the newdata.Then
//link the new split 2 nodes.Set the root to the new node
if(n == root)
{
//set n1 with root's smallData
n1 = new Node(n.smallData,MIN,null,null,null);
//set n2 with root's largeData
n2 = new Node(n.largeData,MIN,null,null,null);
//creat newNode to hold the newData, and link with n1 and n2
newNode = new Node(newData,MIN,n1,null,n2);
//set root point to newNode
root = newNode;
}
//if the n is not the root of the tree
else
{
//split the leaf node in two parts, n1 store the smaller data
//in the lead node, n2 store the large data of the leaf node
n1 = new Node(n.smallData,MIN,null,null,null);
n2 = new Node(n.largeData,MIN,null,null,null);
//call the findParent method to find the leaf node's parent
parent = findParent(n,newData);
//if leaf node's parent is not null or the parent's large data
//is not empty.Goes into the while loop
while(parent != null && parent.largeData != MIN)
{
//if the newData is smaller than the parent's small data
//which means the newDate comes from the parent's
//left child
if(newData < parent.smallData)
{
//do the comparisonm,always set the middle value to the
//newData
tempData = parent.smallData;
parent.smallData = newData;
newData = tempData;
//split the parent in 2 nodes n1,n2. However,at
//this time the previous n1 and n2 are not destroyed,
//So we can store the parent's small data to the
//new n1 and new n1 links the previous n1
//and n2. Then creat new n2 stores the parent's large
//data,and links the parent's middle child and
//right Child
n1 = new Node(parent.smallData,MIN,n1,null,n2);
n2 = new Node(parent.largeData,MIN,
parent.middleChild,null,parent.rightChild);
//keep find the parent of current parent
parent = findParent(parent,newData);
}
//if the newData is between the parent's small and large
//data which means the newDate comes from the parent's
//middle child
else if(newData < parent.largeData)
{
//same idea as before.
//this time creat new n1 with parent's smallData
//link with parent's left child and previous n1.
//creats new n2 with parent's largeData and links
//with the previous n2 and parent's right child
n1 = new Node(parent.smallData,MIN,
parent.leftChild,null,n1);
n2 = new Node(parent.largeData,MIN,
n2,null,parent.rightChild);
//keep find the parent's parent
parent = findParent(parent,newData);
}
//if the newData is larger than the parent's large
//data which means the newDate comes from the parent's
//right child
else if(newData > parent.largeData)
{
//same idea as before, always set he newData the middle
//value
tempData = parent.largeData;
parent.largeData = newData;
newData = tempData;
//this time we need to pay attention in this situation.
//before we link n2 with previous n1 and n2, the
//previous n1 already been destroyed, so we need make a
//pointer hold the previous n1.
temp = n1;// pointer links to the previous n1
//creat new n1 with parent's smallData and links with
//parent's leftChild and parent's middle child; creats
//new n2 with parent's largeData,links with temp
//,which is the previous n1, and previous n2
n1 = new Node(parent.smallData,MIN,
parent.leftChild,null,parent.middleChild);
n2 = new Node(parent.largeData,MIN,temp,null,n2);
//keep find the parent's parent
parent = findParent(parent,newData);
}
}
//if parent is not null and parent's large data
//is empty
if( parent != null && parent.largeData == MIN)
{
//do the comparison with newData and smallData
//in the parent,if newData smaller than the small data
//of the parent.means newData comes from the parent's
//left child
if(newData < parent.smallData)
{
//always set the parent's large data to the
//larger value,small data to the small value
parent.largeData = parent.smallData;
parent.smallData = newData;
//parent's left child point to n1
parent.leftChild = n1;
//parent's middle child point to n2
parent.middleChild = n2;
}
//newData comes from the parent's right child
else
{
parent.largeData = newData;
//parent's middle child point to n1
parent.middleChild = n1;
//parent's right child point to n1
parent.rightChild = n2;
}
}
//if parent is null,creat a new node and store the newData
//and link with n1 and n2, set root point to new node
else if(parent == null)
{
newNode = new Node(newData,MIN,n1,null,n2);
root = newNode;
}
}
}
//------------------------------------------------------
// findParent
//
// PURPOSE: find the give node's parent.
// INPUT PARAMETERS:
// Node n: the given node
// int newData : integer, the data wish to store in the given node n
// OUTPUT PARAMETERS:
// Node previous: Node type, return the given node's previous node
// if it is exist, otherwise return null
//------------------------------------------------------
public Node findParent(Node n,int newData)
{
Node current = root;
Node previous = null;
//if the current node not null and current is not the node we
// want to find, goes into the loop,if current equals to the n
// we return the previous, which is the previous node of the
// current also is the parent of the node n.
// if return null, which means the node we want to search for
// parent is root of the tree
while(current != null && current != n)
{
previous = current;// set the previous to the current node
//if data small than the small data in the node
//goes to the left child of the node
if(newData < current.smallData)
{
current = current.leftChild;
}
//if the newData smaller than the large data in the node
//goes to the middle child of the node
else if(newData < current.largeData)
{
current = current.middleChild;
}
//goes to the right child of the node
else if(newData > current.largeData)
{
current = current.rightChild;
}
}
return previous;
}
}
测试文档
TwoThreeInsert.txt
2924
3546
1270
889
2536
4091
89
1040
1418
1034
628
901
4402
1229
4429
4440
1255
4990
3948
4734
1435
4410
1506
2836
4941
200
3477
2839
4807
4940
1120
4195
2821
519
597
3905
2582
3986
1608
706
928
2150
1565
3921
231
3138
1736
222
4833
679
4113
1470
73
3024
3898
832
1390
3677
1142
147
2943
4511
2383
83
4893
3726
3844
66
4325
3973
494
1819
4568
3551
2245
1673
3297
1323
1331
2622
1771
3411
1525
4321
2844
899
338
982
3098
2708
4041
33
425
2512
4035
2861
1502
3208
3690
3455
194
1665
4509
1680
3918
4853
3977
3623
2000
1789
301
1212
2680
2220
4010
4289
4193
3759
3885
3148
855
1273
4275
4815
369
4931
1363
40
1539
1019
1236
3583
953
526
2862
2402
69
3213
4391
3955
4604
1411
853
2548
4059
3436
1824
2008
27
1047
4863
486
4287
2252
444
4537
1814
1450
4204
2075
460
4196
604
1624
2392
2396
250
4733
2577
3859
2025
132
2753
458
3076
3344
2595
1192
2523
4207
2769
2048
4843
4024
3494
1653
4712
1890
2710
703
4589
2080
2637
2556
3724
379
4054
1909
4335
739
1714
3752
4023
2091
536
662
4577
2059
1693
2394
1708
4049
1332
2817
1041
3450
3585
2228
2482
651
1386
2522
316
645
3218
2450
4194
3055
3842
1135
287
4462
1854
1044
2568
4079
3618
846
3795
1716
3247
4393
2128
2901
1158
3426
1531
1102
3816
2636
2963
2399
1992
1287
2938
1745
1437
2274
1825
635
1719
553
3880
1428
1893
1946
647
755
1209
3027
4779
1089
1035
1352
3106
2587
879
3392
2601
4748
2016
1109
4373
2741
2376
2097
482
2503
1863
2443
136
TwoThreeSearch.txt
647
1451
147
3218
3859
2566
1863
3027
2568
256
132
1824
548
1673
4410
1653
3247
77
3436
2523
