Purity-Project/src/main/scala/dataStructures/BinaryTree.scala at master · ditekunov/Purity-Project · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
package dataStructures

import dataStructures.miscellaneous.DataStructureException
import dataStructures.miscellaneous.DataStructuresExceptionMessages.EmptyLeafException
import dataStructures.miscellaneous.DataStructuresExceptionMessages.EmptyTreeException
import utils.InputException

import scala.annotation.tailrec

/**
  * Contains functional realisation of a standard binary tree.
  *
  * https://en.wikipedia.org/wiki/Linked_list
  *
  * Purity project by Daniil Tekunov.
  */
abstract sealed class BinaryTree[+A] {

  /**
    * Value of a node
    */
  def value: Int

  /**
    * Left branch
    */
  def left: BinaryTree[A]

  /**
    * Right branch
    */
  def right: BinaryTree[A]

  /**
    * Size of a tree
    */
  def size: Int

  /**
    * Whether the tree is empty
    */
  def isEmpty: Boolean

  /**
    * Checks, whether the tree is a valid binary tree
    */
  def isValid: Boolean = {
    if (isEmpty) true
    else if (left.isEmpty && right.isEmpty) true
    else if (left.isEmpty) right.value >= value && right.isValid
    else if (right.isEmpty) left.value <= value && left.isValid
    else (left.value <= value && left.isValid) && right.value >= value && right.isValid
  }
  /**
    * Adds an element to a tree
    */
  def addElement(element: Int): BinaryTree[A] = {
    if (isEmpty) BinaryTree.make(element)
    else if (element < value) BinaryTree.make(value, left.addElement(element), right)
    else if (element > value) BinaryTree.make(value, left, right.addElement(element))
    else this
  }

  /**
    * Removes an element from a tree
    */
  def removeElement(element: Int): BinaryTree[A] = {
    if (isEmpty) throw new InputException(EmptyTreeException)
    else if (element < value) BinaryTree.make(value, left.removeElement(element), right)
    else if (element > value) BinaryTree.make(value, left, right.removeElement(element))
    else {
      if (left.isEmpty && right.isEmpty) BinaryTree.empty
      else if (left.isEmpty) right
      else if (right.isEmpty) left
      else {
        val found = right.min
        BinaryTree.make(found, left, right.removeElement(found))
      }
    }
  }

  /**
    * Finds a minimum value in a tree
    */
  def min: Int = {
    @tailrec
    def find(tree: BinaryTree[A], cur: Int): Int =
      if (tree.isEmpty) cur
      else find(tree.left, tree.value)

    if (isEmpty) throw new InputException(EmptyTreeException)
    else find(left, value)
  }


}

/**
  * Basic object to describe a leaf
  */
case object Leaf extends BinaryTree[Nothing] {
  def value = throw new DataStructureException(EmptyLeafException)
  def left = throw new DataStructureException(EmptyLeafException)
  def right = throw new DataStructureException(EmptyLeafException)
  def size = 0
  def isEmpty = true
}

/**
  * Basic case class, to describe a branch
  */
case class Branch[A](value: Int,
                  left: BinaryTree[A],
                  right: BinaryTree[A],
                  size: Int) extends BinaryTree[A] {
  def isEmpty: Boolean = false
}

object BinaryTree {

  def empty[A]: BinaryTree[A] = Leaf

  def make[A](element: Int, left: BinaryTree[A] = Leaf, right: BinaryTree[A] = Leaf): BinaryTree[A] =
    Branch(element, left, right, left.size + right.size + 1)
}