From f9a7d9cd8a7e603c89d4cc5d98d7f694cc217d85 Mon Sep 17 00:00:00 2001
From: Soikk
Date: Sat, 6 Aug 2022 21:46:45 +0200
Subject: Refactored database. Replaced htable with ctable (same thing
 different name). Introduced AVL tree for hashes.

---
 DOC | 10 ++++++++++
 1 file changed, 10 insertions(+)

(limited to 'DOC')

diff --git a/DOC b/DOC
index 6f1f195..4372f8b 100644
--- a/DOC
+++ b/DOC
@@ -67,6 +67,16 @@ STORAGE
 	If the relation is already on the table, it returns -1. Otherwise, upon it returns 0 upon completion.
 	Searching for a relation returns the index [0 ... size-1] of said relation in the table, or -1 if its not found.
 
+	
+	AVL trees (tree, or node*) are self-balancing binary search trees used for storing the hashes and the index they store.
+	Random lookup, insertion and deletion is O(log n), which makes them very well suited for a database. I have chosen AVL trees over B-trees for simplicity.
+	The height of a node is 1 + the maximum of the height of its left and right children.
+	The balance of a node is the height of its left child minus the height of its right child.
+	The rotation, insert and delete functions are explained in
+		https://www.geeksforgeeks.org/avl-tree-set-1-insertion/
+		https://www.geeksforgeeks.org/avl-tree-set-2-deletion/
+		
+	
 
 DATABASE
 
-- 
cgit v1.2.3