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

Stacks, Q. Explain w hat are the stacks? How can we use the stacks  to chec...

Q. Explain w hat are the stacks? How can we use the stacks  to check whether an expression is correctly parentheses or not. For example (()) is well formed but (() or )()( is not w

Determine the importance of array, Determine the importance of array Ar...

Determine the importance of array Arrays are significant since they allow many values to be stored in a single data structure whereas providing very fast access to each value.

Write algorithm for post-order traversal, P os t - o r d e r T ...

P os t - o r d e r T r av er sal :  This can be done by both iteratively and recursively. The iterative solution would require a modification or alteration of the in-

Comparisons between linear and binary search, Comparative Study of Linear a...

Comparative Study of Linear and Binary Search Binary search is lots quicker than linear search. Some comparisons are following: NUMBER OF ARRAY ELEMENTS EXAMINED array

What is a height balanced tree, What is a height balanced tree? Height Ba...

What is a height balanced tree? Height Balanced Tree (AVL Tree) An AVL tree is a binary search tree in which the height of the left and right subtree of the root vary by at most

Algorithm, Ask question #MWhich of the following is not a characteristic of...

Ask question #MWhich of the following is not a characteristic of good algorithm? inimum 100 words accepted#

Encryption the plain-text using the round keys, Encryption the plain-text u...

Encryption the plain-text using the round keys: 1. (Key schedule) Implement an algorithm that will take a 128 bit key and generate the round keys for the AES encryption/decryp

Sparse metrics, Q. Define the sparse metrics and also explain the represent...

Q. Define the sparse metrics and also explain the representation of a 4X4 matrix using linked list.         Ans: A matrix in which number of zero entries is quite h

Efficiency of binary search, Each of the comparison in the binary search de...

Each of the comparison in the binary search decrease the number of possible candidates where the key value can be searched by a factor of 2 as the array is divided into two halves

Project, human resource management project work in c++

human resource management project work in c++

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