2-3 Tree Insertion Algorithm in Java

A 2-3 Tree provides the near logarithmic search efficiency of a complete Binary Search Tree (BST) by guaranteeing that the tree will always remain balanced.  Unlike a BST, a 2-3 Tree remains balanced even if clients insert data in pre-sorted order.

Before reading the code for the 2-3 Insertion Algorithm, review some key concepts about 2-3 Trees to better understand the algorithm:

  1. Data is always inserted at a leaf (node with no children)
  2. Every internal node (a node with children) must be either a ‘2-node’ or a ‘3-node’ by design. This means an internal node can have either 1 data item and 2 children, or 2 data items and 3 children
  3. Inserting into a full node (node with 2 data items) splits the node and pushes the middle data item up, splitting and pushing recursively until a ‘2-node’ is encountered
  4. The tree grows in height when a recursive call splits the root

Each 2-3 Tree node contains two Data object references and three child references. A 2-node uses only the first Data object reference and the left and right child references, with the second Data reference and middle child reference set to null.  Also, every node has a parent node reference that must be updated after a split.

This algorithm is written for a generic “Data” class with a string ID field and assumes a compare function exists that returns the difference between two string values using Java’s compareTo() function. If the two Data objects match, the compare function returns a value of ‘zero’. This algorithm passes data items of equal value to the right. Since the compare function subtracts the value of the second (argument object) from the first (this object), a negative return value indicates that the first value is smaller than the second.

To insert into a 2-3 Tree, a recursive function must first locate the correct position at a leaf to insert the new item. Don’t forget to use a wrapper function to check if root is null!

/**Recursive function to insert a new Data item at the correct leaf*/
protected void insert(Data item) {
    int diff = dataOne.compare(item);

    //Node is a leaf
    if ((left == null) && (mid == null) && (right == null)) {
        if (this.dataTwo == null) {   //Leaf has only one data item
            if (diff <= 0) {    //New item is larger than dataOne
                this.dataTwo = item;
            } else {            //New item is smaller than dataOne
                this.dataTwo = dataOne;
                this.dataOne = item;
            }
        } else {                //Leaf has two items and must be split
            splitLeaf(item);   

            if (parent != null) {   
                this.parent.pushUp(this);
            }
        }

        return;
    }

    //Not a leaf, continue traversal
    if (diff > 0) {       //New item is smaller than dataOne and the smallest
        left.insert(item);
    }                     //New item is larger or equal to dataOne and this node
    else if (dataTwo == null) {      //is a 2-node
        right.insert(item);
    } else {              //This node is a 3-node
        diff = dataTwo.compare(item);

        if (diff > 0) {   //New item is smaller than dataTwo
            mid.insert(item);
        } else {          //New item is larger than dataTwo and the largest
            right.insert(item);
        }
    }
}

This insert function compares the new data item (as an argument) and recursively traverses the tree until a leaf is encountered.  If the leaf has one item, the new item is added in the appropriate position, with the smallest data item always in dataOne.

The real action happens when the function attempts to insert at a leaf containing two data items already. The algorithm must split the node by passing the new data item as an argument to the splitLeaf() function.

/**Function splits a full leaf creating a 2-node */
private void splitLeaf(Data item) {
    int diff = dataOne.compare(item);

    if (diff > 0) {        //New item is smaller than dataOne and smallest
        left = new Node23(item, this);
        right = new Node23(dataTwo, this);
        dataTwo = null;
    } else {       //New item is larger than dataOne
        diff = dataTwo.compare(item);

        if (diff > 0) {    //New item is smaller than dataTwo
            left = new Node23(dataOne, this);
            right = new Node23(dataTwo, this);
            dataTwo = null;
            dataOne = item;
        }  else {              //New item is larger than dataTwo and largest
            left = new Node23(dataOne, this);
            right = new Node23(item, this);
            dataOne = dataTwo;
            dataTwo = null;
        }
    }
}

A simple constructor builds new leaf nodes:

