image frame

XiShng Blog

既往拼搏，守护一生所爱

平衡二叉树查找算法

算法 / 查找算法 / 树查找

平衡二叉树

树是一种计算机数据结构中非常常用的一种结构，其中就包含了：平衡二叉树，这种树是一种特殊的二叉查找树(二叉查找树也就是，右孩子大于其父结点，左孩子小于其父结点的树)，但是简单的二叉查找树存在的问题就是不平衡，最差的查找效率为O(n)，故就有人发明了一种平衡的额二叉查找树。

特点

平衡二叉树是一种二叉查找树
每个结点的左子树的高度减去右子树的高度的绝对值不超过1
空树和左右子树都是平衡二叉树
相比红黑树，平衡二叉树比较适用于没有删除的情况

平衡因子

平衡二叉树是在二叉查查找树的基础上进行构建了，为了维持平衡二叉树的平衡，那么就需要一种机制来判断平衡二叉树是否是平衡的。这种机制就叫做平衡因子。

平衡二叉树的每个结点都会维持一个值，这个值就是平衡因子，这个平衡因子就是这个结点的左子树的高度减去右子树的高度得到的值。如果这个平衡因子的值的绝对值大于1了，说明这个树就不平衡了，那么就需要调整树的结构了。

我们可以从如上这个这个图中看的到：每个结点都维持了一个值，比如左边的AVL 树根结点的值为-1，这个-1是怎么来的呢，就是结点3的左子树的高度为 2, 右子树的高度为 3, 左子树的高度减去右子树的高度就得到这个结点的平衡因子。

如果某个结点的平衡因子的绝对值大于了 1 ，那么就说明这个平衡二叉树不平衡了，就需要调整平衡二叉树的结构。

平衡因子

旋转

由于AVL树需要做到平衡，所以每次插入叶子节点，如果发现不平衡，都需要进行旋转以保持平衡。

下面是旋转图例，可以参考的看下：

旋转

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
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
package main

import "fmt"

type AVL struct {
	value  int  //值
	height int  //深度
	left   *AVL //左子树
	right  *AVL //右子树
}

// Search 查找元素
func (t *AVL) Search(value int) bool {
	if t == nil {
		return false
	}

	if value < t.value {
		return t.left.Search(value)
	} else if value > t.value {
		return t.right.Search(value)
	} else {
		return true
	}
}

// Insert 添加元素
func (t *AVL) Insert(value int) *AVL {
	if t == nil {
		newNode := AVL{value, 1, nil, nil}
		return &newNode
	}
	if value < t.value {
		t.left = t.left.Insert(value)
		t = t.adjust()
	} else if value > t.value {
		t.right = t.right.Insert(value)
		t = t.adjust()
	} else {
		fmt.Println("the node exit")
	}
	t.height = max(t.left.getHeight(), t.right.getHeight()) + 1
	return t
}

/*
Delete
	删除元素
		*1、如果被删除结点只有一个子结点，就直接将A的子结点连至A的父结点上，并将A删除
		*2、如果被删除结点有两个子结点，将该结点右子数内的最小结点取代A。
		*3、查看是否平衡, 如果不平衡，就调整
*/
func (t *AVL) Delete(value int) *AVL {
	if t == nil {
		return t
	}
	compare := value - t.value
	if compare < 0 {
		t.left = t.left.Delete(value)
	} else if compare > 0 {
		t.right = t.right.Delete(value)
	} else { //找到结点,删除结点（）
		if t.left != nil && t.right != nil {
			t.value = t.right.getMin()
			t.right = t.right.Delete(t.value)
		} else if t.left != nil {
			t = t.left
		} else { //只有一个右孩子或没孩子
			t = t.right
		}
	}
	if t != nil {
		t.height = max(t.left.getHeight(), t.right.getHeight()) + 1
		t = t.adjust()
	}
	return t
}

