Concept of Binary Trees#
Full Binary Tree#
A binary tree in which each node has either 0 or 2 children, and all nodes with 0 children and nodes with 2 children are on the same level.
- There are a total of $2^{k}-1$ nodes (k is the depth of the tree).
- Each level has $2^{n-1}$ nodes (n is the current level).
Complete Binary Tree#
A binary tree in which only the last level may not be full, and the nodes in the last row must be sorted from left to right without any gaps.
- The bottom level can have 1 to $2^{k-1}$ nodes, with no gaps in between.
Binary Search Tree#
A binary search tree is an ordered tree, also known as a binary sort tree or a binary search tree.
- If the left subtree is not empty, then all nodes in the left subtree have values less than the value of their root node.
- If the right subtree is not empty, then all nodes in the right subtree have values greater than the value of their root node.
- Both the left and right subtrees are binary search trees.
- There are no nodes with equal keys.
The root node of a binary search tree is fixed and does not change. When inserting or deleting data, the binary tree may develop into a linked list, reducing the efficiency of data retrieval, so we have balanced binary trees.
Balanced Binary Tree#
AVL Tree (Adelson-Velsky and Landis Tree)
A balanced binary tree is an optimization of a binary tree.
- It can be an empty tree.
- The left and right subtrees of any node are balanced trees, and the absolute difference in height between them does not exceed 1.
Methods for achieving balance
Balance Factor: The difference in height (depth) between the left and right subtrees of a node is called the balance factor of the node. In a balanced binary tree, there are no nodes with a balance factor greater than 1 (only -1, 0, 1).
Balanced Binary Search Tree#
A balanced binary search tree is an empty tree or both the left and right subtrees are balanced binary trees (with a height difference of no more than 1).