Data structures help

In our implementation of AVL search trees, we assumed that, in addition to the key and value, each node stored a pointer to its left and right child as well as the height of its subtree. Suppose that, in addition, we add a pointer to the node's parent in the tree. (The root node's parent pointer is set to null.) The new node structure is as follows, and the node constructor takes an additional argument specifying the parent: class AVLNode { Key key; Value value; int height; AVLNode left, right, parent; AVLNode (Key x, Value val, int hgt, AVLNode 1ft, AVLNode rgt, AVLNode par) { // constructor - details omitted } } Present pseudocode for an insert function that inserts a new key, applies the appropriate rebalancing, and updates the parent pointers appropriately. As with standard AVL insertion, your function should run in time (logn). Hint: This can be messy if you don't approach it carefully. I believe that the cleanest solution is to find all places where a left or right child is changed (e.g., p.left - 2) and fix the parent link right away. This works for almost all the cases where parent links need to be updated. Beware that q may be null, and you must never dereference null