blob: fc4acdd18670ebfeacc25fcd5743c3a5cec75ef3 (
plain)
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
|
using System;
namespace ALGA {
public class Node {
public int number;
public Node left, right;
public Node(int number) {
this.number = number;
}
public Node insert(int value) {
if (number == value) return this;
if (value > number) {
if (right != null)
right = right.insert(value);
else
right = new Node(value);
} else {
if (left != null)
left = left.insert(value);
else
left = new Node(value);
}
int balance = depth(left) - depth(right);
if (Math.Abs(balance) <= 1) return this;
if (balance > 0) {
if (value > left.number)
left = left.rotateLeft();
return rotateRight();
} else {
if (value < right.number)
right = right.rotateRight();
return rotateLeft();
}
}
public Node rotateLeft() {
if (right == null) return null;
Node pivot = right;
(right, right.left) = (right.left, this);
return pivot;
}
public Node rotateRight() {
if (left == null) return null;
Node pivot = left;
(left, left.right) = (left.right, this);
return pivot;
}
public bool isBalanced() {
if (Math.Abs(depth(left) - depth(right)) > 1) return false;
if (left != null && !left.isBalanced()) return false;
if (right != null && !right.isBalanced()) return false;
return true;
}
private int depth(Node here) {
if (here == null) return 0;
return 1 + Math.Max(depth(here.left), depth(here.right));
}
}
}
|