<commit_before># AVL\_Tree

_Rudimentary AVL tree library implementation as a tendermint hiring task_

---

### Installation

To install use the following commands

1. `go get github.com/rigelrozanski/AVL_tree`
2. `go get golang.org/x/crypto/sha3`

### Background

The AVL Tree is data storage structure which allows for the efficient retrieval of key-value pair data. It is an example of a self-balancing binary tree.The basic premise of a binary tree is that keys are linked to up to two childed keys where the left child has a key with a lesser value than its parents, and right child with a greater value.The AVL Tree by definition must always have a balance factor between (incl.) -1 and 1 where a balance factor is defined as the height of the right child node subtract the left child node. As such, an AVL Tree must reorganize itself through 'rotating' its nodes to achieve an appropriate balance factor. By maintaining a rough balance, and minimum overall height the number of operations required when searching for a record is minimized.

![N|Solid](https://upload.wikimedia.org/wikipedia/commons/thumb/a/ad/AVL-tree-wBalance_K.svg/262px-AVL-tree-wBalance_K.svg.png)

Further readings:  
https://en.wikipedia.org/wiki/AVL_tree  
https://en.wikipedia.org/wiki/Binary_tree  
https://en.wikipedia.org/wiki/Merkle_tree  
https://www.tutorialspoint.com/data_structures_algorithms/avl_tree_algorithm.htm  <commit_msg>minor readme change, closes #1<commit_after># AVL\_Tree

_Rudimentary AVL tree library implementation as a tendermint hiring task_

---

### Installation

To install use the following commands

1. `go get github.com/rigelrozanski/AVL_Tree`
2. `go get golang.org/x/crypto/sha3`

### Background

The AVL Tree is data storage structure which allows for the efficient retrieval of key-value pair data. It is an example of a self-balancing binary tree.The basic premise of a binary tree is that keys are linked to up to two childed keys where the left child has a key with a lesser value than its parents, and right child with a greater value.The AVL Tree by definition must always have a balance factor between (incl.) -1 and 1 where a balance factor is defined as the height of the right child node subtract the left child node. As such, an AVL Tree must reorganize itself through 'rotating' its nodes to achieve an appropriate balance factor. By maintaining a rough balance, and minimum overall height the number of operations required when searching for a record is minimized.

![N|Solid](https://upload.wikimedia.org/wikipedia/commons/thumb/a/ad/AVL-tree-wBalance_K.svg/262px-AVL-tree-wBalance_K.svg.png)

Further readings:  
https://en.wikipedia.org/wiki/AVL_tree  
https://en.wikipedia.org/wiki/Binary_tree  
https://en.wikipedia.org/wiki/Merkle_tree  
https://www.tutorialspoint.com/data_structures_algorithms/avl_tree_algorithm.htm  
{'fraction_non_alphanumeric': 0.07070353517675884, 'fraction_numerical': 0.005950297514875744, 'mean_word_length': 4.443809523809524, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 3, 'https://': 10, 'lorem ipsum': 0, 'www.': 2, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '4342268', 'n_tokens_mistral': 834, 'n_tokens_neox': 807, 'n_words': 348}