Binary tree rotations Balanced binary search trees are essential to guarantee O(log n) lookups (or similar operations). In a dynamic environment where a lot of keys are randomly inserted and/or deleted, trees might degenerate to linked lists which are horrible for lookups. Thus there are various kinds of self-balancing binary trees that counteract this effect (such as AVL trees or splay trees). These trees are based on different kinds of rotations that re-balance the tree.

Rotations

In this challenge we'll only look at single right-rotations, such a rotation (left-rotation would be symmetric) looks like this:

    5            3
   / \          / \
  3   6   =&gt;   1   5
 / \              / \
1   4            4   6


If any of the leaves 1,4 or 6 had left or right sub-trees a rotation would simply keep them there. If this is a subtree of a larger tree, we'd simply "cut it off" at the node 5 and "re-attach" the rotated tree (now node 3) to that node.

Challenge

Given a binary search tree1 and a key right-rotate the tree on that node as described above. The key provided in the above example would be 5.

Rules and I/O


you may use any type for keys as long as there is a bijection between the keys of your choice and those of the test cases
you may choose any representation for binary trees as long there's no ambiguity (eg. [3,[]] is ambiguous unless otherwise specified) and it's natural for your language of choice
since the input will always be a binary search tree there are no duplicate keys
you may assume that the key is contained in the tree
you may assume that node containing the key has a left child
you may not assume a right subtree under the provided key
you may not assume that the tree is unbalanced before the rotation
you may not assume that the tree is balanced after the rotation
you may use any default I/O method
your submission may be a function returning the tree or full program printing the solution


Test cases

These examples represent a tree as follows


if it's a leaf: []
if it's a tree with key x and both subtrees are leaves: [x]
if it's a tree with key x and subtrees left right: [x,left,right]


The first example is the one provided in the section Rotations. If for some reason you need a graphical representation of them, here2 you go.

5 [5,[3,[1],[4]],[6]]  -&gt;  [3,[1],[5,[4],[6]]]
5 [5,[3,[1],[4]],[]]  -&gt;  [3,[1],[5,[4],[]]]
5 [5,[3,[],[4]],[6]]  -&gt;  [3,[],[5,[4],[6]]]
5 [5,[3,[1],[]],[]]  -&gt;  [3,[1],[5]]
4 [8,[4,[2,[1],[3]],[6,[5],[7]]],[12,[10,[9],[11]],[14,[13],[15]]]]  -&gt;  [8,[2,[1],[4,[3],[6,[5],[7]]]],[12,[10,[9],[11]],[14,[13],[15]]]]
8 [10,[8,[6,[4,[2,[],[3]],[5]],[7]],[9]],[11]]  -&gt;  [10,[6,[4,[2,[],[3]],[5]],[8,[7],[9]]],[11]]
10 [10,[8,[6,[4,[2,[],[3]],[5]],[7]],[9]],[11]]  -&gt;  [8,[6,[4,[2,[],[3]],[5]],[7]],[10,[9],[11]]]
9 [6,[3,[2],[5]],[9,[8],[12,[11],[15,[14],[]]]]]  -&gt;  [6,[3,[2],[5]],[8,[],[9,[],[12,[11],[15,[14],[]]]]]]
7 [7,[5,[3,[1],[4]],[6]],[8]]  -&gt;  [5,[3,[1],[4]],[7,[6],[8]]]
15 [17,[9,[5,[2,[0],[4]],[8]],[15,[13,[11,[10],[12]],[14]],[16]]],[40,[27,[21,[19,[18],[20]],[24,[22],[25]]],[28]],[44,[42,[41],[]],[51,[47],[59,[55],[61]]]]]]  -&gt;  [17,[9,[5,[2,[0],[4]],[8]],[13,[11,[10],[12]],[15,[14],[16]]]],[40,[27,[21,[19,[18],[20]],[24,[22],[25]]],[28]],[44,[42,[41],[]],[51,[47],[59,[55],[61]]]]]]
21 [17,[9,[5,[2,[0],[4]],[8]],[15,[13,[11,[10],[12]],[14]],[16]]],[40,[27,[21,[19,[18],[20]],[24,[22],[25]]],[28]],[44,[42,[41],[]],[51,[47],[59,[55],[61]]]]]]  -&gt;  [17,[9,[5,[2,[0],[4]],[8]],[15,[13,[11,[10],[12]],[14]],[16]]],[40,[27,[19,[18],[21,[20],[24,[22],[25]]]],[28]],[44,[42,[41],[]],[51,[47],[59,[55],[61]]]]]]




1: meaning that for any node all the keys in the left subtree will be smaller than that key and all the keys in the right subtree are greater than it

2: to prevent link-rot, I embedded them as a comment
Haskell, 93 92 84 83 82 bytes



data B=B[B]Int|L
k!B[l@(B[x,y]a),r]n|k&lt;n=B[k!l,r]n|k&gt;n=B[l,k!r]n|1&gt;0=B[x,B[y,r]k]a


Thanks to @BMO, @alephalpha and @Laikoni for a byte each and @nimi for eight bytes!

Try it online!