0

1.2kviews

0

1.2kviews

0

4views

written 6.1 years ago by |

- A binary tree is a data structure in which every node has no more than two descendent nodes and no more than one parent node.
- A binary search tree is a binary tree in which a node’s left child node has a value less than its and the node’s right node has a value greater than its.
An AVL tree is a binary search tree which has the following properties:-

The sub-trees of every node differ in height by at most one.

Every sub-tree is an AVL tree.

- In this example, every left subtree has a height one greater than each right subtree

- The motivation of AVL trees was to guarantee a height of log(n) so that insertions and deletions always occur at O(log(n)).
- A balanced factor is an integer which is associated with each node of the tree. It indicates weather a tree is left-heavy (height of left subtree is greater than that of right subtree), balanced (both subtress are of the same height), or right-heavy(opposite of left-heavy).
- Balance factor of a node = height othe left subtree - the height of the right subtree
- Each node of an AVL tree can have a balanced factor of -1, 0 or +1 only.
- If the balanced factor’s magnitude exceeds 1 after an operation such as insertion or deletion, then balancing is required. This is done with the help of rotations.
- There are basically 4 types of imbalance cases and 2 types of rotations to make the tree balanced.

ADD COMMENT
EDIT

Please log in to add an answer.