Share
Explore BrainMass

Trees

There is a joke in computer science that "everything is a tree" due to their widespread use and applications. Trees are abstract data types/structures with a hierarchical build made up of a central root node (thought some types of tree allow this space to be empty) and many levels of children nodes under it. These nodes all link up to form a tree like the one below:

Trees can be, and often are, implemented recursively as a collection of nodes that have both a value or condition attribute and one storing a reference for their parent and/or children nodes. The root is the only node that has no parents; all others must have a single parent node in standard trees. A node with no children is called a leaf. The height  of a tree is the longest possible branch (path) from the root to one of these leaves, counted by the the number of nodes it passes through to get there. The industry standard is to say the root has height 0 but some notate it as height 1. Sometimes it is useful to look at trees as a whole, but often more so at subsections or the individual nodes. Common operations on trees are:

  • adding a node
  • searching the tree for a value
  • removing a node with a specific value

There are many types of trees too! Common types include:

  • Binary search trees (BSTs) - wherein values are sorted as they are added. You begin at the root and go left if the value is smaller than the root's value and right if it is bigger, repeating those comparisons until you reach a place where the node you're adding can be a leaf. The above tree is an example of this type.
  • AVL trees - a BST which is balanced, i.e. arranged so that the heights of each branch are within 1 node of each other. The above tree restructured as an AVL tree would look as follows:

  • Red-Black trees - Similarly to AVL trees, these trees must be balanced, but with branch heights 2 nodes of each other. Each node is also assigned a colour attribute, either red or black, and the black height is the number of black nodes in the longest branch from root to leaf. The root of a Red-Black tree is always black.

Newick Format Tree

Draw the graphical representation of the Newick format tree written below. Label each leaf with the appropriate sequence identifier, and label each branch with its appropriate length (both internal and external branches): Tree Data: ((SeqA:0.36,(SeqB:0.08, SeqD:0.08):0.31):0.03,SeqC:0.47,SeqE:0.39);.

Software Development Process.

Your work as a management information consultant has led you to a long-term project working on a custom decision support system software application. In 600-700 words complete the following and 3 references original only please Use the internet and credible sources to research the following approaches to the software deve

Implementing Operations on Binary Trees

Consider the following definition of a Binary Tree structure: typedef struct BTnode *node; struct BTnode { int key; node left; node right; }; 1. Write a function in C programming language that can find and return the height of a Binary Tree. 2. Write a function in C programming language that can find and return the c

Graphs and B-Tree

1.Show a path through the graph in Figure 1 starting at node A (see attachment). a. Using breadth-first traversal. b. Using depth-first traversal. 2. Perform the listed actions on the B-tree shown in Figure 2. Please depict the B-tree both when the value has been added/removed and after any excessively small/large nod

Object Identifier Question

Suppose you worked for a US-based company that wanted to develop its own MIB for managing a product line. Where in the object identifier tree would it be registered? (Hint: You have to do some digging through or other documents to answer this question.)

Java: Data Structures

Write, compile, and test a class that prints William on the screen. Save the class at Name.java Write compile, and test a class that prints William Nichols, 777 Mockingbird Lane, Detroit MI 48222 on three separate lines on the screen. Save as Address.java Write compile and test a class that displays the following pattern o

Build and show a binary tree based on the following names

The Binary Tree is one of the best ways to organize data when you need fast access. For this assignment, we will organize a list of names and perform various operations on those names. Build and show a binary tree based on the following names inserted into the binary tree in order listed: John, Eddie, Kim, Derrick, Ethan, Lonny,

Simple questions inf Class tree diagram

Classes A, B, C and H are related through inheritance and have the fields shown in the class tree diagram below. Class G is not related to any of the other classes Please see attachment file for more details

Prim algorithm

Please see the attached file. For the graph in 16.28(a), replicate the trace of Prim's algorithm to create a minimum spanning tree. For each step, create the list of minInfo elements in the priority queue and indicate which vertices and edges are in the current spanning tree, along with the accumulated total weight. Figure

Heaps, Binary Files and Bit Sets

