Applications of binary trees, Data Structure & Algorithms

Assignment Help:

In computer programming, Trees are utilized enormously. These can be utilized for developing database search times (binary search trees, AVL trees, 2-3 trees, red-black trees), Game programming (decision trees, minimax trees,  pathfinding trees),

3D graphics programming (octrees, quadtrees,), Arithmetic Scripting languages (arithmetic precedence trees), Data compression (Huffman trees), and file systems (sparse indexed trees, B- trees, tries ). Figure illustrated a tic-tac-toe game tree illustrating various stages of game.

218_APPLICATIONS of  binary TREES.png

Figure: A tic-tac-toe game tree showing various stages of game

In the entire above scenario except the first one, ultimately the player (playing with X) looses in subsequent moves.

The General tree (also known as Linked Trees) is a generic tree which has one root node, and each node in the tree can have limitless number of child nodes. One popular employ of this kind of tree is in Family Tree programs. In game programming, several games use these types of trees for decision-making processes as illustrated above for tic-tac-toe. A computer program might have to make a decision depend on an event that happened.

But it is just a simple tree for demonstration. A more complicated AI decision tree would absolutely have a lot more options. The interesting thing regarding using a tree for decision-making is that the options are cut down for each level of the tree as we go down, very much simplifying the subsequent moves & raising the speed at which the AI program makes a decision.

The big problem along with tree based level progressions, but, is that sometimes the tree can get too large & complex as the number of moves (level in a tree) enhance. Suppose a game offering just two choices for every move to the next level at the end of every level in a ten level game. This would need a tree of 1023 nodes to be created.

Binary trees are utilized for searching keys. Such trees are called Binary Search trees

A Binary Search Tree (BST) is a binary tree having the given properties:

1.  Always the key of a node is greater than the keys of the nodes in its left sub-tree

2.  Always the key of a node is smaller than the keys of the nodes in its right sub-tree

It might be seen that while nodes of a BST are traversed by inorder traversal, the keys appear in sorted order:

inorder(root)

{ inorder(root.left) print(root.key) inorder(root.right)

}

Binary Trees are also utilized for evaluating expressions.

A binary tree can be utilized to represent & evaluate arithmetic expressions.

1. If a node is a leaf, then the element in it indicates the value.

2. If this is not leaf, then appraise the children & join them in according to the operation indicated by the element.


Related Discussions:- Applications of binary trees

Convert graph into tree, How can we convert a graph into a tree ? Do we hav...

How can we convert a graph into a tree ? Do we have any standardized algorithm for doing this?

Difference between array and abstract data types, Difference between array ...

Difference between array and abstract data types Arrays aren't abstract data types since their arrangement in the physical memory of a computer is an essential feature of their

Explain backtracking, Explain Backtracking The  principal idea is to co...

Explain Backtracking The  principal idea is to construct solutions single component  at a time  and evaluate such  partially constructed candidates as follows. If a partiall

What are stored and derived attributes, What are stored and derived attribu...

What are stored and derived attributes?  Stored attributes: The attributes kept in a data base are called stored attributes.  Derived attributes: The attributes that are

Enumerate the types in ruby, Enumerate the Types in Ruby Ruby is a pure...

Enumerate the Types in Ruby Ruby is a pure object-oriented language, meaning that all types in Ruby are classes, and each value in a Ruby program is an instance of a class. Thi

Operations on b-trees, Operations on B-Trees Given are various operatio...

Operations on B-Trees Given are various operations which can be performed on B-Trees: Search Create Insert B-Tree does effort to minimize disk access and t

Applications of shortest path algorithms, The minimum cost spanning tree ha...

The minimum cost spanning tree has broad applications in distinct fields. It represents several complicated real world problems such as: 1. Minimum distance for travelling all o

Algorithm for binary search, Q. Write down the algorithm for binary search....

Q. Write down the algorithm for binary search. Which are the conditions under which sequential search of a list is preferred over the binary search?

Implementation of stack using linked lists, In the last subsection, we have...

In the last subsection, we have implemented a stack by using an array. While a stack is implemented by using arrays, it suffers from the basic restriction of an array - i.e., its s

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd