### Home Classes Methods

### In Files

- lib/data-structures.rb

### Parent

Object

### Methods

- ::new
- #==
- #clone
- #delete_node
- #doubleRotateWithLeftChild
- #doubleRotateWithRightChild
- #empty?
- #fetchSuccessor
- #get_next
- #get_node
- #has_next
- #hash
- #height
- #insert_node
- #rebalanceTree
- #rebalanceTreeAfterFetchSuccessor
- #removeNode
- #reset_iterator
- #rotateWithLeftChild
- #rotateWithRightChild
- #to_array

### Files

- LessThan5BlueLabels.txt
- AtLeast2LargeSegments.txt

### Class Index

Quicksearch

- AddLabelTool
- AllRulesAppliedGoal
- Area
- AreaConstraint
- Array
- BalancedBinaryTree
- BalancedBinaryTreeNode
- CloseObserver
- Constants
- Constraint
- CurrentLabelledShape
- DistinctShapeConstraint
- Execution
- Goal
- Grammar
- Label
- LabelledShape
- LineDescriptor
- LinearLinkedList
- LinearLinkedListNode
- NoLabelsGoal
- NoMoreRulesGoal
- NoScalesConstraint
- Numeric
- Object
- OrderedPoint
- PiList
- Point
- Project
- Robot
- Rule
- RuleGroupsObserver
- RuleLabelledShape
- RuleShapeObserver
- Segment
- ShaDeLayersObserver
- Shade
- ShadeUtils
- UndoObserver

No matching classes.

# BalancedBinaryTree

Author | Manuela Ruiz (mruiz@lcc.uma.es)

This class represents a Balanced Binary Tree

### Attributes

root[RW]

Root of the tree. It is a BalancedBinaryTreeNode

size[RW]

Number of nodes in the tree

### Public Class Methods

new() click to toggle source

Initialize the BalancedBinaryTree

         # File lib/data-structures.rb, line 439
    439:         def initialize()

    440:                 @root = nil

    441:                 @size = 0

    442:                 @iterNode = @root

    443:                 @itNodePath = Array.new

    444:         end

### Public Instance Methods

==(another_bb_tree) click to toggle source

another_bb_tree | a BalancedBinaryTree
returns | true if this and another_bb_tree are equal

         # File lib/data-structures.rb, line 867
    867:         def == (another_bb_tree)

    868:                 self_array = self.to_array

    869:                 if !another_bb_tree

    870:                         another_bb_tree = BalancedBinaryTree.new

    871:                 end

    872:                 other_array = another_bb_tree.to_array

    873:                 result = (self_array.length == other_array.length)

    874:                 if result

    875:                         i = 0

    876:                         while ((i < self_array.length) && result)

    877:                                 self_node = self_array[i]

    878:                                 other_node = other_array[i]

    879:                                 result = (result && (self_node.key == other_node.key) && (self_node.list == other_node.list))

    880:                                 i+= 1

    881:                         end

    882:                 end

    883:                 return result

    884:

    885:         end

clone() click to toggle source

returns | a BalancedBinaryTree object identical to this

         # File lib/data-structures.rb, line 853
    853:         def clone

    854:                 new_tree = BalancedBinaryTree.new

    855:                 self.reset_iterator

    856:                 while self.has_next

    857:                         node = self.get_next

    858:                         new_node = node.clone

    859:                         new_tree.insert_node new_node

    860:                 end

    861:                 return new_tree

    862:         end

delete_node(n) click to toggle source

n | a key to delete from this BalancedBinaryTree
returns | true iff removal is performed

Deletes the node n from the tree and rebalances the tree

         # File lib/data-structures.rb, line 450
    450:         def delete_node(n)

    451:                 nodePath = Array.new

    452:

    453:                 current = @root

    454:

    455:                 while current

    456:                         nodePath.push current

    457:

    458:                         if n < current.key

    459:                                 if ((current.left) && n == current.left.key)

    460:                                         current.left = removeNode(current.left)

    461:                                         @size = @size - 1

    462:                                         rebalanceTree(nodePath, false)

    463:                                         return true

    464:                                 end

    465:                                 current = current.left

    466:

    467:                         elsif current.key < n

    468:                                 if ((current.right) && n == current.right.key)

    469:                                         current.right = removeNode(current.right)

    470:                                         @size = @size - 1

    471:                                         rebalanceTree(nodePath, false)

    472:                                         return true

    473:                                 end

    474:                                 current = current.right

    475:

    476:                         else

    477:                                 @root = removeNode(current) #Root is to be removed

    478:                                 @size = @size - 1

    479:                                 rebalanceTree(nodePath, false)

    480:                                 return true

    481:                         end

    482:                 end

    483:                 return false

    484:         end

