Fractal pattern of nested geometric shapes
Image by Pete Linforth from Pixabay

Data Structures and Algorithms

Polish Notation

Infix expression

Postfix expression

Prefix Expression

How it works

Infix notation is the notation commonly used in arithmetical and logical formulae and statements. It is characterized by the placement of operators between operands—"infixed operators"—such as the plus sign in 2 + 2.

Postfix notation is a mathematical notation. It is a way to write down equations and other mathematical formulae. Postfix notation is also known as Reverse Polish Notation

Prefix notation is a mathematical notation. It is a way to write down equations and other mathematical formulae. Prefix notation is also known as Polish notation.

Operands are single letters or digits. Operators, from the highest priority to the lowest: ^ (power, evaluated from right to left); ! and ~ (negation, one operand); * and /; + and -; & (and); | (or). Other operators of equal priority are evaluated from left to right.

AVL Tree

Insert and delete keys: the tree keeps its balance by rotations.

    How it works

    An AVL tree is a binary search tree in which the heights of the two subtrees of every node differ by at most one. The number at a node is its balance: the height of the left subtree minus the height of the right one. After an insertion or a deletion the balance is checked from the changed place up to the root. A node with +2 or −2 is rotated, and when its taller subtree leans the other way, the rotation is double. A deleted key with two children is replaced by the largest key of its left subtree, as in my assignment.

    From the course

    • Semester 3
    • Lab works in Java and C++
    • Assignment 2: deleting a key from an AVL tree

    Useful resources

    1. Polish Notation Wikipedia article
    2. SlayStudy Learn Computer Science (Polish Notation algorithm), archived copy of 3 December 2023