TreeTripper

Description

Library TreeTripper: provides implementations of the following binary search tree data structures:

• Binary Search Tree, see more information
• AVL tree, see more information
• Red-black tree, see more information

Important

The red-black tree is implemented based on the algorithm of left-linear red-black trees described by Robert Sedgewick on his website and presentation about it

The library supports the extension both internally (future library updates) and externally (implemented by the user).

Getting started

To run building library execute command:

./gradlew build -x test

To run tests of library execute command:

./gradlew test

Using library

Basic operations

• insert, see docs
• search, see docs
• remove, see docs

Examples

Example 1 (importing)

import tree_tripper.binary_trees.BSTree
import tree_tripper.binary_trees.AVLTree
import tree_tripper.binary_trees.RBTree


val simpleTree = BSTree<String, Int>() // initialization of empty simple binary search tree
val avlTree = AVLTree<Int, StringBuilder>() // initialization of empty AVL tree
val rbTree = RBTree<String, LinkedHashSet<Long>>() // initialization of empty Red-Black tree

Example 2 (inserting)

Code:

import tree_tripper.binary_trees.BSTree

fun main() {
    val tree = BSTree<Int, Int>()

    tree.insert(key = 1, value = 1)
    tree.insert(key = 2, value = 2)
    tree.insert(key = 3, value = 3)

    /* The words `key` and `value` are optional */
    tree.insert(4, 4)

    /* Alternative insert method */
    tree[5] = 5

    println(tree)
}

Output:

BSTree(1: 1, 2: 2, 3: 3, 4: 4, 5: 5)

Example 3 (searching)

Code:

import tree_tripper.binary_trees.BSTree

fun main() {
    val tree = BSTree<Int, Any>()
    /*
      ...
      inserting from `example 2`
      ...
    */

    /* Existing element in tree */
    println(tree.search(key = 1))
    println(tree.search(key = 3))
    println(tree.search(key = 5))

    /* Unexciting element in tree */
    println(tree.search(key = -2))
    println(tree.searchOrDefault(7, "Element not found"))

    /* Alternative search method */
    println(tree[2])
    println(tree[0])
}

Output:

1
3
5
null
Element not found
2
null

Example 4 (removing)

Code:

import tree_tripper.binary_trees.BSTree

fun main() {
    val tree = BSTree<Int, Any>()
  /*
    ...
    inserting from `example 2`
    ...
  */

    /* Existing element in tree */
    println(tree.remove(key = 1))
    println(tree.remove(key = 3))
    println(tree.remove(key = 5))

    /* Unexciting element in tree */
    println(tree.remove(key = -2))
    println(tree.removeOrDefault(key = 7, "Element not found"))

    println(tree)
}

Output:

1
3
5
null
Element not found
BSTree(2: 2, 4: 4)

Example 5 (tree-like printing)

Code:

import tree_tripper.binary_trees.BSTree
import tree_tripper.binary_trees.AVLTree
import tree_tripper.binary_trees.RBTree

fun main() {
    val simpleTree = BSTree<Int, Int>()
    val avlTree = AVLTree<Int, Int>()
    val rbTree = RBTree<Int, Int>()
    /*
      ...
      inserting similar to `example 2` for each tree
      ...
    */

    println("${simpleTree.toStringWithTreeView()}\n")
    println("${avlTree.toStringWithTreeView()}\n")
    println("${rbTree.toStringWithTreeView()}\n")
}

Output:

BSTree(
				(5: 5)
			(4: 4)
		(3: 3)
	(2: 2)
(1: 1)
)

AVLTree(
		(5: 5)
	(4: 4)
		(3: 3)
(2: 2)
	(1: 1)
)

RBTree(
	(5: 5) - BLACK
(4: 4) - BLACK
		(3: 3) - BLACK
	(2: 2) - RED
		(1: 1) - BLACK
)

Example 6 (iterators)

Code:

import tree_tripper.binary_trees.AVLTree

fun main() {
  val tree = AVLTree<Int, Int>()
  /*
    ...
    inserting from `example 2`
    ...
  */
  
  println("WIDTH ORDER:")
  tree.forEach(IterationOrders.WIDTH_ORDER) {
    println(it)
  }
  println()
  println("INCREASING ORDER:")
  tree.forEach(IterationOrders.INCREASING_ORDER) {
    println(it)
  }
  println()
  println("DECREASING ORDER:")
  tree.forEach(IterationOrders.DECREASING_ORDER) {
    println(it)
  }
}

Output:

WIDTH ORDER:
(2: 2)
(1: 1)
(4: 4)
(3: 3)
(5: 5)

INCREASING ORDER:
(1: 1)
(2: 2)
(3: 3)
(4: 4)
(5: 5)

DECREASING ORDER:
(5: 5)
(4: 4)
(3: 3)
(2: 2)
(1: 1)

Documentation

See more documentation of library TreeTripper to learn more about it.

Authors

• @IliaSuponeff
• @RodionovMaxim05
• @Friend-zva, sometimes in commits his name is Vladimir Zaikin

License

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

(back to top)