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

Explain decision tree, Decision Tree A decision tree is a diagram that ...

Decision Tree A decision tree is a diagram that shows conditions and actions sequentially and therefore shows which condition is to be considered first, second and so on. It is

Sparse matrix, what are the disadvantages of sparse matrix?

what are the disadvantages of sparse matrix?

Define the external path length, Define the External Path Length The Ex...

Define the External Path Length The External Path Length E of an extended binary tree is explained as the sum of the lengths of the paths - taken over all external nodes- from

Kruskals algorithm, Krushkal's algorithm uses the concept of forest of tree...

Krushkal's algorithm uses the concept of forest of trees. At first the forest contains n single node trees (and no edges). At each of the step, we add on one (the cheapest one) edg

Example which cause problems for hidden-surface algorithms, Example which c...

Example which cause problems for some hidden-surface algorithms Some special cases, which cause problems for some hidden-surface algorithms, are penetrating faces and cyclic ov

Sequential search of a list is preferred over binary search, What are the c...

What are the conditions under which sequential search of a list is preferred over binary search? Sequential Search is a preferred over binary search when the list is unordered

Elaborate the symbols of abstract data type, Elaborate the symbols of abstr...

Elaborate the symbols of abstract data type length(a)-returns the number of characters in symbol a. capitalize(a)-returns the symbol generated from a by making its first cha

Determine the effect of ruby in implementation of string, Determine the eff...

Determine the effect of Ruby in implementation of string Ruby has a String class whose instances are mutable sequences of Unicode characters. Symbol class instances are charact

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