dataspace

1
package dataspace
2

3
type node struct {
4
	hash    uint64   // хеш
5
	key     []byte   // ключ
6
	value   []byte   // значение
7
	element *element // элемент списка
8
	left    *node    // указатель на л. лист
9
	right   *node    // указатель на п. лист
10
	height  int      // ширина
11
}
12

13
// Метод ищет ноду по ключу.
14
func (n *node) search(h uint64) *node {
15
	if n == nil {
16
		return nil
17
	}
18
	switch {
19
	case h < n.hash:
20
		return n.left.search(h)
21
	case h == n.hash:
22
		return n
23
	case h > n.hash:
24
		return n.right.search(h)
25
	}
26
	return nil
27
}
28

29
// Метод записывает ноду в дерево.
30
func (n *node) add(h uint64, k, v []byte, e *element) *node {
31
	if n == nil {
32
		return &node{h, k, v, e, nil, nil, 1}
33
	}
34
	switch {
35
	case h < n.hash:
36
		n.left = n.left.add(h, k, v, e)
37
	case h == n.hash:
38
		n = &node{h, k, v, e, n.left, n.right, n.height}
39
	case h > n.hash:
40
		n.right = n.right.add(h, k, v, e)
41
	}
42
	return n.rebalance()
43
}
44

45
// Метод удаляет ноду из дерева.
46
func (n *node) remove(h uint64) *node {
47
	if n == nil {
48
		return nil
49
	}
50
	switch {
51
	case h < n.hash:
52
		n.left = n.left.remove(h)
53
	case h == n.hash:
54
		switch {
55
		case n.left != nil && n.right != nil:
56
			r := n.right.findMinimalNode()
57
			n = &node{
58
				r.hash,
59
				r.key,
60
				r.value,
61
				r.element,
62
				n.left,
63
				n.right.remove(r.hash),
64
				n.height,
65
			}
66
		case n.left != nil:
67
			n = n.left
68
		case n.right != nil:
69
			n = n.right
70
		default:
71
			return nil
72
		}
73
	case h > n.hash:
74
		n.right = n.right.remove(h)
75
	}
76
	return n.rebalance()
77
}
78

79
// Метод ищет минимальную ноду в ветке.
80
func (n *node) findMinimalNode() *node {
81
	if n.left == nil {
82
		return n
83
	}
84
	return n.left.findMinimalNode()
85
}
86

87
// Метод получает ширину ветви.
88
func (n *node) getHeight() int {
89
	if n == nil {
90
		return 0
91
	}
92
	return n.height
93
}
94

95
// Метод устанавливает ширину ноды.
96
func (n *node) setHeight() {
97
	n.height = 1 + max(n.left.getHeight(), n.right.getHeight())
98
}
99

100
// Метод поворачивает дерево влево.
101
func (n *node) rotateLeft() *node {
102
	r := n.right
103
	n.right = r.left
104
	r.left = n
105
	n.setHeight()
106
	r.setHeight()
107
	return r
108
}
109

110
// Метод поворачивает дерево вправо.
111
func (n *node) rotateRight() *node {
112
	l := n.left
113
	n.left = l.right
114
	l.right = n
115
	n.setHeight()
116
	l.setHeight()
117
	return l
118
}
119

120
// Метод балансирует дерево.
121
func (n *node) rebalance() *node {
122
	if n == nil {
123
		return nil
124
	}
125
	n.setHeight()
126
	switch n.left.getHeight() - n.right.getHeight() {
127
	case -2:
128
		if n.right.left.getHeight() > n.right.right.getHeight() {
129
			n.right = n.right.rotateRight()
130
		}
131
		return n.rotateLeft()
132
	case 2:
133
		if n.left.right.getHeight() > n.left.left.getHeight() {
134
			n.left = n.left.rotateLeft()
135
		}
136
		return n.rotateRight()
137
	}
138
	return n
139
}
140

141
// Функция считает количество веток дерева.
142
func countBranches(root *node) int64 {
143
	if root == nil {
144
		return 0
145
	}
146
	l := countBranches(root.left)
147
	r := countBranches(root.right)
148
	return max(l, r) + 1
149
}
150