// adjust 判断是否需要旋转
func (t *AVL) adjust() *AVL {
	if t.right.getHeight()-t.left.getHeight() == 2 {
		if t.right.right.getHeight() > t.right.left.getHeight() {
			t = t.leftRotate()
		} else {
			t = t.rightThenLeftRotate()
		}
	} else if t.left.getHeight()-t.right.getHeight() == 2 {
		if t.left.left.getHeight() > t.left.right.getHeight() {
			t = t.rightRotate()
		} else {
			t = t.LeftThenRightRotate()
		}
	}
	return t
}

// leftRotate 左旋
func (t *AVL) leftRotate() *AVL {
	headNode := t.right
	t.right = headNode.left
	headNode.left = t

	//更新结点高度
	t.height = max(t.left.getHeight(), t.right.getHeight()) + 1
	headNode.height = max(headNode.left.getHeight(), headNode.right.getHeight()) + 1
	return headNode
}

// rightRotate 右旋
func (t *AVL) rightRotate() *AVL {
	headNode := t.left
	t.left = headNode.right
	headNode.right = t

	//更新结点高度
	t.height = max(t.left.getHeight(), t.right.getHeight()) + 1
	headNode.height = max(headNode.left.getHeight(), headNode.right.getHeight()) + 1
	return headNode
}

// rightThenLeftRotate 右旋转,之后左旋转
func (t *AVL) rightThenLeftRotate() *AVL {
	//以失衡点右结点先右旋转
	sonHeadNode := t.right.rightRotate()
	t.right = sonHeadNode

	//再以失衡点左旋转
	return t.leftRotate()
}

// LeftThenRightRotate 左旋转,之后右旋转
func (t *AVL) LeftThenRightRotate() *AVL {
	//以失衡点左结点先左旋转
	sonHeadNode := t.left.leftRotate()
	t.left = sonHeadNode
	//再以失衡点左旋转
	return t.rightRotate()
}

// getAll 按顺序获得树中元素
func (t *AVL) getAll() []int {
	values := []int{}
	return addValues(values, t)
}

// addValues 将一个节点加入切片中
func addValues(values []int, t *AVL) []int {
	if t != nil {
		values = addValues(values, t.left)
		values = append(values, t.value)
		fmt.Println(t.value, t.height)
		values = addValues(values, t.right)
	}
	return values
}

// getMin 查找子树最小值
func (t *AVL) getMin() int {
	if t == nil {
		return -1
	}
	if t.left == nil {
		return t.value
	} else {
		return t.left.getMin()
	}
}

// getMax 查找子树最大值
func (t *AVL) getMax() int {
	if t == nil {
		return -1
	}
	if t.right == nil {
		return t.value
	} else {
		return t.right.getMax()
	}
}

// getMinNode 查找最小结点
func (t *AVL) getMinNode() *AVL {
	if t == nil {
		return nil
	} else {
		for t.left != nil {
			t = t.left
		}
	}
	return t
}

// getMaxNode 查找最大结点
func (t *AVL) getMaxNode() *AVL {
	if t == nil {
		return nil
	} else {
		for t.right != nil {
			t = t.right
		}
	}
	return t
}

// getHeight 得到树高
func (t *AVL) getHeight() int {
	if t == nil {
		return 0
	}
	return t.height
}

// max 最深节点高度
func max(a int, b int) int {
	if a > b {
		return a
	} else {
		return b
	}
}

func main() {
	bsTree := AVL{100, 1, nil, nil}
	newTree := bsTree.Insert(60)
	newTree = bsTree.Insert(120)
	newTree = bsTree.Insert(110)
	newTree = bsTree.Insert(130)
	newTree = bsTree.Insert(105)
	fmt.Println(newTree.getAll())

	newTree.Delete(110)
	fmt.Println(newTree.getAll())
}

二叉树查找

算法 / 查找算法 / 树查找

二叉树查找

二叉查找树是先对待查找的数据进行生成树，确保树的左分支的值小于右分支的值，然后再用所查数据和每个节点的父节点比较大小，查找最适合的范围。 这个算法的查找效率很高，但是如果使用这种查找方法要首先创建树。

