if we take two empty binary search trees and insert the same elements but in different orderthen the resultant trees will be the same when we insert new node in binary search treeit will be added as an internal node mirror image of binary search tree is obtained by interchanging the left sub-tree with the right sub-tree at every node of the tree if the thread appears in the right fieldthen it will point to the in-order successor of the node if the node to be deleted is present in the left subtree of athen rotation is applied height of an avl tree is limited to (log critical node is the nearest ancestor node on the path from the root to the inserted node whose balance factor is - or rl rotation is done when the new node is inserted in the right sub-tree of the right sub-tree of the critical node in red-black treesome leaf nodes can be red fill in the blanks is also called fully threaded binary tree to find the node with the largest valuewe will find the value of the rightmost node of the if the thread appears in the right fieldthen it will point to the of the node the balance factor of node is calculated by balance factor - means searching an avl tree takes time rotation is done when the new node is inserted in the left sub-tree of the left sub-tree of the critical node in red-black treethe colour of the root node is and the colour of leaf node is the zig operation is done when in splay treesrotation is analogous to operation