main file of AVLtree

SheyQ · SheyQ · commit 89e1175735b7 · 2019-02-20T23:30:04.000+08:00
diff --git a/Algorithm/AVLtree.cpp b/Algorithm/AVLtree.cpp
@@ -0,0 +1,183 @@
+#include"AVLtree.h"
+AVL::treenode* AVL::find(int val)
+{
+	if (nodecount == 0) return nullptr;
+	treenode* temp = root;
+	while (temp->value != val)
+	{
+		while (temp != nullptr && temp->value > val) temp = temp->left;
+		while (temp != nullptr && temp->value < val) temp = temp->right;
+		if (temp == nullptr) return nullptr;
+	}
+	return temp;
+}
+
+void AVL::clearall(treenode* node)
+{
+	if (node == nullptr) return;
+	clearall(node->left);
+	clearall(node->right);
+	delete node;
+}
+
+void AVL::print(treenode* node)
+{
+	if (node == nullptr) return;
+	print(node->left);
+	std::cout << node->value << " ";
+	print(node->right);
+}
+
+
+/* LL(insert into leftchild's leftsubtree of k1):
+    sigle rotate
+
+        k1				    k2
+       /  \				   /  \
+      k2   A  			  B    K1
+     /  \       ==>      /    / \
+    B    C  			D    C   A
+   /
+  D
+ */
+AVL::treenode* AVL::LLrotate(treenode* k1)
+{
+	treenode* k2 = k1->left;
+	k1->left = k2->right;
+	k2->right = k1;
+	k1->height = max(getheight(k1->left), getheight(k1->right)) + 1;
+	k2->height = max(getheight(k2->left), getheight(k2->right)) + 1;
+	return k2;
+}
+
+/* RR(insert into rightchild's rightsubtree of k1):
+	sigle rotate
+
+        k1				    	k2
+       /  \				  	   /  \
+      A   k2  			      k1   C
+         /  \       ==>      / \    \
+    	B    C  			A   B    D
+   	   		  \
+  	  		   D
+ */
+AVL::treenode* AVL::RRrotate(treenode* k1)
+{
+	treenode* k2 = k1->right;
+	k1->right = k2->left;
+	k2->left = k1;
+	k1->height = max(getheight(k1->left), getheight(k1->right)) + 1;
+	k2->height = max(getheight(k2->left), getheight(k2->right)) + 1;
+	return k2;
+}
+
+/* LR(insert into leftchild's rightsubtree of k1):
+	double rotate
+
+      k1                         k1                        k3
+     /  \                       /  \                      /  \
+    k2   A                     k3   A                    k2   k1
+   /  \         ==>           /           ==>           / \    \
+  B    k3                    k2                        B   C    A
+      /                    /   \
+     C                    B    	C
+*/
+AVL::treenode* AVL::LRrotate(treenode* k1)
+{
+	k1->left = RRrotate(k1->left);
+	return LLrotate(k1);
+}
+
+/* RL(insert into rightchild's leftsubtree of k1):
+	double rotate
+
+      k1                       		  k1                        k3
+     /  \                      		 /  \                      /  \
+    A   k2                   	    A    k3                   k1   k2
+	   /  \         ==>                 /  \        ==>      /    /  \
+	  k3    B                          C   k2          		A    C    B
+	 /                        				 \
+	C                         				  B
+*/
+AVL::treenode* AVL::RLrotate(treenode* k1)
+{
+	k1->right = LLrotate(k1->right);
+	return RRrotate(k1);
+}
+
+AVL::treenode* AVL::inserthelp(treenode*& node, int val)
+{
+	if (nodecount == 0) {
+		root->value = val;
+		return root;
+	}
+	if (node == nullptr)
+		return (node = new treenode(val, 0));
+	else if (node->value > val)
+		node->left = inserthelp(node->left, val);
+	else
+		node->right = inserthelp(node->right, val);
+	node->height = max(getheight(node->left), getheight(node->right)) + 1;
+	if (getheight(node->left) - getheight(node->right) == 2)
+	{
+		if (val < node->left->value)
+			node = LLrotate(node);
+		else
+			node = LRrotate(node);
+	}
+	else if (getheight(node->right) - getheight(node->left) == 2)
+	{
+		if (val < node->right->value)
+			node = RLrotate(node);
+		else
+			node = RRrotate(node);
+	}
+	return node;
+}
+
+AVL::treenode* AVL::removehelp(treenode*& node, int val)
+{
+	if (node == nullptr)
+	{
+		std::cout << "can't find " << val << std::endl;
+		return nullptr;
+	}
+	if (node->value == val)
+	{
+		if (node->right == nullptr)
+		{
+			treenode* temp = node;
+			node = node->left;
+			delete temp;
+			return root;
+		}
+		else
+		{
+			treenode* temp = node->right;
+			while (temp->left)
+				temp = temp->left;
+			node->value = temp->value;
+			node->right = removehelp(node->right, temp->value);
+		}
+	}
+	else if (node->value > val)
+		return removehelp(node->left, val);
+	else
+		return removehelp(node->right, val);
+	node->height = max(getheight(node->left), getheight(node->right)) + 1;
+	if (getheight(node->left) - getheight(node->right) == 2)
+	{
+		if (val < node->left->value)
+			node = LLrotate(node);
+		else
+			node = LRrotate(node);
+	}
+	else if (getheight(node->right) - getheight(node->left) == 2)
+	{
+		if (val < node->right->value)
+			node = RLrotate(node);
+		else
+			node = RRrotate(node);
+	}
+	return node;
+}
