Trees Implementation

Posted on | In , |

Binary Search Tree

Average Case Worst Case
Space O(n) O(n)
Insert O(log(n)) O(n)
Delete O(log(n)) O(n)
Search O(log(n)) O(n)

Trees Traversal:

  • In-order Traversal: left -> root -> right
  • Pre-order Traversal: root -> left -> right
  • Post-order Traversal: left -> right -> root
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
126
127
128
129
class Node(object):

    def __init__(self, data):
        self.data = data
        self.leftChild = None
        self.rightChild = None


class BinarySearchTree(object):

    def __init__(self):
        self.root = None

    def insert(self, data):

        if not self.root:
            self.root = Node(data)
        else:
            self.insertNode(data, self.root)

    # O(logn) if the tree is balanced. If it is not, it can be reduced to O(n)
    def insertNode(self, data, node):

        if data < node.data:
            if node.leftChild:
                self.insertNode(data, node.leftChild)
            else:
                node.leftChild = Node(data)

        else:
            if node.rightChild:
                self.insertNode(data, node.rightChild)
            else:
                node.rightChild = Node(data)

    def remove(self, data):
        if self.root:
            self.root = self.removeNode(data, self.root)

    def removeNode(self, data, node):

        if not node:
            return node
        if data < node.data:
            node.leftChild = self.removeNode(data, node.leftChild)
        elif data > node.data:
            node.rightChild = self.removeNode(data, node.rightChild)
        else:
            if not node.leftChild and not node.rightChild:
                print('Removing a leaf node')
                del node
                return None

            elif not node.leftChild:
                print('Removing a node with single right child...')
                tempNode = node.rightChild
                del node
                return tempNode
            elif not node.rightChild:
                print('Removing a node with single left child...')
                tempNode = node.leftChild
                del node
                return tempNode

            print('Removing node with two children...')
            tempNode = self.getProdecessor(node.leftChild)
            node.data = tempNode.data
            node.leftChild = self.removeNode(tempNode.data, node.leftChild)

        return node

    def getProdecessor(self, node):
        if node.rightChild:
            return self.getProdecessor(node.rightChild)

        return node

    def getMinValue(self):

        if self.root:
            return self.getMin(self.root)

    def getMin(self, node):

        if node.leftChild:
            return self.getMin(node.leftChild)

        return node.data

    def getMaxValue(self):

        if self.root:
            return self.getMax(self.root)

    def getMax(self, node):

        if node.rightChild:
            return self.getMax(node.rightChild)

        return node.data

    def traverse(self):

        if self.root:
            self.traverseInOrder(self.root)

    def traverseInOrder(self, node):

        if node.leftChild:
            self.traverseInOrder(node.leftChild)

        print(node.data)

        if node.rightChild:
            self.traverseInOrder(node.rightChild)


bst = BinarySearchTree()

bst.insert('a')
bst.insert('s')
bst.insert('b')
bst.insert('t')

# print(bst.getMaxValue())
# print(bst.getMinValue())
# bst.remove('s')
bst.remove('a')
bst.traverse()

AVL Tree

AVL trees and red-black trees are guaranteed to be balanced, so O(log(n)) is guaranteed.

Average Case Worst Case
Space O(n) O(n)
Insert O(log(n)) O(log(n))
Delete O(log(n)) O(log(n))
Search O(log(n)) O(log(n))

Applications

  • Databases when deletion or insertion are not so frequent, but have to make a lot of look-ups.
  • Red-Black trees are a little bit more popular, as for AVL we have to make several rotations, a little bit slower.
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
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
class Node(object):

    def __init__(self, data):
        self.data = data
        self.height = 0
        self.leftChild = None
        self.rightChild = None


