8000 完成红黑树并通过测试。 · mapengfei00099/javaalgorithm@eaa5605 · GitHub
[go: up one dir, main page]
Skip to content

Commit eaa5605

Browse files
author
shengshijun
committed
完成红黑树并通过测试。
1 parent 92e5440 commit eaa5605

File tree

4 files changed

+251
-30
lines changed

4 files changed

+251
-30
lines changed

‎src/main/java/ssj/algorithm/SearchTree.java

Lines changed: 12 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -40,7 +40,18 @@ default void deleteAll(Iterable<? extends T> iter) {
4040

4141
T min();
4242

43-
T kthElement(int k);
43+
default T kthElement(int k) {
44+
Preconditions.checkPositionIndex(k, size());
45+
int cur_pos = 0;
46+
for (T ele : this) {
47+
if (cur_pos == k) {
48+
return ele;
49+
}
50+
cur_pos++;
51+
}
52+
return null;
53+
}
54+
4455

4556
boolean contains(T ele);
4657

‎src/main/java/ssj/algorithm/collections/AVLTree.java

Lines changed: 0 additions & 13 deletions
Original file line numberDiff line numberDiff line change
@@ -539,19 +539,6 @@ public T min() {
539539
return cur_node.getValue();
540540
}
541541

542-
@Override
543-
public T kthElement(int k) {
544-
Preconditions.checkPositionIndex(k, size());
545-
int cur_pos = 0;
546-
for (T ele : this) {
547-
if (cur_pos == k) {
548-
return ele;
549-
}
550-
cur_pos++;
551-
}
552-
return null;
553-
}
554-
555542
@Override
556543
public boolean contains(T ele) {
557544
return findNode(ele) != null;

‎src/main/java/ssj/algorithm/collections/RedBlackTree.java

Lines changed: 183 additions & 16 deletions
Original file line numberDiff line numberDiff line change
@@ -2,6 +2,7 @@
22

33
import com.google.common.base.Preconditions;
44
import ssj.algorithm.SearchTree;
5+
import ssj.algorithm.util.CheckUtil;
56

67
import java.util.Iterator;
78

@@ -107,15 +108,6 @@ public int size() {
107108
return tree_size;
108109
}
109110

110-
@Override
111-
public Iterator<T> preIterator() {
112-
return null;
113-
}
114-
115-
@Override
116-
public Iterator<T> postIterator() {
117-
return null;
118-
}
119111

120112
@Override
121113
public void delete(T ele) {
@@ -363,14 +355,9 @@ public T min() {
363355
return (min_node == null) ? null : min_node.getValue();
364356
}
365357

366-
@Override
367-
public T kthElement(int k) {
368-
return null;
369-
}
370-
371358
@Override
372359
public boolean contains(T ele) {
373-
return false;
360+
return findNode(ele) != null;
374361
}
375362

376363
@Override
@@ -380,7 +367,18 @@ public boolean isBalance() {
380367

381368
@Override
382369
public Iterator<T> iterator() {
383-
return null;
370+
return new MidTreeIterator();
371+
}
372+
373+
@Override
374+
public Iterator<T> preIterator() {
375+
return new PreTreeIterator();
376+
377+
}
378+
379+
@Override
380+
public Iterator<T> postIterator() {
381+
return new PostTreeIterator();
384382
}
385383

386384
private enum TreeNodeColor {
@@ -545,4 +543,173 @@ public void setValue(T value) {
545543
this.value = value;
546544
}
547545
}
546+
547+
private class PreTreeIterator implements Iterator<T> {
548+
549+
int iter_size;
550+
LinkedStack<Node<T>> _stacks;
551+
Node<T> cur_node;
552+
553+
554+
public PreTreeIterator() {
555+
iter_size = size();
556+
_stacks = new LinkedStack<>();
557+
if (root != null) {
558+
_stacks.push(root);
559+
}
560+
cur_node = null;
561+
}
562+
563+
@Override
564+
public boolean hasNext() {
565+
CheckUtil.checkCurrencyModify(iter_size, size());
566+
boolean result = !_stacks.isEmpty();
567+
cur_node = _stacks.pop();
568+
if (cur_node != null) {
569+
if (cur_node.getLeft() != null) {
570+
_stacks.push(cur_node.getLeft());
571+
}
572+
if (cur_node.getRight() != null) {
573+
_stacks.push(cur_node.getRight());
574+
}
575+
}
576+
return result;
577+
}
578+
579+
@Override
580+
public T next() {
581+
CheckUtil.checkCurrencyModify(iter_size, size());
582+
return cur_node.getValue();
583+
}
584+
}
585+
586+
private class MidTreeIterator implements Iterator<T> {
587+
private int iter_size;
588+
private LinkedStack<Node<T>> _stacks;
589+
private Node<T> cur_node;
590+
591+
public MidTreeIterator() {
592+
iter_size = size();
593+
_stacks = new LinkedStack<>();
594+
if (root != null) {
595+
cur_node = root;
596+
insertLeft(cur_node);
597+
}
598+
}
599+
600+
private void insertLeft(Node start_node) {
601+
Node cur_start_node = start_node;
602+
while (cur_start_node != null) {
603+
_stacks.push(cur_start_node);
604+
cur_start_node = cur_start_node.getLeft();
605+
}
606+
}
607+
608+
@Override
609+
public boolean hasNext() {
610+
CheckUtil.checkCurrencyModify(iter_size, size());
611+
if (!_stacks.isEmpty()) {
612+
cur_node = _stacks.pop();
613+
insertLeft(cur_node.getRight());
614+
return true;
615+
}
616+
return false;
617+
}
618+
619+
@Override
620+
public T next() {
621+
CheckUtil.checkCurrencyModify(iter_size, size());
622+
return cur_node.getValue();
623+
}
624+
}
625+
626+
private class PostTreeIterator implements Iterator<T> {
627+
private int iter_size;
628 F987 +
private LinkedStack<Node> unvisited_stack;
629+
private LinkedStack<Node> visited_stack;
630+
private Node<T> cur_node;
631+
632+
public PostTreeIterator() {
633+
iter_size = size();
634+
unvisited_stack = new LinkedStack<>();
635+
visited_stack = new LinkedStack<>();
636+
if (root != null) {
637+
unvisited_stack.push(root);
638+
initStack();
639+
}
640+
}
641+
642+
private void initStack() {
643+
if (!unvisited_stack.isEmpty()) {
644+
Node this_node = unvisited_stack.head();
645+
while (!shouldVisit(this_node)) {
646+
if (this_node.getRight() != null) {
647+
unvisited_stack.push(this_node.getRight());
648+
}
649+
650+
if (this_node.getLeft() != null) {
651+
unvisited_stack.push(this_node.getLeft());
652+
}
653+
this_node = unvisited_stack.head();
654+
}
655+
}
656+
}
657+
658+
private Node insertUnvisitedNode(Node node) {
659+
Node this_node = node;
660+
while (!shouldVisit(this_node)) {
661+
unvisited_stack.push(this_node);
662+
if (this_node.getRight() != null) {
663+
unvisited_stack.push(this_node.getRight());
664+
}
665+
666+
if (this_node.getLeft() != null) {
667+
unvisited_stack.push(this_node.getLeft());
668+
}
669+
this_node = unvisited_stack.pop();
670+
}
671+
return this_node;
672+
}
673+
674+
private boolean shouldVisit(Node node) {
675+
boolean left_result = false;
676+
boolean right_result = false;
677+
Node visited_right_node;
678+
if (node.getRight() == null) {
679+
right_result = true;
680+
} else if ((visited_right_node = visited_stack.head()) != null && (node.getRight() == visited_right_node)) {
681+
right_result = true;
682+
visited_stack.pop();
683+
}
684+
685+
Node visited_left_node;
686+
if (node.getLeft() == null) {
687+
left_result = true;
688+
} else if ((visited_left_node = visited_stack.head()) != null && (node.getLeft() == visited_left_node)) {
689+
left_result = true;
690+
visited_stack.pop();
691+
}
692+
693+
return left_result && right_result;
694+
}
695+
696+
@Override
697+
public boolean hasNext() {
698+
CheckUtil.checkCurrencyModify(iter_size, size());
699+
boolean result = !unvisited_stack.isEmpty();
700+
if (!unvisited_stack.isEmpty()) {
701+
cur_node = insertUnvisitedNode(unvisited_stack.pop());
702+
visited_stack.push(cur_node);
703+
}
704+
return result;
705+
}
706+
707+
@Override
708+
public T next() {
709+
CheckUtil.checkCurrencyModify(iter_size, size());
710+
return cur_node.getValue();
711+
}
712+
}
713+
548714
}
715+

‎src/test/java/ssj/algorithm/collections/RedBlackTreeTest.java

Lines changed: 56 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -3,6 +3,10 @@
33

44
import org.junit.Test;
55

6+
import java.util.Iterator;
7+
8+
import static org.junit.Assert.assertEquals;
9+
import static org.junit.Assert.assertFalse;
610
import static org.junit.Assert.assertTrue;
711

812
/**
@@ -37,5 +41,57 @@ public void testDelete() {
3741
tree.size();
3842
}
3943

44+
@Test
45+
public void testPostIterator() {
46+
int[] tree_data = new int[]{10, 4, 6, 14, 4, 8, 9, 12, 16, 11};
47+
RedBlackTree<Integer> tree = RedBlackTree.newInstance();
48+
for (int i : tree_data) {
49+
tree.add(i);
50+
}
51+
Iterator<Integer> iterator = tree.postIterator();
52+
while (iterator.hasNext()) {
53+
System.out.println(iterator.next());
54+
}
55+
}
56+
57+
@Test
58+
public void testIterator() {
59+
RedBlackTree<Integer> tree = RedBlackTree.newInstance();
60+
Integer[] values = new Integer[10001];
61+
for (int i = 0; i < 10001; i++) {
62+
tree.add(i);
63+
values[i] = i;
64+
}
65+
assertEquals(tree.size(), 10001);
66+
assertTrue(tree.max().equals(10000));
67+
assertTrue(tree.min().equals(0));
68+
assertTrue(tree.contains(10000));
69+
assertFalse(tree.contains(1000000));
70+
71+
Iterator<Integer> pre_iterator = tree.preIterator();
72+
while (pre_iterator.hasNext()) {
73+
values[pre_iterator.next()] = null;
74+
}
75+
for (int i = 0; i < 10001; i++) {
76+
assertTrue(values[i] == null);
77+
values[i] = i;
78+
}
79+
80+
Iterator<Integer> mid_iterator = tree.iterator();
81+
for (int i = 0; i < tree.size() && mid_iterator.hasNext(); i++) {
82+
assertEquals(values[i], mid_iterator.next());
83+
}
84+
85+
Iterator<Integer> post_iterator = tree.postIterator();
86+
while (post_iterator.hasNext()) {
87+
values[post_iterator.next()] = null;
88+
}
89+
for (int i = 0; i < 10001; i++) {
90+
assertTrue(values[i] == null);
91+
values[i] = i;
92+
}
93+
}
94+
95+
4096

4197
}

0 commit comments

Comments
 (0)
0