问题引入
二叉搜索树
特点,简介
代码简单功能实现
二叉搜索树
代码简单实现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
56public class BinarySearchTree
{
int data;
BinarySearchTree left;
BinarySearchTree right;
public BinarySearchTree(int data)
{
this.data = data;
}
void insert(BinarySearchTree root, int data)
{
if (data < root.data)// 左插入
{
if (root.left == null)
{
root.left = new BinarySearchTree(data);
} else
{
insert(root.left, data);
}
} else// 右插入
{
if (root.right == null)
{
root.right = new BinarySearchTree(data);
} else
{
insert(root.right, data);
}
}
}
void in(BinarySearchTree root)
{
if (root != null)
{
in(root.left);
System.out.print(root.data + " ");
in(root.right);
}
}
public static void main(String[] args)
{
int[] nums = {4, 12, 4, 58, 19, 0, 98, 23, 5, 0, 123};
BinarySearchTree root = new BinarySearchTree(nums[0]);
for (int i = 1; i < nums.length; i++)
{
root.insert(root, nums[i]);
}
// 从小到大依次输出
root.in(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
96public class Node
{
int data;
Node left;
Node right;
Node parent;
Boolean R;
public Node(int data)
{
this.data = data;
this.R = true;
}
// 查找根节点
Node root()
{
for (Node root = this; ; )
{
if (root.parent == null)
{
return root;
}
root = root.parent;
}
}
void insert(int data)
{
Node root = root();
{
root = new Node(data);
root.R = false;
} else
{
Node temp = root;
while (true)
{
if (data < temp.data)// 左插入
{
if (temp.left == null)
{
temp.left = new Node(data);
temp.left.parent = temp;
break;
} else
{
temp = temp.left;
}
} else// 右插入
{
if (temp.right == null)
{
temp.right = new Node(data);
temp.right.parent = temp;
break;
} else
{
temp = temp.right;
}
}
}
}
// 变色,左旋,右旋
}
// 左旋
// 情况:父红,叔黑,是右子树
// 旋转规则:以父亲左旋
void RotateLeft(Node node)
{
Node right = node.right;
right.left.parent = node;
node.right = right.left;
if (node.parent == null)// 根节点
{
right.parent = null;
} else
{
right.parent = node.parent;
if (right.data < node.parent.data)// 左
{
node.parent.left = right;
} else// 右
{
node.parent.right = right;
}
}
right.left = node;
node.parent = right;
}
}