Implementation of binary search trees in the Kotlin programming language

• Binary search tree
• AVL tree
• Red-Black tree

Description of the tree interface

K - the key type
V - the value type
N - the node type of the tree

TreeInterface<K : Comparable<K>, V> defines the basic operations for working with search trees:

✭ search(key: K): V? - searches for values ​​by key.

• If the key is found, it returns its value.
  
• If the key is not found returns null.
  

✭ insert(key: K, value: V) - inserts a new key with the specified value into the tree.

• If such a key already exists in the tree, an exception: "IllegalArgumentException" is thrown.
  
• If such a key and value pair already exists in the tree, an exception: "IllegalArgumentException" is thrown.
  

✭ remove(key: K) - removes the specified key from the tree

• If the key is not found in the tree, an exception: "NoSuchElementException" is thrown.
  

✭ getKeys(): List<K> - gets a list of all keys in ascending order.

• Returns a list of keys
  
• If the tree is empty, it returns empty list.
  

✭ getValues(): List<V> - gets a list of all values ​​in ascending order of their corresponding keys.

• Returns a list of values
  
• If the tree is empty, it returns empty list.
  

✭ getMinKey(): K? - gets the minimum key in the tree

• Returns the minimum key in the tree
  
• If the tree is empty, returns null.
  

✭ getMaxKey(): K? - gets the maximum key in the tree

• Returns the maximum key in the tree
  
• If the tree is empty, returns null.
  

✭ insert(list: List<Pair<K, V>>) - inserts multiple keys and specified values ​​in the order in which they appear in the specified list.

✭ remove(list: List<K>) - removes multiple keys in the order in which they appear in the specified list.

✭ replaceValue(key: K, newValue: V) - replaces the value of the specified key with the specified one

• If the key is not in the tree, an exception: "NoSuchElementException" is thrown
  

✭ clean() - completely clears the entire tree, removing all keys

Technologies

❀Kotlin version for JVM: 1.9.22
❀Kotlin Test Framework
Kotest Runner for JUnit 5 (JVM)
❀JVM 21

Launch

Example of use on an AVL tree:

val avlTree = AVLTreeSearch<Int, String>()
avlTree.insert(listOf(1 to "one", 2 to "two", 3 to "three", 4 to "four", 5 to "five"))
val keyRemove = avlTree.getMaxKey()
avlTree.remove(keyRemove)
for(i in avlTree.getValues()) {
  println(i)
}

Output:

one
two
three
four

Example of use on an Binary tree:

val tree = BinaryTreeSearch<Int, String>()
tree.insert(45, "apple")
tree.insert(30, "banana")
tree.insert(65, "apricot")
tree.insert(50, "lemon")
val keyRemove = tree.getMinKey()
tree.remove(keyRemove)
for(i in tree.getKeys()) {
  println(i)
}
println(tree.search(65))
tree.replaceValue(65, "orange")
println(tree.search(65))

Output:

45
50
65
apricot
orange

Example of use on an Red-Black tree:

val rbTree = RedBlackTreeSearch<Int, String>()
rbTree.insert(1, "bicycle")
rbTree.insert(2, "motorcycle")
rbTree.insert(3, "car")
rbTree.insert(4, "ship")
rbTree.insert(5, "plane")
rbTree.remove(6)

Output:

Exception in thread "main" java.util.NoSuchElementException: The key: 6 was not found in the tree.
...

License

Distributed under the MIT License. See LICENSE for more information.

Status

❤️ All trees and tests are implemented

Contact

• @Kirilich
• @b08lsoai
• @MigunovaAnastasia1

Authors:

• Nabieva Liya♡
• Tenyaeva Ekaterina♡
• Migunova Anastasia♡