Uses of Binary Tree

Start

We know that when user gave input in-order, it resulted in linked list. But searches for linked list become worse if the data gets increased. To avoid this, we used AVL tree for fast searches.

In worst case scenario, we’ve to search 1.44 log(n) (log with base 2) levels.

Expression Trees

“Expression trees, the more general parse trees and abstract syntax trees are significant components of compilers.”

A compiler translates high-level programming languages like Python, C++, etc., into assembly language. Then, an assembler converts the assembly language code into machine code (binary) that the computer’s processor can execute.

Given figure is the expression tree for the expression: (a+b*c)+((d*e+f)*g):

We’ll get into its detail in the next blog. For now, just understand the use of AVL or binary tree. Which tells us that the binary tree is used to store both operators and operands of the expression for evaluation.

Right now, just keep in mind:

Parse Tree in Compilers

See the expression tree of expression A := A + B * C below. We are multiplying B and C, Then adding the resultant in A and then finally assigning the resultant to A.

Relax! It’s not worse as it seems. This is just used by compilers to understand the expression and help them to decide that how they’re going to use this for evaluation.

• <assign> has 3 parts:
  • On the left of it, there is always an identifier (single or an array reference) called l-value. In above case, the l-value is <id> and identifier is A.The middle one is assignment operator (= or :=).
  • On the right side, there is <expr>
• Node <expr> has 3 sub-nodes:
  • <expr>+
  • <term>
• <expr>’s further left subtree is <expr>, <term>, <factor>, <id> and then finally is B.
• The right sub-child <term> has further sub-nodes as <term>, * and <factor>.
• <factor> has <id>
• <id> has C.

Parse Tree for an SQL Query

The parse trees are used in query processing.

The queries are questions to the databases to see a particular kind of data.

Consider you have a database for a video store that contains data of movies and artists etc. You are querying that database to find the titles of movies with stars born in 1960.

The language used to query from the database is called SQL (Structured Query Language)

So the SQL to retrieve information from this database:

SELECT title
FROM StarsIn, MovieStar
WHERE starName = name AND birthdate LIKE ‘%1960’ ;

In this way, the query is evaluated.

Compiler Optimization

You can consider optimization as the compiler will think before it do its job. It won’t step into evaluation mode blindly. Think it as the intelligence of the compiler.

The root node is +, left subtree is capturing the f+d*e expression while the right subtree is capturing (d*e+f)*g.

Common Subexpressions and Optimizer

Normally compilers has intelligence to look at the common parts inside parse trees. For example in the tree above, the expressions f+d*e and d*e+f are same basically.

These common subtrees are called common subexpressions. To gain efficiency, instead of calculating the common subexpressions again, the compilers calculates them once and use them at other places. The part of the compiler that is responsible to do this kind of optimization is called optimizer.

REFERENCE: CS301 Handouts (page 279 to 283)