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

Construct a minimum spanning tree, Construct G for α, n, and W given as com...

Construct G for α, n, and W given as command line parameters. Throw away edges that have an asymmetric relation between nodes. That is, if A is connected to B, but B is not connect

Multiqueue, data structure for multiqueue

data structure for multiqueue

Search on a hashed file, Write a program to simulate searching over a hashe...

Write a program to simulate searching over a hashed file, with different assumptions for the sizeof file pages.Write a program to perform equality search operations on the hashed f

Multikey file organization, what are the applications of multikey file orga...

what are the applications of multikey file organization?

Characteristics of good algorithms, What do we mean by algorithm? What are ...

What do we mean by algorithm? What are the characteristics of a good and relevant algorithm? An algorithm is "a step-by-step procedure for finishing some task'' An algorithm c

What is a data structure, Question 1 What is a data structure? Discuss bri...

Question 1 What is a data structure? Discuss briefly on types of data structures Question 2 Explain the insertion and deletion operation of linked list in detail Question

Binary search, Explain binary search with an example

Explain binary search with an example

Determine the class invariants- ruby, Determine the class invariants- Ruby ...

Determine the class invariants- Ruby Ruby has many predefined exceptions classes (like ArgumentError) and new ones can be created easily by sub-classing StandardError, so it's

Which data structure is used for implementing recursion, Which data structu...

Which data structure is used for implementing recursion Stack.

Arrays, This unit discussed about data structure called Arrays. The easiest...

This unit discussed about data structure called Arrays. The easiest form of array is a one-dimensional array which may be described as a finite ordered set of homogeneous elements

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