From c37e08f643475a1a3fb3e2e3f5d4cf81297970d7 Mon Sep 17 00:00:00 2001
From: jwansek <eddie.atten.ea29@gmail.com>
Date: Mon, 17 May 2021 23:23:14 +0100
Subject: added heap data structure
---
SelfBalancingBinarySearchTree.java | 93 +++++++++++++++++++++++---------------
1 file changed, 57 insertions(+), 36 deletions(-)
(limited to 'SelfBalancingBinarySearchTree.java')
diff --git a/SelfBalancingBinarySearchTree.java b/SelfBalancingBinarySearchTree.java
index efb6ab2..31a5343 100644
--- a/SelfBalancingBinarySearchTree.java
+++ b/SelfBalancingBinarySearchTree.java
@@ -95,6 +95,12 @@ public class SelfBalancingBinarySearchTree<T extends Comparable<T>> {
}
return leftHeight - rightHeight;
}
+
+ public void leftRotate() {
+ BinaryTreeNode<T> newRoot = getRightChild();
+ newRoot.leftChild = this;
+ this.rightChild = newRoot.getLeftChild();
+ }
}
public static class DuplicateItemException extends Exception {
@@ -380,47 +386,62 @@ public class SelfBalancingBinarySearchTree<T extends Comparable<T>> {
public static void main(String[] args) {
SelfBalancingBinarySearchTree<Integer> bst = new SelfBalancingBinarySearchTree<>();
+ // try {
+ // bst.recursiveAdd(25);
+ // bst.recursiveAdd(15);
+ // bst.recursiveAdd(50);
+ // bst.recursiveAdd(10);
+ // bst.recursiveAdd(22);
+ // bst.iterativeAdd(35);
+ // bst.iterativeAdd(70);
+ // bst.iterativeAdd(4);
+ // bst.iterativeAdd(12);
+ // bst.iterativeAdd(18);
+ // bst.iterativeAdd(24);
+ // bst.iterativeAdd(31);
+ // bst.iterativeAdd(44);
+ // bst.iterativeAdd(66);
+ // bst.iterativeAdd(90);
+ // } catch (DuplicateItemException e) {
+ // e.printStackTrace();
+ // }
+
+ // System.out.println("In-Order Traversal:");
+ // for (Integer s : bst.new InOrderIterator()) {
+ // System.out.print(s + ", ");
+ // }
+ // System.out.println("");
+ // System.out.println("\nPre-Order Traversal:");
+ // for (Integer s : bst.new PreOrderIterator()) {
+ // System.out.print(s + ", ");
+ // }
+ // System.out.println("");
+ // System.out.println("\nPost-Order Traversal:");
+ // for (Integer s : bst.new PostOrderIterator()) {
+ // System.out.print(s + ", ");
+ // }
+ // System.out.println("");
+ // System.out.println("\nBreadth first Traversal:");
+ // for (Integer s : bst.new BreadthFirstIterator()) {
+ // System.out.print(s + ", ");
+ // }
+ // System.out.println("\n");
try {
- bst.recursiveAdd(25);
- bst.recursiveAdd(15);
- bst.recursiveAdd(50);
- bst.recursiveAdd(10);
- bst.recursiveAdd(22);
- bst.iterativeAdd(35);
- bst.iterativeAdd(70);
- bst.iterativeAdd(4);
- bst.iterativeAdd(12);
- bst.iterativeAdd(18);
- bst.iterativeAdd(24);
- bst.iterativeAdd(31);
- bst.iterativeAdd(44);
- bst.iterativeAdd(66);
- bst.iterativeAdd(90);
+ bst.recursiveAdd(9);
+ bst.recursiveAdd(6);
+ bst.recursiveAdd(20);
+ bst.recursiveAdd(4);
+ bst.recursiveAdd(7);
+ bst.iterativeAdd(15);
+ bst.iterativeAdd(26);
+ bst.iterativeAdd(22);
+ bst.iterativeAdd(30);
} catch (DuplicateItemException e) {
e.printStackTrace();
}
- System.out.println("In-Order Traversal:");
- for (Integer s : bst.new InOrderIterator()) {
- System.out.print(s + ", ");
- }
- System.out.println("");
- System.out.println("\nPre-Order Traversal:");
- for (Integer s : bst.new PreOrderIterator()) {
- System.out.print(s + ", ");
- }
- System.out.println("");
- System.out.println("\nPost-Order Traversal:");
- for (Integer s : bst.new PostOrderIterator()) {
- System.out.print(s + ", ");
- }
- System.out.println("");
- System.out.println("\nBreadth first Traversal:");
- for (Integer s : bst.new BreadthFirstIterator()) {
- System.out.print(s + ", ");
- }
- System.out.println("\n");
-
+ System.out.println(bst);
+ bst.root.leftRotate();
System.out.println(bst);
}
}
\ No newline at end of file
--
cgit v1.2.3