Author | Manuela Ruiz (mruiz@lcc.uma.es) |
This class represents a Balanced Binary Tree
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
another_bb_tree | |
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
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
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
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
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
returns::true iff the tree is empty
# File lib/data-structures.rb, line 792 792: def empty? 793: return !@root 794: end
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
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
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
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
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
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
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
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
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
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
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
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
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
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.
Generated with the Darkfish Rdoc Generator 1.1.6.