/** Constructor builds a leaf node with one data item */
Node23(Data toAdd, Node23 prev) {
    parent = prev;
    dataOne = toAdd;
}

During a leaf split, the node must manage three data items, but only has memory for two.  A comparison determines the middle data item to inherit the node. The function then creates two new nodes by passing the appropriate data items (smaller to the left, larger to the right) and a ‘this’ reference via a simple constructor.  The function transforms the node into a 2-node, with two children and the middle item as the data field.

Next, program control returns to the insert function.  If the node has a parent, the insert function calls the parent’s recursive pushUp function, passing itself as an argument via the ‘this’ reference.  pushUp then attempts to absorb its child 2-node.

/**Function to push up the middle item after splitting a 3-node or leaf
 * @param item is a '2-node'
 * @post If this node is a 2-node, the Node23 object is inserted and connected 
 *       creating a 3-node
 *       If this node is a 3-node, it must be split and pushed up again */
protected void pushUp(Node23 item) {
    if (this.dataTwo == null) {   //This node is a 2-node
        int diff = dataOne.compare(item.dataOne);

        if (diff > 0) { //Node item.dataOne to add is smaller than this.dataOne
            this.dataTwo = dataOne;
            this.dataOne = item.dataOne;
            left = item.left;
            left.parent = this;
            mid = item.right;
            mid.parent = this;
        } else { //Node item.dataOne to add is larger or equal than this.dataOne
            this.dataTwo = item.dataOne;
            mid = item.left;
            mid.parent = this;
            right = item.right;
            right.parent = this;
        }
    } else {              //This node is a 3-node and must be split
        splitThreeNode(item);

        if (parent != null) {
            parent.pushUp(this);
        }
    }
}

If the parent is a 2-node, the function inserts the new data item and reconnects the children appropriately.  However, if the parent is a 3-node, it too must be split and pushed up.

/**Recursive function to split an internal 3-node creating a 2-node to be pushed
 * up to the node's parent
 * @param item is a 2-node to be inserted, reconnected and pushed up the tree
 * @post  Node is a 2-node with all data connected to left and right children */
private void splitThreeNode(Node23 item) {
    int diff = dataOne.compare(item.dataOne);
    Node23 temp = null;

    if (diff > 0) {     //Item toAdd is smaller than dataOne
        left = item;
        left.parent = this;
        temp = new Node23(dataTwo, this);
        dataTwo = null;
        temp.left = mid;
        temp.left.parent = temp;
        temp.right = right;
        temp.right.parent = temp;
        right = temp;
        mid = null;

    } else {
        diff = dataTwo.compare(item.dataOne);

        if (diff > 0) {     //Item to add is between dataOne and dataTwo
            temp = new Node23(dataOne, this);
            temp.left = left;
            temp.left.parent = temp;
            temp.right = item.left;
            temp.right.parent = temp;
            left = temp;
            temp = new Node23(dataTwo, this);
            temp.left = item.right;
            temp.left.parent = temp;
            temp.right = right;
            temp.right.parent = temp;
            right = temp;
            dataOne = item.dataOne;
            dataTwo = null;
            mid = null;
        } else {          //Item to add is larger than dataTwo
            right = item;
            right.parent = this;
            temp = new Node23(dataOne, this);
            temp.left = left;
            temp.left.parent = temp;
            temp.right = mid;
            temp.right.parent = temp;
            left = temp;
            dataOne = dataTwo;
            dataTwo = null;
            mid = null;
        }
    }
}

The splitThreeNode function creates a 2-node, being careful not to lose or misplace the four children. Program control returns to the pushUp function, which executes recursively until it encounters either a 2-node or the root.

The graphics below provide a visual demonstration of this algorithm:

23insert001
1) insert() traverses to the appropriate leaf to insert ’21’ and calls splitLeaf() because the leaf is full.
23insert002
2) splitLeaf() rearranges the data items by value, creates a left and right node, and calls pushUp() to push the middle data item into the parent. Since the parent node is full, splitThreeNode() is called.
23insert003
3) splitThreeNode() rearranges the data items by value, reconnects the children, and calls pushUp() to push the middle data item into the parent.
23insert004
4) The parent has room for the data item, and the insertion operation is complete.

