class AVL_SET_NODE [E_ -> COMPARABLE]

Features exported to AVL_SET

Auxiliary class to implement AVL_SET.

This a classic implementation of an AVL tree (balanced tree first designed by Adelson-Velskii and Landis, 1960)

Direct parents

conformant parents

ANY_AVL_SET_NODE, AVL_TREE_NODE

Summary

creation features

exported features

Creation:

Rotations:

Details

make (i: E_)

ensure

  • item = i

out_in_tagged_out_memory

ensure

  • not_cleared: tagged_out_memory.count >= old tagged_out_memory.count
  • append_only: (old tagged_out_memory.twin).is_equal(tagged_out_memory.substring(1, old tagged_out_memory.count))

left: AVL_SET_NODE [E_ -> COMPARABLE]
right: AVL_SET_NODE [E_ -> COMPARABLE]
item: E_
balance: INTEGER

Balance factor; either balanced (the tree is balanced), imbalanced_left (the left branch is the longer) or imbalanced_right (the right branch is the longer)

count: INTEGER
height: INTEGER
map_in (map: COLLECTION[AVL_SET_NODE [E_ -> COMPARABLE]])

require

  • map /= Void

ensure

  • map.count = old map.count + count

has (e: E_): BOOLEAN

Is element e in the tree?

fast_has (e: E_): BOOLEAN

Is element e in the tree?

ensure

  • Result implies count > 0

at (e: E_): AVL_SET_NODE [E_ -> COMPARABLE]

Is element e in the tree?

set_item (i: E_)

require

  • left /= Void implies left.item = i or else left.item < i
  • right /= Void implies right.item > i

ensure

  • item = i

set_left (l: AVL_SET_NODE [E_ -> COMPARABLE])

require

  • l /= Void implies l.item = item or else l.item < item

ensure

  • left = l

set_right (r: AVL_SET_NODE [E_ -> COMPARABLE])

require

  • r /= Void implies r.item > item

ensure

  • right = r

set_balance (b: INTEGER)

ensure

  • balance = b

rotate_right: AVL_SET_NODE [E_ -> COMPARABLE]

Proceeds to some reorganisation and returns the upper node.

ensure

  • Result /= Void

rotate_left: AVL_SET_NODE [E_ -> COMPARABLE]

Proceeds to some reorganisation and returns the upper node.

ensure

  • Result /= Void