Solve problems that are commonly asked in C++ coding interviews related to common data structures.

Ace the C++ Coding Interview

Data structures are among the fundamentals of computer science and are often a core decision in developing efficient programs. They are categorized as a vital benchmark of computer science knowledge when it comes to industry interviews. This module contains a detailed review of common data structures in C++. We'll also become well-equipped with different data structures by implementing them.
By the end of this module, we'll have expertise in solving problems in data structures.

Data Structures

# Introduction

Named after inventors **A**delson-**V**elsky and **L**andi in 1962, they claimed that AVL trees are "An algorithm for the organization of information." They are Binary Search Trees such that for every internal Node $v$ of the tree $T$ the heights of $v$'s children can differ by at most $1$. To put it simply, for each Node, the height of the left and right subtrees in an AVL tree can differ at most by one, or the tree is *balanced*.  If, at any point, their difference becomes more than one, steps are taken to re-balance the tree. 

# Time Complexity

In the case of binary search trees, the time complexity of all three basic operations, Insertion, Deletion, and Search, take $O(h)$ time, where *"h"* is the height of Binary Search Tree. The worst-case time complexity is $O(n)$ for skewed BSTs, where *"n"* is the number of nodes in the tree. This is the same as an array or list. However, in the best case, when the tree is completely balanced, the time complexity for basic operations is $O(log(n))$. AVL trees are essentially that: BSTs in the best-case. 

The following diagram is an example of a valid AVL Tree.

This lesson is a brief introduction to AVL trees, why they are used, and what makes them more efficient than regular binary search trees.

What is an AVL Tree?

Introduction