GameTree-Python/BST.py at master · alissondiegodnz/GameTree-Python · 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
class NodeTree:
  def __init__(self, key):
    self.key = key
    self.right = None
    self.left = None

class Bst:
  def __init__(self, root = None):
    self.root = root
    self.height = 0


  def insert(self, key, cont = 0 ):
    tree = self.root
    if self.root is None:
        self.root = NodeTree(key)
        self.root.right = Bst()
        self.root.left = Bst()

        return(cont)

    elif key < tree.key:
      return self.root.left.insert(key, cont +1 )

    else:
      return self.root.right.insert(key, cont +1)


  def calc_height(self, recursion=True):
    if not self.root is None:
        if recursion:
            if self.root.left != None:
                self.root.left.calc_height()
            if self.root.right != None:
                self.root.right.calc_height()

        self.height = max(self.root.left.height, self.root.right.height) + 1
    else:
        self.height = -1


  def search(self, key):
    cont = 0
    if self.root.key == key:
      return 0
    else:
      pointer = self.root

      while pointer != None:

        if pointer.key == key:
          return cont
        elif pointer.key > key:
          pointer = pointer.left.root
          cont += 1
        elif pointer.key < key:
          pointer = pointer.right.root
          cont += 1
      return (-1)


  def search2(self, key):
    cont = 0
    cont2 = 0

    if self.root.key == key:
      return 0
    else:
      pointer = self.root

      while pointer != None:

        if pointer.key == key:
          cont2 = cont

        if pointer.key > key:
          pointer = pointer.left.root
          cont += 1
        elif pointer.key <= key:
          pointer = pointer.right.root
          cont += 1

      if cont == 0:
        return (-1)
      return(cont2)

  def sucessor(self, root):
        root = root.right.root
        if root != None:
            while root.left != None:
                if root.left.root is None:
                    return root
                else:
                    root = root.left.root
        return root


  def delete (self, key):

    if self.root is not None:
        if self.root.key == key:
            if (self.root.left.root is None) and (self.root.right.root is None):
                self.root = None
            elif self.root.left.root is None:

                self.root = self.root.right.root
            elif self.root.right.root is None:

                self.root = self.root.left.root
            else:
                sucessor = self.sucessor(self.root)
                if sucessor is not None:
                    self.root.key = sucessor.key
                    self.root.right.delete(sucessor.key)
            return
        elif key < self.root.key:
            self.root.left.delete(key)
        elif key > self.root.key:
            self.root.right.delete(key)
    else:
      pass