What is the importance of the AVL tree?

AVL Tree(Hight - Balance Tree)
It is nothing but a Binary Search Tree (BST) with balance factor.
Balance Factor can be -1, 0, 1.
Balance Factor
Hight of left subtree - Hight of Right subtree.
Application of AVL tree
It is use to perform searching in O(log n) Time complexity.
Importance of AVL tree
Searching can be done by Binary Search Tree (BST) but if element are already sorted BST take form of chain and time complexity is O(n).
To overcome this problem AVL tree is introduced.
Due to balance factor it never take a form of chain, in fact AVL tree is nearly complete Binary tree.
Operations like Insertion, Deletion, Searching in a tree take O(log n) Time in worst case and Average case.

Comments

Post a Comment

Popular posts from this blog

What is the difference between Data Science, Big Data, Data Mining and Machine Learning?

Image
On an average, about 1.7 megabytes of new information will be created every second for every human being on the planet.According to IBM, 2.5 billion gigabytes (GB) of data was generated every day in 2012.Facebook users send on average 31.25 million messages and view 2.77 million videos every minute.Our accumulated digital universe of data will grow from 4.4 zettabytes today to around 44 zettabytes, or 44 trillion gigabytes. It is not possible to handle such a large amount of data using a traditional method like SQL or RDBMS, if we use these methods it may take a large amount of time to processed data. Also data not only of a single type (Structured) but also in Unstructured form. Let’s understand this two term. Structured Data : - Structured data is data that can be easily organized.It is clean, analytical and usually stored in databases.Some types of structured data can be machines generated, such as data that comes from medical devices (heart rate, blood pressure), manufacturing se...
Read more

What is the difference between spooling, buffering and caching in OS?

Spooling:  Simultaneous peripheral operation online, an acronym for this is Spooling. A spool is a kind of buffer that holds the jobs for a device till the device is ready to accept the job. Spooling considers disk as a huge buffer that can store as many jobs for the device till the output devices are ready to accept them. Buffering: The  buffer  is an area in the  main memory  that is used to store or hold the data  temporarily  that is being transmitted either between two devices or between a device or an application. In simple words, buffer temporarily stores data that is being transmitted from one place to another. The act of storing data temporarily in the buffer is called buffering.Buffering helps in  matching the speed between the sender and receiver  of the data stream. If the sender’s transmission speed is slower than receiver, then a buffer is created in main memory of the receiver, and it accumulates the bytes received from the...
Read more

About Me

I am Pranay Neema and pursuing my Engineering in Computer Science. I am here to share my knowledge about Technology, Data Structure, Algorithm and other Subjective Knowledge. I keep posting Notes to the reader. Ideas, feedback and suggestions are always welcome. The reader can request for content related to Computer Science. Luckily if I have a knowledge about requested content I can share.    
Read more