Algorithm Review

How can this algorithm be improved upon?

By changing the compare() function to compare an int rather than a string, the cost of comparisons can be reduced.

What are the disadvantages of a 2-3 Tree design?

Maintaining balance of a search tree improves performance during search operations.  However, maintaining this balance comes with an occasionally large performance cost during a recursive split. If the recursive calls split all the way to the root (increasing the tree height) on a large data set, clients will notice a delay after certain insertion operations.  Therefore, if a client performs frequent insertion operations, a Red-black Tree would provide better performance.

Advertisements

How to Write a C++ Program With Linux

If you run Linux on your computer, you’re only a few steps away from being able to write, compile, and run C++ programs at the terminal using vim, g++ and gdb. Your system probably already has the vi text editor. However, vim offers many improvements over vi, and is worth installing. Install g++ to compile your code and gdb to debug your code. Type the lines sudo apt-get install vim and sudo apt-get install g++ at the terminal to download and install the necessary programs.

Use the mkdir command to make a new folder for our program, then navigate to that folder with the cd command. Type vi main.cpp to create a new file and start coding. The classic “Hello World” program below demonstrates basic output:

#include 

using namespace std;

int main() {
	cout << "\nThis is a test of the National Broadcasting System." << endl;

	return 0;
}

Because vi is a text-only editor, learning to edit with it can be discouraging for unfamiliar users. Nonetheless, knowing how to use a basic text editor like vi or emacs is an essential survival skill in the computer world. New users should take the time to familiarize themselves with this resource on vi editor commands.

If you aren’t familiar with vi, use the following commands to complete this basic program: Type i to enter insert-mode, and then type the program code listed above. Once you’re done typing the code, press Esc to exit insert-mode. Next press : and type wq to save and quit. Now we’re ready to compile our program by typing the line g++ main.cpp at the terminal.

No news is good news. If the compiler didn’t display any errors, it’s time to run our program by typing ./a.out.

dcampbe@pdx:~/prog1$ g++ main.cpp
dcampbe@pdx:~/prog1$ ./a.out
This is a test of the National Broadcasting System.
dcampbe@pdx:~/prog1$

If your results looked something like the box above, congratulations! You’re officially a computer programmer. The same tools and technique can be used to write programs in the C programming language by replacing the g++ compiler with gcc.

Four Things to Do After Installing Kubuntu 15.10 on an SSD

The release of Kubuntu 15.10 brings with it the clean aesthetics of KDE Plasma 5.4:

Run the update manager after booting into Kubuntu for the first time. Naturally there will be a considerable list of updates to download and install. After restarting, use the native Muon Discover Software Center package manager to search and install programs. Many users may prefer Synaptic Package Manager (which can be installed through Muon).

1) Install and Configure Internet Browsers

Kubuntu comes with Firefox. I prefer to add Chromium and use Firefox as an emergency backup. Perform the following essential tweaks to improve user experience in both browsers:

  • Install AdBlock to block almost all ads making the browsing experience faster and more secure (under Settings/Extensions in Chromium, and ‘Add-ons’ in Firefox)
  • Set DuckDuckGo as the default search engine and use the !bang system to speed up searches and save bandwidth
  • Users with SSDs may want to disable Firefox ‘safebrowsing’ by un-checking the two ‘Block reported…’ options under Preferences/Security (instructions in the link in Step 4)

firefox safebrowsing

Firefox comes with Flash already installed. With HTML5 support available on many websites, I’m not recommending users install Flash on Chromium.

2) Install Wine

You’ll probably wan’t to run Windows software or drivers at some point. PlayOnLinux is an easy front-end for installing Windows applications. NDISwrapper runs Windows drivers for network devices that don’t have Linux drivers.

Wine installs the ‘C Drive’ folder under a hidden directory. Link this folder under ‘Places’ in the Dolphin File Manager for easy access. Simply click and drag. Right-click to change the label.

