Implement a city database using a Binary Search Tree (BST) to store the database

Question

Implement a city database using a Binary Search Tree (BST) to store the database records. Each database record contains the name of the city (a string of arbitrary length) and the coordinates of the city expressed as integer x- and y-coordinates. The BST should be organized by city name. Your database should allow records to be inserted, deleted by name or coordinate, and searched by name or coordinate. Another operation that should be supported is to print all records within a given distance of a specified point. [15] Write a C++ code to implement the city database. [5] Collect running-time statistics for each operation. [3] Which operations can be implemented reasonably efficiently (i.e., in O (log n) time in the average case) using a BST? [2] Can the database system be made more efficient by using one or more additional BSTs to organize the records by location? (Answering by just saying YES is not sufficient. Explain how.)

Explanation / Answer

using namespace std; // to save us having to type std::

const int MAX_CHAR = 1024;
int v1,v2;
char cname[100];

int main ( )
{

SQLCHAR SQLStmt[MAX_CHAR];
char strSQL[MAX_CHAR];
char chrTemp;

SQLVARCHAR CName[50];
SQLVARCHAR cvalue1[50];
SQLVARCHAR cvalue2[30];
  

// Get a handle to the database

SQLHENV EnvironmentHandle;
RETCODE retcode = SQLAllocHandle( SQL_HANDLE_ENV, SQL_NULL_HANDLE, &EnvironmentHandle );

// Set the SQL environment flags

retcode = SQLSetEnvAttr( EnvironmentHandle, SQL_ATTR_ODBC_VERSION, (SQLPOINTER) SQL_OV_ODBC3, SQL_IS_INTEGER );

// create handle to the SQL database

SQLHDBC ConnHandle;
retcode = SQLAllocHandle( SQL_HANDLE_DBC, EnvironmentHandle, &ConnHandle );

// Open the database using a System DSN

retcode = SQLDriverConnect(ConnHandle,
NULL,
(SQLCHAR*)"DSN=PRG411;UID=myUser;PWD=myPass;",
SQL_NTS,
NULL,
SQL_NTS,
NULL,
SQL_DRIVER_NOPROMPT);
if (!retcode)
{
cout << "SQLConnect() Failed";
}
else
{
// create a SQL Statement variable

SQLHSTMT StatementHandle;
retcode = SQLAllocHandle(SQL_HANDLE_STMT, ConnHandle, &StatementHandle);

// Part 1: Create the DataTable table (Database)

do
{
cout << "Create the new table? ";
cin >> chrTemp;
} while (cin.fail());

if (chrTemp == 'y' || chrTemp == 'Y')
{
strcpy((char *) SQLStmt, "CREATE TABLE [dbo].[DataTable]([pkEmployeeID] [int] IDENTITY(1,1) NOT NULL,[CName] [varchar](50) NOT NULL,[value1] [varchar](50) NOT NULL,[value2] [varchar](30) NOT NULL,[City] [varchar](30) NOT NULL,[State] [varchar](3) NOT NULL, [Salary] [decimal] NOT NULL,[Gender] [varchar](1) NOT NULL, [Age] [int] NOT NULL, CONSTRAINT [PK_Employee] PRIMARY KEY CLUSTERED ([pkEmployeeID] ASC)WITH (PAD_INDEX = OFF, STATISTICS_NORECOMPUTE = OFF, IGNORE_DUP_KEY = OFF, ALLOW_ROW_LOCKS = ON, ALLOW_PAGE_LOCKS = ON) ");
retcode = SQLExecDirect(StatementHandle, SQLStmt, SQL_NTS);
}

// Part 2: Hardcode records into the table

do
{
cout << "Add records to the table? ";
cin >> chrTemp;
} while (cin.fail());

if (chrTemp == 'y' || chrTemp == 'Y')

{

cout<<"Enter the city Name:";
cin>>cname;
cout<<"Enter the cordinate values:";
cin>>v1>>v2;
strcpy((char *) SQLStmt, "INSERT INTO DataTable([CityName], [cvalue1], [Cvalue2]) values(cname,v1,v2))");
retcode = SQLExecDirect(StatementHandle, SQLStmt, SQL_NTS);

  
}

// Part 3 & 4: Searchs based on criteria

do
{
cout << "1. Display all records in the database" << endl;
cout << "2. Insert Record into DataBase" << endl;
cout << "3. Dlete Record form database" << endl;
cout << "4. Exit" << endl << endl;

do
{
cout << "Please enter a selection: ";
cin >> chrTemp;
} while (cin.fail());

if (chrTemp == '1')
{
strcpy((char *) SQLStmt, "SELECT [CName], [cvale1], [cvalue2] FROM DataTable");
}
else if (chrTemp == '2')
{

cout<<"Enter the city Name:
cin>>cname;
cout<<"Enter the cordinate values:";
cin>>v1>>v2;
strcpy((char *) SQLStmt, "Insert [CName], [Cvalue1], [Cvalue2]] into DataTable values(cname,v1,v2)");
}
else if (chrTemp == '3')
{
strcpy((char *) SQLStmt, "delete FROM DataTable WHEREcname=[cname]");
strcpy((char *) SQLStmt, "delete FROM DataTable WHEREcname=[cvale1]");
strcpy((char *) SQLStmt, "delete FROM DataTable WHEREcname=[cvalue2]");
}

if (chrTemp == '1' || chrTemp == '2' || chrTemp == '3')
{
retcode = SQLExecDirect(StatementHandle, SQLStmt, SQL_NTS);

//SQLGetDiagRec(SQL_HANDLE_STMT, StatementHandle, RecNumber, SQLState, NativeErrorPtr, (SQLCHAR*) MessageText, (SQLINTEGER) BufferLength, (SQLSMALLINT*) &TextLengthPtr);

SQLBindCol(StatementHandle, 1, SQL_C_CHAR, &rtnFirstName, sizeof(CName), NULL );
  

for(;;)
{
retcode = SQLFetch(StatementHandle);
if (retcode == SQL_NO_DATA_FOUND) break;

cout << CName << " " << value1 << " " << value2 << endl;
}

SQLFreeStmt(StatementHandle, SQL_CLOSE);

}
} while (chrTemp != '4');

SQLFreeStmt(StatementHandle, SQL_CLOSE );
SQLFreeHandle(SQL_HANDLE_STMT, StatementHandle);

SQLDisconnect(ConnHandle);

SQLFreeHandle(SQL_HANDLE_DBC, ConnHandle);
SQLFreeHandle(SQL_HANDLE_ENV, EnvironmentHandle);

printf( "Done. " );
}

return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.