Binary tree rotations

Question

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   =>   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 tree¹ 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, here² you go.

5 [5,[3,[1],[4]],[6]]  ->  [3,[1],[5,[4],[6]]]
5 [5,[3,[1],[4]],[]]  ->  [3,[1],[5,[4],[]]]
5 [5,[3,[],[4]],[6]]  ->  [3,[],[5,[4],[6]]]
5 [5,[3,[1],[]],[]]  ->  [3,[1],[5]]
4 [8,[4,[2,[1],[3]],[6,[5],[7]]],[12,[10,[9],[11]],[14,[13],[15]]]]  ->  [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]]  ->  [10,[6,[4,[2,[],[3]],[5]],[8,[7],[9]]],[11]]
10 [10,[8,[6,[4,[2,[],[3]],[5]],[7]],[9]],[11]]  ->  [8,[6,[4,[2,[],[3]],[5]],[7]],[10,[9],[11]]]
9 [6,[3,[2],[5]],[9,[8],[12,[11],[15,[14],[]]]]]  ->  [6,[3,[2],[5]],[8,[],[9,[],[12,[11],[15,[14],[]]]]]]
7 [7,[5,[3,[1],[4]],[6]],[8]]  ->  [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]]]]]]  ->  [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]]]]]]  ->  [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}

Answer 1

Haskell, 93 92 84 83 82 bytes

data B=B[B]Int|L
k!B[l@(B[x,y]a),r]n|k<n=B[k!l,r]n|k>n=B[l,k!r]n|1>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!

Answer 2

Vim, 25 bytes

Takes the input in the buffer - space separated key and tree. The tree is expected to be represented as follows:

• leaf: []
• node with key k, left child <left> and right child <right>: [ k <left><right>]

Not the spaces around the key k which are important, such that the solution works for arbitrary trees.

"adw/ <C-r>a⏎3dw%l"apr[%xl%i]

Try it online!

Explanation

"adw                           " delete the key and trailing space, keep in register a
    / <C-r>a⏎                  " move cursor to the key surrounded with spaces
             3dw               " remove key and [ (move left node to top)
                %l             " move cursor to the right subtree
                  "ap          " insert key there
                     r[        " insert a [ (appending subtree to key)
                       %       " move to the end of new left subtree
                        x      " remove ] (fix parentheses)
                         l%    " move to the end of new right subtree
                           i]  " insert ] (fix parentheses)

Preview

Here's a preview of the first test case, generated with this script by Lynn:

                       

Answer 3

Wolfram Language (Mathematica), 30 bytes

#2/.a_~b_~c_~#~d_:>b[a,c~#~d]&

Try it online!

A tree represented as follows:

• if it's a leaf: $ (you can replace it by any value which is not a key)
• if it's a tree with key x and subtrees left right: x[left,right]

For example, the tree in the first test case is represented by 5[3[1[$,$],4[$,$]],6[$,$]].

Explanation:

#2                                the second input
  /.                              replace
    a_~b_~c_~#~d_                 #[b[a,c],d], where # is the first input
                 :>               by
                   b[a,c~#~d]     b[a,#[c,d]]
                             &    define a function

Answer 4

Common Lisp, 146 bytes

(defun r(k a)(cond((not a)a)((=(car a)k)`(,(caadr a),(cadadr a)(,(car a),(car(cddadr a)),(caddr a))))(t`(,(car a),(r k(cadr a)),(r k(caddr a))))))

Try it online or verify all the testcases!

A tree is represented as follows:

• an empty tree is represented as nil (or equivalently in Common Lisp as the empty list ())
• a non-empty tree is represented as a list of three elements (node left-subtree right-subtree) (so a leaf L is represented as (L nil nil)).

Answer 5

JavaScript (Node.js), 70 bytes

n=>f=a=>n-a[0]?(a[i=n<a[0]?1:2]=f(a[i]),a):(i=a[1],a[1]=i[2],i[2]=a,i)

Try it online! Link includes test cases. All nodes must have left and right entries but they can be [] indicating no subtree on that side. As an abbreviation the test suite uses l(N) to indicate that N is a leaf and l(N,L) to indicate that N has a left subtree L but no right subtree both on input and output.

Answer 6

Python 2, 85 bytes

R=lambda T,k:k in T and T[1][:2]+[[T[0],T[1][2],T[2]]]or T[:1]+[R(i,k)for i in T[1:]]

Try it online!

Input format:

• Tree: [KEY, LEFT_SUBTREE, RIGHT_SUBTREE]
• Leaf: []

Answer 7

Jelly, 24 bytes

ñ
Ḣ,1ịṪƊṭ@ṪṭḢð{Ḣ;ç€ɗ¹¡i?

Try it online!

Warning: Normally, the top line shouldn't exist, and the bottom line should have a ß, not a ç. However, clever chain tricks and ß don't go well together, due to ß's variable arity. Technically, I could have still omitted the top line, but then the result would have had to be a full program, since otherwise it would have to be able to be incorporated as its own line inside any program, which isn't possible unless you're lucky. This means that, unfortunately, the output would've had an ambiguous representation, because, when you submit a full program, what gets actually output counts, and not what the result technically is before the program closes. So, in order to not make a mess with both recursion and proper string representation, I've decided to submit a 2-line function, where the top line's job is just to call the bottom one. The consequence? A huge waste of 2 precious and valuable bytes. In Jelly's (and Dennis's, as well as every other contributor's) defense, the language is still under active development, and is now experiencing a big wave of new features.