适用场景：

前面的几种查找算法因为都是适用于有序集，在插入和删除操作上就需要耗费大量的时间。有没有一种既可以使得插入和删除效率不错，又可以比较高效的实现查找的算法。

二叉查找树（BinarySearch Tree，也叫二叉搜索树，或称二叉排序树Binary Sort Tree）或者是一棵空树，或者是具有下列性质的二叉树：

1）若任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；

2）若任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；

3）任意节点的左、右子树也分别为二叉查找树。

  • 二叉查找树性质：对二叉查找树进行中序遍历，即可得到有序的数列。

如代码：

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
/**
基本思路：先把数组构造出一颗二叉树的样纸，然后查找的时候在从root往下对比
 */
func BSTsearch(arr []int, key int) int{
	// 先在内存中构造 二叉树
	tree := new(Tree)
	for i, v := range arr {
		Insert(tree, v, i)
	}
	// 开始二叉树查找目标key
	return searchKey(tree.Root, key)
}

// 节点结构
type Node struct {
	Value, Index int  // 元素的值和在数组中的位置
	Left, Right *Node
}

// 树结构
type Tree struct {
	Root *Node
}

// 把数组的的元素插入树中
func Insert(tree *Tree, value, index int){
	if nil == tree.Root {
		tree.Root = newNode(value, index)
	}else {
		InsertNode(tree.Root, newNode(value, index))
	}
}

// 把新增的节点插入树的对应位置
func InsertNode(root, childNode *Node) {
	// 否则，先和根的值对比
	if childNode.Value <= root.Value {
		// 如果小于等于跟的值，则插入到左子树
		if  nil == root.Left {
			root.Left = childNode
		}else {
			InsertNode(root.Left, childNode)
		}
	}else{
		// 否则，插入到右子树
		if nil == root.Right {
			root.Right = childNode
		}else {
			InsertNode(root.Right, childNode)
		}
	}
}

func newNode(value, index int) *Node {
	return &Node{
		Value: value,
		Index: index,
	}
}
// 在构建好的二叉树中，从root开始往下查找对应的key 返回其在数组中的位置
func searchKey(root *Node, key int) int {
	if nil == root {
		return -1
	}
	if  key == root.Value {
		return root.Index
	}else if key < root.Value {
		// 往左子树查找
		return searchKey(root.Left, key)
	}else {
		// 往右子树查找
		return searchKey(root.Right, key)
	}
}

红黑树查找

算法 / 查找算法 / 树查找

红黑树查找

红黑树查找：

它一种特殊的二叉查找树。红黑树的每个节点上都有存储位表示节点的颜色，可以是红(Red)或黑(Black)。红黑树是2-3树的一种简单高效的实现。

红黑树的特性:

（1）每个节点或者是黑色，或者是红色。（2）根节点是黑色。（3）每个叶子节点（NIL）是黑色。 [注意：这里叶子节点，是指为空(NIL或NULL)的叶子节点！]（4）如果一个节点是红色的，则它的子节点必须是黑色的。（5）从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。

如图所示:

红黑树的特性

基本思路: 红黑树的基本操作是添加、删除。在对红黑树进行添加或删除之后，都会用到旋转方法。为什么呢？道理很简单，添加或删除红黑树中的节点之后，红黑树就发生了变化，可能不满足红黑树的5条性质，也就不再是一颗红黑树了，而是一颗普通的树。而通过旋转，可以使这颗树重新成为红黑树。简单点说，旋转的目的是让树保持红黑树的特性。

旋转包括两种：左旋 和 右旋。

左旋示意图：

左旋示意图

完整左旋示意图:

完整左旋示意图

右旋示意图：

右旋示意图

完整右旋示意图：

完整右旋示意图

无论是左旋还是右旋，被旋转的树，在旋转前是二叉查找树，并且旋转之后仍然是一颗二叉查找树。(二叉查找树：左子 < 根 < 右子)