doubleRotateWithLeftChild(sRoot) click to toggle source

sRoot | The root of the subtree with which to double rotate the node’s left child
returns | The node that is the new root of the specified root’s subtree.

         # File lib/data-structures.rb, line 708
    708:         def doubleRotateWithLeftChild(sRoot)

    709:                 sRoot.left = rotateWithRightChild(sRoot.left)

    710:

    711:                 return rotateWithLeftChild(sRoot)

    712:         end

doubleRotateWithRightChild(sRoot) click to toggle source

sRoot | The root of the subtree with which to double rotate the node’s right child
returns | The node that is the new root of the specified root’s subtree.

         # File lib/data-structures.rb, line 718
    718:         def doubleRotateWithRightChild(sRoot)

    719:                 sRoot.right = rotateWithLeftChild(sRoot.right)

    720:

    721:                 return rotateWithRightChild(sRoot)

    722:         end

empty?() click to toggle source

returns::true iff the tree is empty

         # File lib/data-structures.rb, line 792
    792:         def empty?

    793:                 return !@root

    794:         end

fetchSuccessor(sRoot) click to toggle source

sRoot | the root of the subtree of which to fetch the logical successor node
returns | the successor node of the specified subtree root node

Removes and returns the node that is the logical in-order successor of the specified subtree root node

         # File lib/data-structures.rb, line 526
    526:         def fetchSuccessor(sRoot)

    527:                 if (!sRoot || !sRoot.right)

    528:                         return nil

    529:                 end

    530:

    531:                 successorNode = sRoot.right

    532:

    533:                 if !sRoot.right.left

    534:                         sRoot.right = successorNode.right

    535:                         return successorNode

    536:                 else

    537:                         nodePath = Array.new

    538:                         nodePath.push sRoot

    539:                         current = sRoot.right

    540:

    541:                         while (current.left.left)

    542:                                 nodePath.push current

    543:

    544:                                 current = current.left

    545:                         end

    546:

    547:                         nodePath.push current

    548:

    549:                         successorNode = current.left

    550:                         current.left = current.left.right

    551:

    552:                         rebalanceTreeAfterFetchSuccessor(nodePath)

    553:

    554:                         return successorNode

    555:                 end

    556:         end

get_next() click to toggle source

returns | the next element of the iterator

         # File lib/data-structures.rb, line 808
    808:         def get_next

    809:                 nextElement = nil

    810:

    811:                 while @iterNode

    812:                         @itNodePath.push(@iterNode)

    813:

    814:                         @iterNode = @iterNode.left

    815:                 end

    816:

    817:                 if !@itNodePath.empty?

    818:                         @iterNode = @itNodePath.pop

    819:                         nextElement = @iterNode

    820:                         @iterNode = @iterNode.right

    821:                 end

    822:

    823:                 return nextElement

    824:         end

get_node(key) click to toggle source

key::key of the node we want to recover

returns | the node with the specified key. In case it does not exists, returns nil.

         # File lib/data-structures.rb, line 774
    774:         def get_node(key)

    775:                 result = nil

    776:                 current = @root

    777:                 found = false

    778:                 while current && !found

    779:                         if key < current.key

    780:                                 current = current.left

    781:                         elsif current.key < key

    782:                                 current = current.right

    783:                         else

    784:                                 found = true

    785:                                 result = current

    786:                         end

    787:                 end

    788:                 return result

    789:         end

has_next() click to toggle source

returns | true if the iterator has more elements

         # File lib/data-structures.rb, line 803
    803:         def has_next

    804:                 return (@iterNode or !@itNodePath.empty?)

    805:         end

hash() click to toggle source

returns | the hash code for this tree

         # File lib/data-structures.rb, line 888
    888:         def hash

    889:                 array = self.to_array

    890:                 hash_array = Array.new

    891:                 array.each { |node|

    892:                         hash_array.push node.hash

    893:                 }

    894:                 return hash_array.hash

    895:         end

height(node) click to toggle source

node::The node of which to get the height.

returns | The height of the node in the tree or -1 if the node is null.

         # File lib/data-structures.rb, line 670
    670:         def height(node)

    671:                 if node

    672:                         return node.height

    673:                 else

    674:                         return 1

    675:                 end

    676:         end

insert_node(n) click to toggle source

