Binary Search Tree
In a Binary Search Tree(BST), when a list of numbers are given, the left side of the root node should have the data should have a number lesser than the root element and the right side should always have the number greater than the root element. This pattern follows until the leaf node is reached.
AVL Tree
It is a BST
Hight of left subtree minus the height of right subtree it is the balance factor. This answer should be either{-1,0,1}.
Duplicate elements are not allowed.
Here are some points to remember
When a root node has right side but no left side it is 0-(degree of the element). When a root node has leftside but no right side it is (Degree of the node)-0.
If the element is balanced its balance factor is zero.
Balance factor is the degree of the node.
When an element is towards the left it is positive. But if it is towards the right then is negative.
When calculating the degree of the node it is the number of the levels until the leaf node is reached.
Left rotation- Where the element in the right comes above the parent node.
Right rotation- Where the element in the left comes above the parent node.
While deleting the node replace root node either by the inorder predessor or the inorder successer.
Inorder predecessor- Relace by the highest element in the right subtree.
Inorder successor- Replace by the lowest element in the right subtree.
B-Tree
In this type of tree each node has more than one data or number. Like BST the lesser element is towards the left and the greater element is towards the right. You can imagine an array of elements in each node and in between each number there is the address to the next node with element greater or lesser than the current element. Here are some points to remember.
Balanced m-way tree
Generalization of BST in which a node can have more than one key and more than 2 children.
Maintains sorted data
All leaf node must be at the same level
Every node has max m children
Min children-
leaf->0
root->2
internodes->[m/2]
Every node has max(m-1) keys
Min keys- Root node->1, all other nodes->[m/2]-1
Deletion in B-Tree
The key which has to be deleted is called the target key.
If target key is in leaf node
If target key is in internal node
Order(M)=5
min children=[M/2]
max children=5
min keys=2([M/2]-1)
max keys=4
If case 1
leaf node contains more than min no of keys
Borrow from immediate left node.
Borrow from immediate right node.
Leaf node contains min no of keys
B+ Tree
A B+ tree is a type of self-balancing tree data structure used for efficient searching, inserting, and deleting operations. It is just like the B tree but all the leaf nodes are interconnected. In a B+ tree, all keys are stored in internal nodes, but actual data is stored only in leaf nodes, which are linked together for fast sequential access.
The main advantage of a B+ tree is that it reduces the number of disk accesses, making it ideal for handling large amounts of data. Since all data is in the leaf nodes, range queries and ordered retrieval are much faster compared to other tree structures.
Here are some points to remember about B+ tree.
Order(M) = 5
Min children = [M/2]
Max children = 5
Min keys = [M/2] - 1
Max keys = M - 1
Leaf nodes:
Min keys = [M/2] - 1
Max keys = M - 1
Hope you learnt something new from this blog.
Happy Coding…