Computer Science

 According the property of Red-Black tree, no two Red node come together (as Parent-Child relation). So if it happens then we have to reordering the tree either by recoloring or by rotation. Note: Here NULL will considered as Black node If the uncle of the conflicting child is red:          Apply Recoloring:                    If G is root node then change it to black, also check if parent of G is red, if yes apply reordering recursively If the uncle of the conflicting child is Black:          Apply Rotation:                 Zig-Zig Rotation: This is similar to LL/RR rotation:                    Zig-Zag Rotation: This is similar to LR/RL rotation: Let us create a tree by using the following nodes:               10, 20, 30, 50, 40, ...

Properties: It's a height balanced BST, similar to 2-3-4 Tree. Every Node is either Red or Black Root of  a tree is Black Null is also Black Number of Blacks on paths from Root to Leaf are same No 2 consecutive Red, children and parent of Red   is Black New inserted node is Red Height in logn <= h <= 2*logn (height of AVL is 1.44logn)

Insertion:               Let we create 2-3 tree by inserting elements:                                                                      20, 30, 40, 50, 60, 10, 15, 70, 80                Insert 20,30:               Now we insert these two element in a single node as it can hold 2 elements so,       Insert 40:               Node is already full so split the node             In splitting: We take two nodes left and right and a root node Left node contain smallest element Right node contain greatest element Root node contain middle element and take lest and ...

 Some properties: Multiway/M-way search tree Degree : 3 (maximum no. of children) All leaf at same level Every node must have at least ceil(n/2 here 3/2) children Also call B-Tree of degree 3 Can't have duplicate element Representation: l contain all the element smaller than k1 m contain all the element b/w k1 and k2 n contain all the element greater than n k1 < k2 for every node Applications: Used as example during study B-Tree and B+ Tree Used internally in DBMS    

Rotation is required only in the nodes which are imbalance, imbalance means that | height of right sub-tree - height of left sub-tree | > 1. Balancing reduce the height of tree like a tree with node n have maximum height (n-1) but after rotation it will be about log(n).

 AVL tree is a self-balancing binary search tree.

Introduction:            A Binary Search Tree or BST is a binary tree in which left child of every node contain child whose value is smaller than current node and right child will contain child whose value is greater than current node. Binary Search Tree Insertion:          There are many cases which must be consider to run the program without any error.          Function execute: Reursive function -> Node* push(data,current_node)          Every function return node or subtree which contain node to be inserted          We always start from root node           Let us consider an example of inserting 40 in the given tree     Case 1: When data < current_node->data                Step 1: Compere 40 with current_node (here root)->data, 40<50     ...