n | a BalancedBinaryTreeNode to add to this BalancedBinaryTree
returns | the inserted node or the previously existing node in case the key already exist in the tree

     Adds the specified node as an offspring of the tree, maintaining the order

         # File lib/data-structures.rb, line 728
    728:         def insert_node(n)

    729:                 nodePath = Array.new

    730:

    731:                 current = @root

    732:                 while current

    733:                         nodePath.push current

    734:

    735:                         if n.key < current.key

    736:

    737:                                 if !current.left

    738:                                         current.left = n

    739:                                         @size += 1

    740:

    741:                                         rebalanceTree(nodePath, true)

    742:

    743:                                         return n

    744:                                 end

    745:

    746:                                 current = current.left

    747:

    748:                         elsif current.key < n.key

    749:

    750:                                 if !current.right

    751:                                         current.right = n

    752:                                         @size += 1

    753:

    754:                                         rebalanceTree(nodePath, true)

    755:

    756:                                         return n

    757:                                 end

    758:

    759:                                 current = current.right

    760:                         else #Element is already stored in the tree

    761:                                 return current

    762:                         end

    763:                 end

    764:

    765:                 #The tree is empty

    766:                 @root = n

    767:                 @size += 1

    768:                 return n

    769:         end

rebalanceTree(nodePath, isInsertion) click to toggle source

nodePath | the stack which contains the nodes in the order that they were traversed
isInsertion | Indicates whether insertion or removal was performed

Rebalances the tree after an insertion or a removal

         # File lib/data-structures.rb, line 593
    593:         def rebalanceTree(nodePath, isInsertion)

    594:                 while !nodePath.empty?

    595:                         current = nodePath.pop();

    596:

    597:                         #Check for an imbalance at the current node:

    598:                         if (height(current.left) - height(current.right) == 2)

    599:                                 #Compare heights of subtrees of left child node of

    600:                                 #imbalanced node (check for single or double rotation case

    601:                                 if (height(current.left.left) >= height(current.left.right))

    602:                                         #Check if imbalance is internal or at the tree root:

    603:                                         if (!nodePath.empty?)

    604:                                                 #Compare current element with element of parent

    605:                                                 #node (check which child reference to update for the

    606:                                                 #parent node):

    607:                                                 if (current.key < nodePath.last.key)

    608:                                                         nodePath.last.left = rotateWithLeftChild(current)

    609:                                                 else

    610:                                                         nodePath.last.right = rotateWithLeftChild(current)

    611:                                                 end

    612:                                         else

    613:                                                 @root = rotateWithLeftChild(current)

    614:                                         end

    615:                                 else

    616:                                         if (!nodePath.empty?)

    617:                                                 if (current.key < nodePath.last.key)

    618:                                                         nodePath.last.left = doubleRotateWithLeftChild(current)

    619:                                                 else

    620:                                                         nodePath.last.right = doubleRotateWithLeftChild(current)

    621:                                                 end

    622:                                         else

    623:                                                 @root = doubleRotateWithLeftChild(current)

    624:                                         end

    625:                                 end

    626:

    627:                                 current.height = ([height(current.left),height(current.right)].max) + 1

    628:

    629:                                 if isInsertion

    630:                                         break

    631:                                 end

    632:                         elsif (height(current.right) - height(current.left) == 2)

    633:                                 if (height(current.right.right) >= height(current.right.left))

    634:                                         if (!nodePath.empty?)

    635:                                                 if ((current.key < nodePath.last.key))

    636:                                                         nodePath.last.left = rotateWithRightChild(current)

    637:                                                 else

    638:                                                         nodePath.last.right = rotateWithRightChild(current)

    639:                                                 end

    640:                                         else

    641:                                                 @root = rotateWithRightChild(current)

    642:                                         end

    643:                                 else

    644:                                         if (!nodePath.empty?)

    645:                                                 if ((current.key < nodePath.last.key))

    646:                                                         nodePath.last.left = doubleRotateWithRightChild(current)

    647:                                                 else

    648:                                                         nodePath.last.right = doubleRotateWithRightChild(current)

    649:                                                 end

    650:                                         else

    651:                                                 @root = doubleRotateWithRightChild(current)

    652:                                         end

    653:                                 end

    654:

    655:                                 current.height = ([height(current.left),height(current.right)].max) + 1

    656:

    657:                                 if isInsertion

    658:                                         break

    659:                                 end

    660:                         else

    661:                                 current.height = ([height(current.left),height(current.right)].max) + 1

    662:                         end

    663:                 end

    664:         end

rebalanceTreeAfterFetchSuccessor(nodePath) click to toggle source

nodePath | the stack which contains the nodes in the order that they were traversed

