Ask a question from expert

Ask now

CS4343 Programming Assignment

19 Pages2084 Words97 Views
   

Programming Assignment (CS4343)

   

Added on  2021-09-17

CS4343 Programming Assignment

   

Programming Assignment (CS4343)

   Added on 2021-09-17

BookmarkShareRelated Documents
Introduction
The Red-Black Tree is a self-balancing Binary Search Tree (BST). The structure is governed
by a number of rules which include;
1. Nodes are either red or black
2. The root node is always black
3. Every final/last leaf is black
4. A red node must have both of its children red
5. Simple paths for any node must have equal number of black descendant nodes
How to Compile and Run the Program
The solution developed for this question is presented in a single java file named;
RedBlackTree.java
to compile the program;
java RedBlackTree.java
javac RedBlackTree
The program requests for the filename from which it will read the commands, as shown below.
CS4343 Programming Assignment_1
CS4343 Programming Assignment_2
SOURCE CODE
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.Scanner;
public class RedBlackTree {
//The colors will be represented by 0 and 1
private final int RED = 0;
private final int BLACK = 1;
private final RBNode nil = new RBNode(-1);
private RBNode root = nil;
/*
We use a private inner class
to define the NODE
*/
private class RBNode {
int data = -1;
int color = BLACK;
RBNode left = nil;
RBNode right = nil;
RBNode parent = nil;
CS4343 Programming Assignment_3
public RBNode(int key) {
this.data = key;
}
/**
* Constructor
*/
public RBNode(int key, RBNode parent, RBNode left, RBNode right, char color) {
this.data = key;
this.parent = parent;
this.left = left;
this.right = right;
this.color = color;
}
void setColor(char color) {
this.color = color;
}
}
/**
* This function prints out the Tree
* inorder
* @param node
*/
void printInorder(RBNode node) {
CS4343 Programming Assignment_4

End of preview

Want to access all the pages? Upload your documents or become a member.

Related Documents
Implementation of Binary Search Tree in Java
|13
|706
|64

Desklib - Online Library for Study Material
|8
|1880
|61

Solving a Color Maze using DFS
|7
|1042
|184