wine drive c

3) VLC media player

VLC plays everything. Indispensable.

VLC.png

4) Solid State Drive Optimization

To improve SSD performance edit /etc/fstab and add the parameters ‘discard’ and ‘noatime’ to the SSD device (install a text editor like gedit if you haven’t already). The first parameter turns on TRIM, to help maintain SSD performance over time, and the second reduces unnecessary writes to the SSD.

Edit /etc/fstab to mount /tmp and /varlog as tmpfs on a ramdisk, further reducing unnecessary writes.

Prevent use of the swap partition by adding ‘vm.swappiness=0’ to /etc/sysctl.conf, further reducing unnecessary writes.

To reduce writes to the SSD even further, install and configure Profile-sync-daemon, which can place browser cache files on a ramdisk.

Detailed instructions on these tweaks and a few others are contained at Ubuntu – Tweaks for SSD drive.

Four Useful Websites

1) DuckDuckGo

duckduckgo.com (ddg.gg)

A time-saving, search engine alternative to Google, DuckDuckGo offers the privacy, speed, and simplicity that other, bigger search engines no longer provide. Unlike Google, Bing, or Yahoo, DuckDuckGo doesn’t filter search results based on customer behavior, or track customers for that matter.

However, my favorite feature of this search engine is the ‘!bang’ system, which allows simple command-based searches to be executed from the search bar in your browser (once you set your default search engine to DuckDuckGo). For example, searching for “!d crepuscular” sends the browser directly to The Free Dictionary search result page for “crepuscular”.

ddgbang

The traditional way of getting there would involve going to thefreedictionary.com, loading the main page, then typing in your search query, and finally loading the results page. Using DuckDuckGo’s !bang system saves time and bandwidth. There are over 7000 !bang commands built into DuckDuckGo. Here are some of the most useful and time-saving commands:

!a Amazon
!b Bing
!d TheFreeDictionary.com
!e Ebay
!g Google (TSL encrypted)
!gf Google Finance
!i Google Images
!m Google Maps
!mc Metacritic
!n Google News
!rt Rottentomatoes
!t Thesuaraus.com
!wa WolframAlpha
!y Yahoo
!yt Youtube
!zillow Zillow

Full list of !bang commands here.


I
find DuckDuckGo to be one of the more underrated and useful web developments of the last few years. However, the search engine may be gaining recognition. According to DuckDuckGo’s official traffic report, the search engine has grown to over 5 million search queries daily.

2) Glassdoor

Although the cumbersome layout—including pop-ups pestering the user to login or register before viewing some content—diminishes the user experience of this website, it is nonetheless notable for providing indispensable information about the job market. The website compiles current and former employee reviews of experiences working at many major companies and government agencies. Current employees can compare their work experiences, salaries, and even opinions of their CEO to those of coworkers in different positions, while prospective employees can read company reviews and interview experiences to better prepare and determine if a company is the right fit for them.

glassdoor

3) Where’s George?

This entertaining gem of a website harkens back to 1998. During the late 90s and early 00s dollar bills with “wheresgeorge.com” stamped on them became a ubiquitous fixture in many cash registers in the US. The simple concept of Where’s George? allows users to track the circulation of US banknotes by stamping them. When another Where’s George user comes across a banknote that has been stamped, she or he may log the time and place of the transaction on the website.

wheresgeorge

Although its popularity has declined in recent years, the website is still fully operational and can be a surprising source of occasional entertainment. For example, I once logged a bill that I received as change at my university, only to find that it had originally been deposited by a patron at a nearby strip club. It can take a long time before banknotes get logged by another user, however it’s rewarding to see how far your bills have traveled and where they were spent.

4) Astronomy Picture of the Day (APOD)

Everyday for the past 20 years APOD has posted an image relating to astronomy. Each post includes a brief commentary on the image written by an astronomer. This website can provide an interesting and often beautiful 2-minute diversion from anyone’s daily routine.

apod