Binary Trees,
Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
project report helper
Active In SP
**

Posts: 2,270
Joined: Sep 2010
#1
05-10-2010, 05:28 PM



.ppt   bst3.ppt (Size: 1.64 MB / Downloads: 127)
Binary Trees, an d Binary Search Trees and Binary Search Trees


Linear access time of linked lists is prohibitive
Does there exist any simple data structure for which the running time of most operations (search, insert, delete) is O(log N)?
Trees
Basic concepts
Tree traversal
Binary tree
Binary search tree and its operations
Reply
seminar surveyer
Active In SP
**

Posts: 3,541
Joined: Sep 2010
#2
20-01-2011, 12:42 PM




.ppt   Binary Search Trees.PPT (Size: 360 KB / Downloads: 39)

Binary Search Trees


Binary Search Trees
One of the tree applications in Chapter 10 is binary search trees.
In Chapter 10, binary search trees are used to implement bags and sets.
This presentation illustrates how another data type called a dictionary is implemented with binary search trees.
The Dictionary Data Type
A dictionary is a collection of items, similar to a bag.
But unlike a bag, each item has a string attached to it, called the item's key.
The Dictionary Data Type
A dictionary is a collection of items, similar to a bag.
But unlike a bag, each item has a string attached to it, called the item's key.
The Dictionary Data Type
A dictionary is a collection of items, similar to a bag.
But unlike a bag, each item has a string attached to it, called the item's key.
The Dictionary Data Type
The insertion procedure for a dictionary has two parameters.
The Dictionary Data Type
When you want to retrieve an item, you specify the key...
The Dictionary Data Type
The Dictionary Data Type
We'll look at how a binary tree can be used as the internal storage mechanism for the dictionary.
A Binary Search Tree of States
The data in the dictionary will be stored in a binary tree, with each node containing an item and a key.
A Binary Search Tree of States
Storage rules:
Every key to the left of a node is alphabetically before the key of the node.
A Binary Search Tree of States
Storage rules:
Every key to the left of a node is alphabetically before the key of the node.
A Binary Search Tree of States
Storage rules:
Every key to the left of a node is alphabetically before the key of the node.
Every key to the right of a node is alphabetically after the key of the node.
A Binary Search Tree of States
Storage rules:
Every key to the left of a node is alphabetically before the key of the node.
Every key to the right of a node is alphabetically after the key of the node.
Retrieving Data
Start at the root.
If the current node has the key, then stop and retrieve the data.
If the current node's key is too large, move left and repeat 1-3.
If the current node's key is too small, move right and repeat 1-3.
Retrieve ' New Hampshire'
Start at the root.
If the current node has the key, then stop and retrieve the data.
If the current node's key is too large, move left and repeat 1-3.
If the current node's key is too small, move right and repeat 1-3.
Retrieve 'New Hampshire'
Start at the root.
If the current node has the key, then stop and retrieve the data.
If the current node's key is too large, move left and repeat 1-3.
If the current node's key is too small, move right and repeat 1-3.
Retrieve 'New Hampshire'
Start at the root.
If the current node has the key, then stop and retrieve the data.
If the current node's key is too large, move left and repeat 1-3.
If the current node's key is too small, move right and repeat 1-3.
Retrieve 'New Hampshire'
Start at the root.
If the current node has the key, then stop and retrieve the data.
If the current node's key is too large, move left and repeat 1-3.
If the current node's key is too small, move right and repeat 1-3.
Adding a New Item with a Given Key
Pretend that you are trying to find the key, but stop when there is no node to move to.
Add the new node at the spot where you would have moved to if there had been a node.
Adding
Pretend that you are trying to find the key, but stop when there is no node to move to.
Add the new node at the spot where you would have moved to if there had been a node.
Adding
Pretend that you are trying to find the key, but stop when there is no node to move to.
Add the new node at the spot where you would have moved to if there had been a node.
Adding
Pretend that you are trying to find the key, but stop when there is no node to move to.
Add the new node at the spot where you would have moved to if there had been a node.
Adding
Pretend that you are trying to find the key, but stop when there is no node to move to.
Add the new node at the spot where you would have moved to if there had been a node.
Adding
Pretend that you are trying to find the key, but stop when there is no node to move to.
Add the new node at the spot where you would have moved to if there had been a node.
Adding
Pretend that you are trying to find the key, but stop when there is no node to move to.
Add the new node at the spot where you would have moved to if there had been a node.
Adding
Adding
Removing an Item with a Given Key
Find the item.
If necessary, swap the item with one that is easier to remove.
Remove the item.
Removing 'Florida'
Find the item.
Removing 'Florida'
Removing 'Florida'
Removing 'Florida'
If necessary, do some rearranging.
Removing 'Florida'
If necessary, do some rearranging.
Removing 'Florida'
If necessary, do some rearranging.
Removing 'Florida'
If necessary, do some rearranging.
Removing 'Florida'
If necessary, do some rearranging.
Removing 'Florida'
Removing 'Florida'
Removing an Item with a Given Key
Find the item.
If the item has a right child, rearrange the tree:
Find smallest item in the right subtree
Copy that smallest item onto the one that you want to remove
Remove the extra copy of the smallest item (making sure that you keep the tree connected)
else just remove the item.
Summary
Binary search trees are a good implementation of data types such as sets, bags, and dictionaries.
Searching for an item is generally quick since you move from the root to the item, without looking at many other items.
Adding and deleting items is also quick.



