Wednesday 23, July 2014
Welcome Guest, Register | Login  
      Home    |    Tutorials    |    Free Ebooks    |    Free Scripts    |    Articles    |    Blog     |    About Us    |    Contact Us

Trees

Trees are the type of nonlinear data structure. A data structure accessed beginning at the root node. Each node is either a leaf or an internal node. An internal node has one or more child nodes and is called the parent of its child nodes. All children of the same node are siblings. Contrary to a physical tree, the root is usually depicted at the top of the structure, and the leaves are depicted at the bottom.


Height of Tree:
The maximum distance of any leaf from the root of a tree. If a tree has only one node (the root), the height is zero. The height of a tree is also known as the order.
The degree of a node is the number of subtrees associated with that node. For example, the degree of tree T is n.
A node of degree zero has no subtrees. Such a node is called a leaf.

Binary Tree:
A binary tree T is defined as a finite set of elements, called nodes, such that
  1. T is empty (called the null tree or empty tree)
  2. T contains a distinguished node R called the root of T, and the remaining nodes of T form an ordered pair of disjoint binary tree T1 and T2.
If T does contain a root R, than the two trees, T1 and T2 are called respectively the left and right subtrees or R. If T1 is non empty, than its root is called the left successor of R, similarly, if T2 is nonempty, than its root is called the right successor of R.

Binary Search Tree:
Binary Search tree is a binary tree in which each internal node T stores an element such that the element stored in the left subtree of T are less than or equal to T and elements stored in the right subtree of T are greater than or equal to T. T is called binary-search-tree property.

Traversing Binary Trees:
There are three standard ways of traversing a binary tree T with root R. These three algorithm are called preorder, inorder and postorder.

Preorder:
  1. Process the root R.
  2. Traverse the left subtree of R in preorder.
  3. Traverse the right subtree of R in preorder.

Inorder:
  1. Traverse the left subtree of R in inorder.
  2. Process the root R.
  3. Traverse the right subtree of R in inorder.

Postorder:
  1. Traverse the left subtree of R in postorder.
  2. Traverse the right subtree of R in postorder.
  3. Process the root R.

Breath-first Traversal:

The breadth-first traversal of a tree visits the nodes in the order of their depth in the tree. Breadth-first traversal first visits all the nodes at depth zero (i.e., the root), then all the nodes at depth one, and so on. At each depth the nodes are visited from left to right.

Depth-first Traversal:
Depth-first traversal is an algorithm for traversing or searching a tree, tree structure, or graph. One starts at the root (selecting some node as the root in the graph case) and explores as far as possible along each branch before backtracking.


Height Balanced Tree:
A height-balanced tree which is also a binary search tree. It supports membership, insert, and delete operations in time logarithmic in the number of nodes in the tree.
self-balancing binary search tree or height-balanced binary search tree is a binary search tree that attempts to keep its height, or the number of levels of nodes beneath the root, as small as possible at all times, automatically.

AVL Trees:
An AVL tree is a self-balancing binary search tree, and it is the first such data structure to be invented. In an AVL tree, the heights of the two child subtrees of any node differ by at most one; therefore, it is also said to be height-balanced. Lookup, insertion, and deletion all take O(log n) time in both the average and worst cases, where n is the number of nodes in the tree prior to the operation. Insertions and deletions may require the tree to be rebalanced by one or more tree rotations.


 

 
     
   
Data Structure Theory Tutorial
 
  Data Structure
Data Structure
  Abstract Data Types
Abstract Data Types
  Stacks
Stacks
  Queues
Queues
  Linked Lists
Linked Lists
  Linear Search
Linear Search
  Sorting
Sorting
  Hashing
Hashing
  Trees
Trees
  Graphs
Graphs
 
 
 
Web Designing Tutorials
  HTML Tutorial
HTML Tutorial
  DHTML Tutorial
DHTML  Tutorial
  CSS Tutorial
CSS Tutorial
  XHTML Tutorial
XHTML Tutorial
 
Programming Languages Tutorials
  C Language Tutorial
C Language Tutorial
  C++ Tutorial
C++ Tutorial
  Java Language Tutorial
Java Language Tutorial
  Data Structure Theory Tutorial
Data Structure Theory Tutorial
 
Server Side Scripting Tutorials
  PHP Tutorial
PHP Tutorial
  SQL Tutorial
SQL Tutorial
  ASP Tutorial
ASP Tutorial
 
Client Side Scripting Tutorials
  JavaScript Tutorial
JavaScript Tutorial
  VBScript Tutorial
VBScript Tutorial
 
 
 
POPULAR E-BOOKS
 
Download Introduction to Object-Oriented Programming Using C++  Ebook Introduction to Object-Oriented Programming Using C++
   
Download Creating Applications with Mozilla  Ebook Creating Applications with Mozilla
   
Download How to Succeed in Online Marketing and Sales Because of Proven Techniques Ebook How to Succeed in Online Marketing and Sales Because of Proven Techniques
   
Download Affiliate Money Machine Ebook Affiliate Money Machine
   
Download Secrets of Affiliate Marketing Ebook Secrets of Affiliate Marketing
   
     
Studiesinn.com 2014 All Rights Reserved.
 
Website Designed & Developed by TechXprtz