二叉查找树：左子 < 根 < 右子

  • 可见：
    • 左旋中的“左”，意味着“被旋转的节点将变成一个左节点”；
    • 右旋中的“右”，意味着“被旋转的节点将变成一个右节点”。

节点的插入：

将红黑树当作一颗二叉查找树，将节点插入将节点着色为红色通过旋转和重新着色等方法来修正该树，使之重新成为一颗红黑树。

为什么着色成红色，而不是黑色呢？

在回答之前，我们需要重新温习一下红黑树的特性：

(1) 每个节点或者是黑色，或者是红色。
(2) 根节点是黑色。
(3) 每个叶子节点是黑色。 [注意：这里叶子节点，是指为空的叶子节点！]
(4) 如果一个节点是红色的，则它的子节点必须是黑色的。
(5) 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。

将插入的节点着色为红色，不会违背”特性(5)”！少违背一条特性，就意味着我们需要处理的情况越少。接下来，就要努力的让这棵树满足其它性质即可；满足了的话，它就又是一颗红黑树了。

将插入节点着色为”红色”之后，不会违背”特性(5)”。那它到底会违背哪些特性呢？

对于”特性(1)”，显然不会违背了。因为我们已经将它涂成红色了。
 对于”特性(2)”，显然也不会违背。在第一步中，我们是将红黑树当作二叉查找树，然后执行的插入操作。而根据二叉查找数的特点，插入操作不会改变根节点。所以，根节点仍然是黑色。
对于”特性(3)”，显然不会违背了。这里的叶子节点是指的空叶子节点，插入非空节点并不会对它们造成影响。
对于”特性(4)”，是有可能违背的！

**那接下来，想办法使之”满足特性(4)”**，就可以将树重新构造成红黑树了。
 
 代码如下：

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
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
const (
	RED   = true
	BLACK = false
)

// 节点
type RBNode struct {
	Color               bool // true == 红  false == 黑
	Parent, Left, Right *RBNode
	Value, Index        int
}

type RBTree struct {
	Root *RBNode
}

/*
* 对红黑树的节点(x)进行左旋转
*
* 左旋示意图(对节点 x 进行左旋)：
*      px                              px
*     /                               /
*    x                               y
*   /  \\      --(左旋)-.           / \\                #
*  lx   y                          x  ry
*     /   \\                       /  \\
*    ly   ry                     lx  ly
*
*
*/
func (t *RBTree) leftSpin(node *RBNode) {
	// 先提出自己的 右子
	y := node.Right

	// 自己的新右子 是前右子的左子
	node.Right = y.Left

	if nil != y.Left {
		y.Left.Parent = node
	}

	// 你以前的爹，就是我现在的爹
	y.Parent = node.Parent

	// 如果被旋转的节点是 之前树的根
	// 那么，新的跟就是 y 节点
	if nil == node.Parent {
		t.Root = y
	} else { // 被旋转的是普通节点时, 需要结合自身的父亲来确认自己之前是属于 左子还是右子
		if node.Parent.Left == node { // 被旋转节点之前是 左子时
			// 用 y 来作为之前 该节点父亲的 新左子
			node.Parent.Left = y
		} else { // 否则，是 右子
			node.Parent.Right = y
		}
	}

	// 将 node 设为 y 的左子
	y.Left = node
	// 将 y 设为 node 的新父亲
	node.Parent = y
}

/*
 * 对红黑树的节点(y)进行右旋转
 *
 * 右旋示意图(对节点 y 进行左旋)：
 *            py                               py
 *           /                                /
 *          y                                x
 *         /  \\      --(右旋)-.            /  \\                     #
 *        x   ry                           lx   y
 *       / \\                                   / \\                   #
 *      lx  rx                                rx  ry
 *
 */
