由一个golang的B-Tree包展开-3(删除元素)

发表于 | 分类于 |

前面说了B-Tree数据结构等定义，并基于google的一个内存golang btree包源码分析，实现了B-Tree的初始化和插入，最后再来说说元素删除部分代码的理解吧。要看示例代码请点这里

关于b-tree删除元素的方法，有不少种， 我觉得google/btree使用的是比较巧妙的一种，但是因为库种把删除一个元素/删除最大元素/删除最小元素等放在一个函数种了，初看的时候会觉得有点儿绕，像我这种脑回路着急的人，愣是需要断点调试才搞明白，后来自己去实现删除方法时，干脆将删除特定元素和删除最大元素的代码分开了，虽然有重复代码，但是，个人感觉能更清楚地看清楚逻辑.
先说下大致思路：
对一个btree执行删除某个item的时候，有两种情况：
1.删除的item在非叶子节点中
2.删除的item在叶子节点中

对于情况1， item删除后，len(node.items) + 1 = len(node.children)被破坏，为了弥补这个空洞，可以进行如下操作，假设被删除的节为node.items[index],这里利用一个btree的神奇性质，所有小于items值的元素中最大的一个，一定在则从以node.children[index]为根节点的子树的最右侧叶子节点的最后一个，假设这个值为m, 则将m从叶子节点删除放到node.item[index]的位置，node节点就又平衡了。

这是不是看起来很美好，但是。。。， 这样做会带来另一个问题， 把m从叶子节点抠走以后，可能会造成叶子节点变空了，这样就有破坏了btree的平衡。所以，接下来我们就来考虑怎么能即能从叶子节点中抠出m填补node.item[index]又能保证叶子节点不被抠成空节点。

这里先搁置这个问题的解决，我们来聊聊情况2
对于要删除的item在叶子节点中的情况， 不用担心破坏非叶子节点len(node.items) +1 = len(node.children)这条规则，但是面临着另外一个问题，就是删除item之后，可能造成叶子节点变成空节点的情况。

说到这里，我们发现，情况1和情况2都面临着同样的问题， 只要能解决从叶子节点中抠元素造成叶子节点变为空的情况，删除item的问题也就搞定了。

在之前说插入新元素的时候，我们的困难是，担心item插入到某个叶子后，造成叶子节点被撑爆， 这里的问题相反，是担心删除后，造成叶子节点被饿死。与插入元素时候的预分裂对比起来，我们能大概想到的就是，对可能饿死的节点进行预添加。

来从几个示例说说预添加的操作方法和需要解决的问题：

非叶子节点元素删除的理想情况：

1
2
3
4
5
6
7
8
9
10
待删除元素: 5
原树：    
    |  2  |  5  |
   /       \     \    
  |1|      |3|4|  |6|7|

元素5位于非叶子节点， 且将左子树的最大值抠出后，未造成叶子节点变空，删除后树形态如下：
    |  2  |  4  |
   /       \     \    
  |1|      |3|   |6|7|

叶子节点元素删除的理想情况：

1
2
3
4
5
6
7
8
9
10
待删除元素: 6
原树：    
    |  2  |  5  |
   /       \     \    
  |1|      |3|4|  |6|7|

直接将目标元素抠出即可，删除后树形态：
    |  2  |  5  |
   /       \     \    
  |1|      |3|4|  |7|

但是。。。 理想情况总是可遇不可求的，比如下面

非叶子节点元素删除非理想情况1

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
待删除元素: 2
原树：    
    |  2  |  5  |
   /       \     \    
  |1|      |3|4|  |6|7|

按照我们之前的设想，删除元素2， 需要从其左子树找到最大值去填补空缺，
但是这里把1抠出来填补空缺后，叶子节点就空了，
那怎么办呢，从其他兄弟节点偷元素呗。

step1:从|2|5|这一层开始remvoe，定位到index = 0,
判断左子树节点元素可能不足，则从兄弟节点中比较充足的节点偷
(这里因为|1|没有左兄弟，只能从右边的兄弟偷)，调整之后的树长这样：

    |  3  |  5  |
   /       \     \       
  |1|2|     |4|   |6|7|

step2: 经过调整之后，继续从|3|5|这一层开始执行remove,定位到的还是index = 0, 
此时children[0]节点元素已经充足（得益于step1偷的操作），递归到|1|2|这一层，
继续进行remove操作，已经到叶子节点， 直接删除，于是最终到树就长这样：

    |  3  |  5  |
   /       \     \       
  |1|       |4|   |6|7|

