Med Java

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
====== Concurrent Binary Tree using Java Threads ======

Implementing a thread-safe binary tree in Java where each node has its own lock can be an efficient solution for concurrent insertions. 

This approach allows multiple threads to work on different parts of the tree simultaneously, reducing contention compared to a global lock for the entire tree.

<code java ConcurrentBinaryTree.java>
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;

public class ConcurrentBinaryTree {
    private Node root;

    static class Node {
        int value;
        Node left;
        Node right;
        final Lock lock;

        Node(int value) {
            this.value = value;
            this.left = null;
            this.right = null;
            this.lock = new ReentrantLock();
        }

        void insert(int value) {
            lock.lock();
            try {
                if (value < this.value) {
                    if (this.left == null) {
                        this.left = new Node(value);
                    } else {
                        this.left.insert(value);
                    }
                } else {
                    if (this.right == null) {
                        this.right = new Node(value);
                    } else {
                        this.right.insert(value);
                    }
                }
            } finally {
                lock.unlock();
            }
        }

        void inOrderTraversal() {
            if (this.left != null) {
                this.left.inOrderTraversal();
            }
            System.out.print(this.value + " ");
            if (this.right != null) {
                this.right.inOrderTraversal();
            }
        }
    }

    public void insert(int value) {
        if (root == null) {
            synchronized (this) {
                if (root == null) {
                    root = new Node(value);
                    return;
                }
            }
        }
        root.insert(value);
    }

    public void inOrderTraversal() {
        if (root != null) {
            root.inOrderTraversal();
        }
    }

    // Usage Example
    public static void main(String[] args) throws InterruptedException {
        ConcurrentBinaryTree tree = new ConcurrentBinaryTree();

        Thread[] threads = new Thread[7];
        int[] values = {5, 3, 7, 2, 4, 6, 8};
        for (int i = 0; i < threads.length; i++) {
            int val = values[i];
            threads[i] = new Thread(() -> tree.insert(val));
            threads[i].start();
        }

        for (Thread thread : threads) {
            thread.join();
        }

        System.out.println("In-order traversal of the binary tree:");
        tree.inOrderTraversal();
    }
}
</code>

The **ConcurrentBinaryTree** class, along with its inner **Node** class, is designed to allow concurrent insertions into a binary tree. Each node has its lock to ensure thread-safe modifications. The **inOrderTraversal** method is added to traverse the tree in order, which is a common way to visualize the content of a binary tree.

In the **Main** class, multiple threads (**t1 to t7**) are created, each inserting a unique value into the binary tree. The **insert** method in the **ConcurrentBinaryTree** class is thread-safe, allowing these concurrent insertions without data corruption or race conditions.
**
Thread Creation and Starting**: The **main** method creates and starts seven threads, each calling the insert method on the binary tree with different values.

**Concurrent Insertions**: These threads run concurrently, and due to the thread-safe design of the ConcurrentBinaryTree class, they can safely modify the tree without interfering with each other.

**Thread Joining**: The **join** method is called on each thread to ensure that the main thread waits for all of them to finish executing before proceeding.

**Tree Traversal**: After all insertions are complete, the **inOrderTraversal** method is called to print the elements of the tree in order. This should display the tree's elements in ascending order, demonstrating that the concurrent insertions were successful.

This implementation and usage example demonstrate a practical approach to managing concurrent access to a complex data structure like a binary tree in Java. By ensuring each node's thread-safe operations, the tree can be modified concurrently by multiple threads without data inconsistencies or race conditions.

===== Example Input =====

Suppose we have seven threads, each inserting a unique value into the binary tree. The values to be inserted by these threads are as follows:

Thread 1 inserts 5 \\ 
Thread 2 inserts 3 \\ 
Thread 3 inserts 7 \\ 
Thread 4 inserts 2 \\ 
Thread 5 inserts 4 \\ 
Thread 6 inserts 6 \\ 
Thread 7 inserts 8 \\ 

===== Expected Output =====

The expected output will be the in-order traversal of the binary tree after all threads have completed their insertions. In-order traversal of a binary tree prints the node values in ascending order.

For the given input, the output should be: 2 3 4 5 6 7 8

This output represents the binary tree's elements sorted in ascending order, indicating that the concurrent insertions were successful and the tree structure was maintained correctly.