A complete binary tree B, containing 50 nodes, is stored in a vector. (a). What is the level of the tree? (b). How many nodes are leaf nodes? Nonleaf nodes? (c). What is the index of the parent of B[35]? (d). What are the indices of the children of node B[20]? (e). What is the index of the first node with no children

Heaps, Binary Files and Bit Sets

Draw the complete tree corresponding to each of the following vectors: (a). int a[8] = (15, 9, 3, 6, 2, 1, 4, 7) int aSize = sizeof(a)/sizeof(int); vector<int> v(a, a + aSize); (b). string b = "array-based tree"; Vector<char> w(b.c_str(), b.c_str()+b.length());

Calculating the depth of a binary tree

10.30. Use the integers from one to nine to build a nine-node binary search tree with no duplicate data values (a). Give the possible root node values if the depth of the tree is 4. (b). Answer part (a) for depths of 5, 6, 7, and 8.

Binary tree: pre-order, post-order and in-order scan

(a). Draw the binary tree that the following allocations create. tnode< int > *root, *a, *c,*d, *e; e = new tnode< int > (50); d = new tnode< int > (20, NULL, e); c = new tnode< int > (30); b = new tnode< int > (45, c, NULL); a = new tnode< int > (15, b, d); r

Active Directory Riordan Manufacturing

Using Riordan Manufacturing as your model, create an Active Directory design for the organization. This should include your reasoning for core choices like number of forests and domains, DNS server placement, and placement of key roles in the AD design. You can use Visio® to assist in the design, and then prepare a 2-3 page pro

Relational database

Describe how the following information about airlines, flights (for a particular day), and passengers would be represented in a relational database: Airlines: Clear Sky, Long Hop, and Tree Top Flights for Clear Sky: CS205, CS37, CS 102 Flights for Long Hop: LH67, LH89 Flights for Tree Top: TT331, TT809 Smith has reservation

Excel #3

Using the documents given to you by the class president, you will be entering more data into the Excel workbook you created in Phase 1. You will also insert a new sheet into that workbook that will contain the cost data. Open the Excel workbook you created in Phase 1, the list of everyone who has responded to their invitatio

Excel Data Processing

Someone please help! The class president has given me a MS Word document that contains a list of everyone who has been invited to the high school reunion. I will enter this data into a pre-made Excel workbook. This Excel workbook does not contain all the information, so I will enter and format a substantial amount of the data

Create a unix shell script that does the following

Create a script that checks the day of the week, and takes one of two actions (step 2 or 3) depending on the day. If the day is Monday through Friday, print (send to stdout) the name of the day. Then, find each file named TTDL (Things-To-Do List) in the tree rooted at the current directory (pwd on down). Using a separate outp

Spreadsheet Applications

Help with the following tasks: I need help with this workbook i am doing for a spreadsheet application: 1.Open the guest.xls workbook that I created and uploaded: Review the data on the responded.doc document. 2. Enter the Attend, Adult, and Child data into your existing workbook. 3. Create headings on your Guest Lis

Web Site Structure Paper

Resource: Cascading Style Sheets at the following Web site: http://www.w3.org/Style/CSS/learning Explain which structure you prefer and why. Locate two Web sites that utilize this structure, and list their URLs. What advantages do Cascading Style Sheets (CSS) have when creating Web pages?

Types of Join Operations

What are the different types of joins, and how are they used? Show examples to support your reasoning.

Maximum records a B-tree can store

Please answer the following questions as detailed as possible: 1. For a B-tree of order 4 consisting of 3 levels, what is the maximum amount of records which may be stored? 2. For a B+-tree of order 3 consisting of 3 levels for the index part, what is the maximum amount of records which may be stored assuming that a data

BNF grammar and parse tree

1. Write a BNF grammar that describes the structure of a nonterminal called <number>. Assume that <number> contains an optional + sign followed by exactly 2 decimal digits, the first of which cannot be a 0. Thus 23, +91, and +40 are legal, but 9, +01, and 123 are not. Using this grammar, show a parse tree for the value +90.