Reply
seminar ideas
Super Moderator
******

Posts: 10,003
Joined: Apr 2012
#3
13-04-2012, 03:08 PM

Binary Trees


.pdf   BinaryTrees.pdf (Size: 49.74 KB / Downloads: 13)



Stanford CS Education Library -- #110
This is article #110 in the Stanford CS Education Library. This and other free CS materials are available at the
library (cslibrary.stanford.edu/). That people seeking education should have the opportunity to find it.
This article may be used, reproduced, excerpted, or sold so long as this paragraph is clearly reproduced. Copyright
2000-2001, Nick Parlante, nick.parlante@cs.stanford.edu.


Introduction To Binary Trees
A binary tree is made of nodes, where each node contains a "left" pointer, a "right" pointer, and a data element.
The "root" pointer points to the topmost node in the tree. The left and right pointers recursively point to smaller
"subtrees" on either side. A null pointer represents a binary tree with no elements -- the empty tree. The formal
recursive definition is: a binary tree is either empty (represented by a null pointer), or is made of a single node,
where the left and right pointers (recursive definition ahead) each point to a binary tree.



Binary Search Tree Niche

Basically, binary search trees are fast at insert and lookup. The next section presents the code for these two
algorithms. On average, a binary search tree algorithm can locate a node in an N node tree in order lg(N) time (log
base 2). Therefore, binary search trees are good for "dictionary" problems where the code inserts and looks up
information indexed by some key. The lg(N) behavior is the average case -- it's possible for a particular tree to be
much slower depending on its shape.

Strategy

Some of the problems in this article use plain binary trees, and some use binary search trees. In any case, the
problems concentrate on the combination of pointers and recursion. (See the articles linked above for pointer articles
that do not emphasize recursion.)
For each problem, there are two things to understand...
The node/pointer structure that makes up the tree and the code that manipulates it
The algorithm, typically recursive, that iterates over the tree
When thinking about a binary tree problem, it's often a good idea to draw a few little trees to think about the
various cases.


Pointer Changing Code
There is a common problem with pointer intensive code: what if a function needs to change one of the pointer
parameters passed to it? For example, the insert() function below may want to change the root pointer. In C and
C++, one solution uses pointers-to-pointers (aka "reference parameters"). That's a fine technique, but here we will
use the simpler technique that a function that wishes to change a pointer passed to it will return the new value of
the pointer to the caller.


Binary Tree Problems
Here are 14 binary tree problems in increasing order of difficulty. Some of the problems operate on binary search
trees (aka "ordered binary trees") while others work on plain binary trees with no special ordering. The next
section, Section 3, shows the solution code in C/C++. Section 4 gives the background and solution code in Java. The
basic structure and recursion of the solution code is the same in both languages -- the differences are superficial.


Java Binary Trees and Solutions
In Java, the key points in the recursion are exactly the same as in C or C++. In fact, I created the Java solutions by
just copying the C solutions, and then making the syntactic changes. The recursion is the same, however the outer
structure is slightly different.
Reply
seminar tips
Super Moderator
******

Posts: 8,857
Joined: Oct 2012
#4
12-11-2012, 12:08 PM

to get information about the topic "binary search tree in vhdl" full report ppt and related topic refer the link bellow


topicideashow-to-a-binary-search-tree-implementation


topicideashow-to-binary-trees
Reply

Important Note..!

If you are not satisfied with above reply ,..Please

ASK HERE

So that we will collect data for you and will made reply to the request....OR try below "QUICK REPLY" box to add a reply to this page

Quick Reply
Message
Type your reply to this message here.


Image Verification
Please enter the text contained within the image into the text box below it. This process is used to prevent automated spam bots.
Image Verification
(case insensitive)

Possibly Related Threads...
Thread Author Replies Views Last Post
  SAVE TREES seminar tips 0 316 21-12-2012, 05:55 PM
Last Post: seminar tips