func (t *RBTree) rightSpin(node *RBNode) {
	// 先提出自己的 左子
	x := node.Left
	node.Left = x.Right

	if nil != x.Left {
		x.Right.Parent = node
	}

	x.Parent = node.Parent

	// 如果被旋转的节点是 之前树的根
	// 那么，新的跟就是 x 节点
	if nil == node.Parent {
		t.Root = x
	} else {

		if node.Parent.Right == node {
			node.Parent.Right = x
		} else {
			node.Parent.Left = x
		}
	}

	x.Right = node

	node.Parent = x
}

func insertValue(tree *RBTree, val, index int) {
	node := &RBNode{Value: val, Index: index, Color: BLACK}
	if nil == tree.Root {
		tree.Root = node
	}else{
		tree.insert(node)
	}
}

func (t *RBTree) insert(node *RBNode) {
	//int cmp;
	var tmpNode *RBNode
	root := t.Root

	// 1. 将红黑树当作一颗二叉查找树，将节点添加到二叉查找树中。
	for nil != root {
		if node.Value < root.Value {
			root = root.Left
		} else {
			root = root.Right
		}
		tmpNode = root
	}

	node.Parent = tmpNode
	if nil != tmpNode {

		if node.Value < tmpNode.Value {
			tmpNode.Left = node
		} else {
			tmpNode.Right = node
		}
	} else {
		t.Root = node
	}

	// 2. 设置节点的颜色为红色
	node.Color = RED

	// 3. 将它重新修正为一颗二叉查找树
	t.adjustRBTree(node)
}

// 修正树
func (t *RBTree) adjustRBTree(node *RBNode) {
	var parent, gparent *RBNode // 父亲 和 祖父

	// 若“父节点存在，并且父节点的颜色是红色”
	for nil != node.Parent && RED == node.Parent.Color {
		parent = node.Parent
		gparent = parent.Parent

		//若“父节点”是“祖父节点的左孩子”
		if parent == gparent.Left {
			// Case 1条件：叔叔节点是红色
			uncle := gparent.Right
			if nil != uncle && RED == uncle.Color {
				uncle.Color = BLACK
				parent.Color = BLACK
				gparent.Color = RED
				node = gparent
				continue
			}

			// Case 2条件：叔叔是黑色，且当前节点是右孩子
			if node == parent.Right {
				var tmp *RBNode
				t.leftSpin(parent)
				tmp = parent
				parent = node
				node = tmp
			}

			// Case 3条件：叔叔是黑色，且当前节点是左孩子。
			parent.Color = BLACK
			gparent.Color = RED
			t.rightSpin(gparent)
		} else { //若“z的父节点”是“z的祖父节点的右孩子”
			// Case 1条件：叔叔节点是红色
			uncle := gparent.Left
			if nil != uncle && RED == uncle.Color {
				uncle.Color = BLACK
				parent.Color = BLACK
				gparent.Color = RED
				node = gparent
				continue
			}

			// Case 2条件：叔叔是黑色，且当前节点是左孩子
			if node == parent.Left {
				var tmp *RBNode
				t.rightSpin(parent)
				tmp = parent
				parent = node
				node = tmp
			}

			// Case 3条件：叔叔是黑色，且当前节点是右孩子。
			parent.Color = BLACK
			gparent.Color = RED
			t.leftSpin(gparent)
		}
	}
	// 将根节点设为黑色
	t.Root.Color = BLACK
}

/**
红黑树查找
 */
func RedBlackTreeSearch(arr []int, key int) int{
	// 先构造树
	tree := new(RBTree)
	for i, v := range arr {
		insertValue(tree, v, i)
	}
	// 开始二叉树查找目标key
	return tree.serch(key)
}

func (t *RBTree) serch(key int) int {
	return serch(t.Root, key)
}
func serch(node *RBNode, key int) int {
	if nil == node {
		return -1
	}
	if key < node.Value {
		return serch(node.Left, key)
	}else if key > node.Value {
		return serch(node.Right, key)
	}else {
		return node.Index
	}
}

请我喝杯咖啡吧~

支付宝
微信