Restores balance to the tree after a node successor has been fetched given the specified node traversal path

         # File lib/data-structures.rb, line 561
    561:         def rebalanceTreeAfterFetchSuccessor(nodePath)

    562:

    563:                 while nodePath.size > 2

    564:                         current = nodePath.pop

    565:

    566:                         if (height(current.right) - height(current.left) == 2)

    567:                                 if (height(current.right.right) >= height(current.right.left))

    568:                                         nodePath.last.left = rotateWithRightChild(current)

    569:                                 else

    570:                                         nodePath.last.left = doubleRotateWithRightChild(current)

    571:                                 end

    572:                         end

    573:

    574:                         current.height = ([height(current.left) , height(current.right)].max) + 1

    575:                 end

    576:                 #Current node is root of right subtree of removal node:

    577:                 current = nodePath.pop

    578:                 if (height(current.right) - height(current.left) == 2)

    579:                         if (height(current.right.right) >= height(current.right.left))

    580:                                 nodePath.last.right = rotateWithRightChild(current)

    581:                         else

    582:                                 nodePath.last.right = doubleRotateWithRightChild(current)

    583:                         end

    584:                 end

    585:

    586:                 current.height = ([height(current.left) , height(current.right)].max) + 1

    587:         end

removeNode(removalNode) click to toggle source

removalNode | the node to be removed from the tree
returns | the node to replace the removed node

Removes the specified node from the tree, returning an appropiate replacement node

         # File lib/data-structures.rb, line 490
    490:         def removeNode(removalNode)

    491:

    492:                 if (removalNode.left && removalNode.right)

    493:                         replacementNode = fetchSuccessor(removalNode)

    494:

    495:                         replacementNode.left = removalNode.left

    496:                         replacementNode.right = removalNode.right

    497:

    498:                         if ((height(replacementNode.left) - height(replacementNode.right)) == 2)

    499:                                 if (height(replacementNode.left.left) >= height(replacementNode.left.right))

    500:                                         replacementNode = rotateWithLeftChild(replacementNode)

    501:                                 else

    502:                                         replacementNode = doubleRotateWithLeftChild(replacementNode)

    503:                                 end

    504:                         end

    505:

    506:                         replacementNode.height = ([height(replacementNode.left),height(replacementNode.right)].max) + 1

    507:                 else

    508:                         if removalNode.left

    509:                                 replacementNode = removalNode.left

    510:                         else

    511:                                 replacementNode = removalNode.right

    512:                         end

    513:                 end

    514:

    515:                 removalNode.left = nil

    516:                 removalNode.right = nil

    517:

    518:                 return replacementNode

    519:

    520:         end

reset_iterator() click to toggle source

Resets the iterator of the tree

         # File lib/data-structures.rb, line 797
    797:         def reset_iterator

    798:                 @iterNode = @root

    799:                 @itNodePath = Array.new

    800:         end

rotateWithLeftChild(sRoot) click to toggle source

sRoot | The root of the subtree with which to rotate the node’s left child
returns | The node that is the new root of the specified root’s subtree.

         # File lib/data-structures.rb, line 681
    681:         def rotateWithLeftChild(sRoot)

    682:                 newRoot = sRoot.left

    683:                 sRoot.left = newRoot.right

    684:                 newRoot.right = sRoot

    685:

    686:                 sRoot.height = ([height(sRoot.left) , height(sRoot.right)].max) + 1

    687:                 newRoot.height = ([height(newRoot.left), sRoot.height].max) + 1

    688:                 return newRoot

    689:         end

rotateWithRightChild(sRoot) click to toggle source

sRoot | The root of the subtree with which to rotate the node’s right child
returns | The node that is the new root of the specified root’s subtree.

         # File lib/data-structures.rb, line 694
    694:         def rotateWithRightChild(sRoot)

    695:                 newRoot = sRoot.right

    696:                 sRoot.right = newRoot.left

    697:                 newRoot.left = sRoot

    698:

    699:                 sRoot.height = ([height(sRoot.left) , height(sRoot.right)].max) + 1

    700:                 newRoot.height = ([sRoot.height, height(newRoot.right)].max) + 1

    701:

    702:                 return newRoot

    703:         end

to_array() click to toggle source

returns | the nodes of the tree in the form of an array

         # File lib/data-structures.rb, line 827
    827:         def to_array

    828:                 result = Array.new

    829:

    830:                 path = Array.new

    831:                 isDone = false

    832:                 current = @root

    833:

    834:                 while (!isDone)

    835:                         if current

    836:                                 path.push current

    837:                                 current = current.left

    838:                         else

    839:                                 if !path.empty?

    840:                                         current = path.pop

    841:                                         result.push current

    842:                                         current = current.right

    843:                                 else

    844:                                         isDone = true

    845:                                 end

    846:                         end

    847:                 end

    848:

    849:                 return result

    850:         end

Disabled; run with --debug to generate this.

[Validate]

Generated with the Darkfish Rdoc Generator 1.1.6.