非叶子节点元素删除非理想情况2

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
待删除元素: 4
原树：    
        |   4   |
        /         \ 
    | 2 |         | 6 |
   /     \       /     \   
 |1|     |3|   |5|      |7|8|9|

按照我们之前的设想，删除元素4， 需要从其左子树找到最大值去填补空缺，
但是这里把1抠出来填补空缺后，叶子节点就空了，
那怎么办呢，从其他兄弟节点偷元素呗。

step1:
从|4|这一层开始remvoe，定位到index = 0,
判断左子树节点元素可能不足，则从兄弟节点中比较充足的节点偷，
结果发现child[0]没有充足到兄弟可以偷，
只能走另外一条路:将child[0]和另外一个同样不充足的节点合并，形成新的子树，
调整之后的树长这样：

    |  2  |  4  |  6  |
   /      /    /       \     (合并之后，原本的根节点变为空， |2|4|6|变为新的根节点）
 |1|    |3|  |5|     |7|8|9|

step2: 
经过调整之后，继续从|2|4|5|这一层开始执行remove,定位到的还是index = 1, 
此时children[1]节点元素不充足，又因为 |3| 的左右兄弟节点都不充足，
又不得不进行一次合并（这里选择与左兄弟|1|进行合并，合并之后树变成这样：

     |  4  |  6  |
    /       \     \     
 |1|2|3|    |5|    |7|8|9|

 step3: 对step2调整之后的树继续从|4|6|这一层开始执行remvoe, 这一次定位到的index = 0，
 此时children[0]是|1|2|3|，已经充足了， 
 从这一层递归执行removeMax找到以|1|2|3|为根节点子树上的最大值，
 抠出来，替换到原本 |4|6|着一层4的位置， 就搞定， 最终树的形态：

      |  3  |  6  |
    /        \     \     
 |1|2|       |5|    |7|8|9|

实现代码摘要：

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
func (t *BTree) Delete(item Item) Item {
	return t.root.remove(item, t.MinCap())
}

func (n *node) remove(t Item, minCap int) Item {

	i, found := n.items.find(t)

	// 如果node节点的子树i中items小于等于最小键个数，则先对其进行一次调整处理, 保证到叶子节点时其可以直接删除

	// 如果子树i需要调整，则调整节点后，重新进行remove操作
	if len(n.children) != 0 && len(n.children[i].items) <= minCap {
		return n.growChildAndRemove(i, t, minCap)
	}

	//
	if found {
		if len(n.children) == 0 {
			// 如果查找到元素，且元素在叶子节点，则直接删除并返回
			// 因为在进入叶子节点之前，已经通过growChildAndRemove做了扩容处理，保证到达叶子是，一定可以直接删除而不破坏结构
			return n.items.removeAt(i)
		} else {
			// 从n.childrend[i]为根的子树依次向下，最终删除一个最大值，替换n.items[i-1]原来的值

			// 如果查找到要删除的元素不在叶子节点上， 则删除之，并从children[i]为根的子树上提取最大元素放入要删除的位置
			out := n.items[i]
			n.items[i] = n.children[i].removeMax(minCap)
			return out
		}
	} else {
		if len(n.children) == 0 {
			return nil
		} else {
			child := n.children[i]
			return child.remove(t, minCap)
		}

	}
}

func (parent *node) growChildAndRemove(index int, t Item, minCap int) Item {

	// 从左兄弟子树偷一个尾部item放入parent item[i-1],然后源parent item[i-1]下移插入到parent.children[i]的头部
	if index > 0 && len(parent.children[index-1].items) > minCap {

		stoleNode := parent.children[index-1]
		stoleNodeIndex := len(parent.children[index-1].items) - 1
		stoleItem := stoleNode.items.removeAt(stoleNodeIndex)
		parent.children[index].items.insertAt(0, parent.items[index-1])
		parent.items[index-1] = stoleItem
		if len(stoleNode.children) != 0 {
			lastIndex := len(stoleNode.children) - 1
			nodeLastChildren := stoleNode.children.removeAt(lastIndex)
			parent.children[index].children.insertAt(0, nodeLastChildren)
		}

		return parent.remove(t, minCap)

	}

	// 从右子树偷
	if index < len(parent.children)-1 && len(parent.children[index+1].items) > minCap {

		stoleNode := parent.children[index+1]
		parent.children[index].items = append(parent.children[index].items, parent.items[index])
		stoleItem := stoleNode.items.removeAt(0)
		parent.items[index] = stoleItem

		if len(stoleNode.children) != 0 {
			nodeFirstChildren := stoleNode.children.removeAt(0)
			parent.children[index].children = append(parent.children[index].children, nodeFirstChildren)
		}

		return parent.remove(t, minCap)

	}

	//无可偷兄弟节点，需要做一次兄弟合并
	if index > 0 {
		// 非最左节点， 则合并左兄弟
		n := &node{}
		n.items = append(n.items, parent.children[index-1].items...)
		n.items = append(n.items, parent.items[index-1])
		n.items = append(n.items, parent.children[index].items...)

		if len(parent.children[index-1].children) != 0 {
			n.children = append(n.children, parent.children[index-1].children...)
			n.children = append(n.children, parent.children[index].children...)
		}

		// 处理根节点被删空的情况
		if len(parent.items) == 1 {
			*parent = *n
		} else {
			parent.items.removeAt(index - 1)
			parent.children.removeAt(index - 1)
			parent.children[index-1] = n //合并后index前移一位
		}
		return parent.remove(t, minCap)
	}

	if index+1 < len(parent.children) {
		// 最左边不可偷节点，合并右侧兄弟节点
		n := &node{}
		n.items = append(n.items, parent.children[index].items...)
		n.items = append(n.items, parent.items[index])
		n.items = append(n.items, parent.children[index+1].items...)

		if len(parent.children[index].children) != 0 {
			n.children = append(n.children, parent.children[index].children...)
			n.children = append(n.children, parent.children[index+1].children...)
		}

		if len(parent.items) == 1 {
			*parent = *n
		} else {
			parent.items.removeAt(index)
			parent.children.removeAt(index + 1)
			parent.children[index] = n
		}

		return parent.remove(t, minCap)
	}

	return nil

}

func (parent *node) growChildAndRemoveMax(lastChildIndex int, minCap int) Item {

	// 从左兄弟子树偷一个尾部item放入parent item[i-1],然后源parent item[i-1]下移插入到parent.children[i]的头部
	if len(parent.children[lastChildIndex-1].items) > minCap {
		lastItemIndex := lastChildIndex - 1

		stoleNode := parent.children[lastChildIndex-1]
		stoleItemIndex := len(stoleNode.items) - 1
		stoleItem := stoleNode.items.removeAt(stoleItemIndex)
		downItem := parent.items[lastItemIndex]
		parent.children[lastChildIndex].items.insertAt(0, downItem)
		parent.items[lastItemIndex] = stoleItem
		if len(stoleNode.children) != 0 {
			lastIndex := len(stoleNode.children) - 1
			nodeLastChildren := stoleNode.children.removeAt(lastIndex)
			parent.children[lastChildIndex].children.insertAt(0, nodeLastChildren)
		}
	} else {
		// combing subling

		lastItemIndex := lastChildIndex - 1
		n := &node{}
		n.items = append(n.items, parent.children[lastChildIndex-1].items...)
		n.items = append(n.items, parent.items[lastItemIndex])
		n.items = append(n.items, parent.children[lastChildIndex].items...)

		if len(parent.children[lastChildIndex-1].children) != 0 {
			n.children = append(n.children, parent.children[lastChildIndex-1].children...)
			n.children = append(n.children, parent.children[lastChildIndex].children...)
		}

		if len(parent.items) == 1 {
			*parent = *n //注意这里要对对指针指向内容重新赋值
		} else {
			parent.items.removeAt(lastItemIndex)
			parent.children.removeAt(lastChildIndex)
			parent.children[lastChildIndex-1] = n
		}

	}

	return parent.removeMax(minCap)
}

func (n *node) removeMax(minCap int) Item {
	lastItemIndex := len(n.items) - 1
	if len(n.children) == 0 {
		return n.items.removeAt(lastItemIndex)
	} else if len(n.children[lastItemIndex+1].items) <= minCap {
		lastChildIndex := lastItemIndex + 1
		return n.growChildAndRemoveMax(lastChildIndex, minCap) //
	}

	lastChildIndex := lastItemIndex + 1
	lastChildNode := n.children[lastChildIndex]
	return lastChildNode.removeMax(minCap)
}

~ 全剧终 ～