class AVL(object):

    def __init__(self):
        self.root = None

    def insert(self, data):
        self.root = self.insertNode(data, self.root)

    def insertNode(self, data, node):

        if not node:
            return Node(data)

        if data < node.data:
            node.leftChild = self.insertNode(data, node.leftChild)
        else:
            node.rightChild = self.insertNode(data, node.rightChild)

        node.height = max(self.calcHeight(node.leftChild), self.calcHeight(node.rightChild)) + 1

        return self.settleViolation(data, node)

    def settleViolation(self, data, node):
        # four different cases
        balance = self.calcBalance(node)

        if balance > 1 and data < node.leftChild.data:
            print('Left Left heavy situation...')
            return self.rotateRight(node)

        elif balance < - 1 and data > node.rightChild.data:
            print('Right right heavy situation...')
            return self.rotateLeft(node)

        # left and right rotation
        elif balance > 1 and data > node.leftChild.data:
            print('Left right heavy situation...')
            node.leftChild = self.rotateLeft(node.leftChild)
            return self.rotateRight(node)

        # right and left rotation
        elif balance < -1 and data < node.rightChild.data:
            print('Right left heavy situation...')
            node.rightChild = self.rotateRight(node.rightChild)
            return self.rotateLeft(node)

        return node

    def calcHeight(self, node):

        if not node:
            return -1

        return node.height

    # if it returns value > 1, it means it is a left heavy tree --> right rotation
    # if it returns value < -1, it means it is a right heavy tree --> left rotation
    def calcBalance(self, node):

        if not node:
            return 0

        return self.calcHeight(node.leftChild) - self.calcHeight(node.rightChild)

    def traverse(self):
        if self.root:
            self.traverseInOrder(self.root)

    def traverseInOrder(self, node):

        if node.leftChild:
            self.traverseInOrder(node.leftChild)

        print(node.data)

        if node.rightChild:
            self.traverseInOrder(node.rightChild)

    def rotateRight(self, node):

        print('Rotating to the right on node', node.data)

        temLeftChild = node.leftChild
        t = temLeftChild.rightChild

        temLeftChild.rightChild = node
        node.leftChild = t

        node.height = max(self.calcHeight(node.leftChild), self.calcHeight(node.rightChild)) + 1
        temLeftChild.height = max(self.calcHeight(temLeftChild.leftChild), self.calcHeight(temLeftChild.rightChild)) + 1

        return temLeftChild

    def rotateLeft(self, node):

        print('Rotating to the left on node', node.data)

        temRightChild = node.rightChild
        t = temRightChild.leftChild

        temRightChild.leftChild = node
        node.rightChild = t

        node.height = max(self.calcHeight(node.leftChild), self.calcHeight(node.rightChild)) + 1
        temRightChild.height = max(self.calcHeight(temRightChild.leftChild), self.calcHeight(temRightChild.rightChild)) + 1

        return temRightChild

    def remove(self, data):
        if self.root:
            self.root = self.removeNode(data, self.root)

    def removeNode(self, data, node):

        if not node:
            return node
        elif data < node.data:
            node.leftChild = self.removeNode(data, node.leftChild)
        elif data > node.data:
            node.rightChild = self.removeNode(data, node.rightChild)
        else:
            if not node.leftChild and not node.rightChild:
                print('Removing a leaf node')
                del node
                return None

            elif not node.leftChild:
                print('Removing a node with right child...')
                tempNode = node.rightChild
                del node
                return tempNode
            elif not node.rightChild:
                print('Removing a node with left child...')
                tempNode = node.leftChild
                del node
                return tempNode

            print('Removing node with two children...')
            tempNode = self.getProdecessor(node.leftChild)
            node.data = tempNode.data
            node.leftChild = self.removeNode(tempNode.data, node.leftChild)

        if not node:
            return node  # if the tree has only a single node

        node.height = max(self.calcHeight(node.leftChild), self.calcHeight(node.rightChild)) + 1

        balance = self.calcBalance(node)

        # doubly left heavy situation
        if balance > 1 and self.calcBalance(node.leftChild) >= 0:
            return self.rotateRight(node)

        # doubly right heavy situation
        elif balance < -1 and self.calcBalance(node.rightChild) <= 0:
            return self.rotateLeft(node)

        # left right case
        elif balance > 1 and self.calcBalance(node.leftChild) <= 0:
            node.leftChild = self.rotateLeft(node.leftChild)
            return self.rotateRight(node)

        # right left case
        elif balance < -1 and self.calcBalance(node.rightChild) > 0:
            node.rightChild = self.rotateRight(node.rightChild)
            return self.rotateLeft(node)

        return node


avl = AVL()

avl.insert(10)
avl.insert(20)
avl.insert(5)
avl.insert(4)
avl.insert(15)

avl.remove(5)
avl.remove(4)

avl.traverse()

Red-Black Tree

Average Case Worst Case
Space O(n) O(n)
Insert O(log(n)) O(log(n))
Delete O(log(n)) O(log(n))
Search O(log(n)) O(log(n))

Red-Black tree properties:

  • Each node is either red or black
  • The root node is always black
  • Every red most have two black child nodes and no other children -> it must have a black parent
  • Every path from a given node to any of its descendant Null nodes contains the same number of black nodes.

Tries & Ternary Search Tree

Hash Table VS Tries

  • We can replace hash tables with tries, tries are more efficient for search misses
    • Hash table the key is going to be converted into an index with the help of the hash function
    • Tries, we consider every single character of the key, but we return right when there is a mismatch.
  • For tries there is no collision.
  • Tries can provide string, so alphabetical ordering of the entries by keys. Hash table does not.
  • No hash function needed for tries.

Applications

  • Predictive text, auto-complete feature
  • Spell checking
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
class Node(object):

    def __init__(self, character):
        self.character = character
        self.leftNode = None
        self.midNode = None
        self.rightNode = None
        self.value = 0


class TST(object):

    def __init__(self):
        self.rootNode = None

    def put(self, key, value):
        self.rootNode = self.putItem(self.rootNode, key, value, 0)

    def putItem(self, node, key, value, index):

        c = key[index]

        if node is None:
            node = Node(c)

        if c < node.character:
            node.leftNode = self.putItem(node.leftNode, key, value, index)
        elif c > node.character:
            node.rightNode = self.putItem(node.rightNode, key, value, index)
        elif index < len(key) - 1:
            node.midNode = self.putItem(node.midNode, key, value, index + 1)
        else:
            node.value = value

        return node

    def get(self, key):

        node = self.getItem(self.rootNode, key, 0)

        if node is None:
            return -1  # means given key is not present in the dictionary

        return node.value

    def getItem(self, node, key, index):

        if node is None:
            return None

        c = key[index]

        if c < node.character:
            return self.getItem(node.leftNode, key, index)
        elif c > node.character:
            return self.getItem(node.rightNode, key, index)
        elif index < len(key) - 1:
            return self.getItem(node.midNode, key, index + 1)
        else:
            return node


if __name__ == "__main__":
    tst = TST()

    tst.put('apple', 100)
    tst.put('orange', 200)

    print(tst.get('apple'))
0%