Ask Your Question
0

Rotating binary trees gives unexpected error

asked 2016-08-26 03:26:24 -0500

Peter Luschny gravatar image

Hi all,

when I try

for d in DyckWords(3):
    print "--------------"        
    t = d.to_binary_tree()
    s = t.left_rotate()
    print ascii_art(t)
    print ascii_art(s)

I get "IndexError: list index out of range".

What am I doing wrong?

edit retag flag offensive close merge delete

Comments

1 answer

Sort by » oldest newest most voted
1

answered 2016-08-26 04:16:07 -0500

tmonteil gravatar image

updated 2016-08-26 04:16:58 -0500

The documentation of the left_rotate method starts with:

Left rotation on binary trees is defined as follows: Let T be a
binary tree such that the right child of the root of T is a node.

In the error happens when the following tree shows up:

sage: t
[[., [., .]], .]
sage: ascii_art(t)

  o
 /
o
 \
  o

So, indeed the right child of the root of t is not a node:

sage: ascii_art(t.left_rotate())
...
IndexError: list index out of range

sage: ascii_art(t.right_rotate())

o
 \
  o
 /
o

I agree that the error could be more explicit.

edit flag offensive delete link more

Comments

What I find more misleading is the description in the docs: "Left rotation on binary trees is defined as follows:" I think it would be much better to say: "Left rotation is only defined for binary trees where the right child of the root is a node, as follows:"

Peter Luschny gravatar imagePeter Luschny ( 2016-08-26 05:28:53 -0500 )edit

Indeed. Feel free to open and fill a ticket, i will review it.

tmonteil gravatar imagetmonteil ( 2016-08-26 06:17:13 -0500 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2016-08-26 03:26:24 -0500

Seen: 50 times

Last updated: Aug 26 '16