AVL Tree / Red Black Tree Flashcards
What is a Binary Search Tree (BST)?
A Binary Search Tree is a binary tree in which each node has at most two children, and for every node, the left subtree contains only nodes with keys less than the node’s key, and the right subtree contains only nodes with keys greater than the node’s key.
What is the time complexity for searching in a BST?
The time complexity for searching in a BST is
O(h), where h is the height of the tree. In the average case, this is
O(logn), and in the worst case (unbalanced tree), this is
O(n).
What is the in-order traversal of a BST?
The in-order traversal of a BST visits nodes in non-decreasing order of their keys: left subtree, root, right subtree.
How do you insert a new node into a BST?
To insert a new node into a BST, start at the root and recursively find the correct position in the left or right subtree, then insert the node as a leaf.
How do you delete a node from a BST?
To delete a node from a BST:
Find the node to be deleted.
If the node has no children, simply remove it.
If the node has one child, replace it with its child.
If the node has two children, find its in-order successor (smallest node in the right subtree) or in-order predecessor (largest node in the left subtree), replace the node’s value with the successor’s value, and delete the successor.
What is the height of a BST?
The height of a BST is the length of the longest path from the root to a leaf. A BST with n nodes can have a minimum height of
log(n+1) and a maximum height of
n−1.
What is a balanced BST?
A balanced BST is a BST where the height of the left and right subtrees of any node differ by at most one. Balanced BSTs provide better performance for operations like search, insert, and delete, maintaining O(logn) time complexity.
What is an AVL tree?
An AVL tree is a self-balancing BST where the difference in heights of left and right subtrees of any node is at most one. If at any time this condition is violated, rotations are performed to restore balance.
What is a Red-Black tree?
A Red-Black tree is a self-balancing BST with the following properties:
Each node is either red or black.
The root is always black.
Red nodes cannot have red children (no two red nodes can be adjacent).
Every path from a node to its descendant NULL nodes has the same number of black nodes.
These properties ensure the tree remains balanced, with a height of O(logn).
What is the purpose of tree rotations in a BST?
Tree rotations are used to maintain or restore balance in a BST, particularly in self-balancing trees like AVL and Red-Black trees. Rotations re-arrange the nodes to ensure the height balance property is preserved, improving the efficiency of operations.
How do you perform a left rotation in a BST?
In a left rotation, a node x and its right child y are rotated such that y takes x’s place, x becomes y’s left child, and y’s left subtree becomes x’s right subtree.
How do you perform a right rotation in a BST?
In a right rotation, a node y and its left child x are rotated such that x takes y’s place, y becomes x’s right child, and x’s right subtree becomes y’s left subtree.
What is the difference between a BST and a binary tree?
A BST is a type of binary tree with the additional property that for each node, all elements in the left subtree are less than the node, and all elements in the right subtree are greater. A binary tree does not have this ordering property.
How do you check if a given binary tree is a BST?
To check if a binary tree is a BST, ensure that for every node, all elements in the left subtree are less than the node, and all elements in the right subtree are greater than the node. This can be done using in-order traversal, checking that the sequence of visited nodes is in ascending order.
Balance Factor
The difference between the heights of the left and right subtrees of a node.
