20162314 Experiment 2 - Tree

Experiment report of Besti

course：《Program Design & Data Structures》

Class： 1623

Student Name： Wang, Yixiao

Student Number：20162314

Tutor：Mr.Lou、Mr.Wang

Experiment date：2017.10.27

Secret level： Unsecretive

Experiment time：60 minutes

Major/Elective：Major

Experiment order：6

Experiment content

1. LinkedBinaryTreeTest
   

1. BinaryTree
   

1. DecisionTree
   

1. Expression Tree
   

1. BinarySearchTree
   

6.Analyze Source Code (Red-Black Tree)

Experiment situation

Exp1 LinkedBinaryTreeTest

• It's easy to finish this experiment.
• To start with , import to form a new LinkedBinaryTree to start the experiment.
• Next , use the method GetRight GetLeft to ealuation.
• Then , new element "ABC".
• Last , Assert.assertequals();

Exp2 BinaryTree

• To start with , use the number to replace "A B C D ....."
• Next , new newNode
• Then, creat BinTree to get left child and right child
• Use three methods preOrderTraverse,inOrderTraverse,postOrderTraverse.

Exp3 Decision Tree

• To start with , creat a class TwentyQuestionsPlayer
• String the Questions and the answers as the order
• New them
• Write a method play(),Yes =Y , No=N .
• Next , write a function to finish this experiment.

Exp4 ExpressionTree

Exp5 BinarySearchTreeTest

• To start with , creat a class BinarySearchTree
• public method Node find, insert,preorder,inorder,postorder,getMinNode get MaxNode，Delete.
• creat three new Nodes(id and name);
• Node n1 n2 n3 n4 ...n7 n8
• Use method insert to n4 n5 n6 n7 n8
• Bst.inorder and Systemin.

Exp6 Red-Black Tree (Analyze Source Code)

• TreeMap底层通过红黑树（Red-Black tree）实现，也就意味着containsKey(), get(), put(), remove()都有着log(n)的时间复杂度。
  

• SortedMap m = Collections.synchronizedSortedMap(new TreeMap(...));

• 结构调整过程包含两个基本操作：左旋（Rotate Left），右旋（RotateRight）。
  
• Rotate Left

  //Rotate Left
private void rotateLeft(Entry<K,V> p) {if (p != null) {Entry<K,V> r = p.right;p.right = r.left;if (r.left != null)r.left.parent = p;r.parent = p.parent;if (p.parent == null)root = r;else if (p.parent.left == p)p.parent.left = r;elsep.parent.right = r;r.left = p;p.parent = r;}
}

• Rotate Right

  //Rotate Right
private void rotateRight(Entry<K,V> p) {if (p != null) {Entry<K,V> l = p.left;p.left = l.right;if (l.right != null) l.right.parent = p;l.parent = p.parent;if (p.parent == null)root = l;else if (p.parent.right == p)p.parent.right = l;else p.parent.left = l;l.right = p;p.parent = l;}
}

• .get()
  

  //getEntry()方法
final Entry<K,V> getEntry(Object key) {......if (key == null)//不允许key值为nullthrow new NullPointerException();Comparable<? super K> k = (Comparable<? super K>) key;//使用元素的自然顺序Entry<K,V> p = root;while (p != null) {int cmp = k.compareTo(p.key);if (cmp < 0)//向左找p = p.left;else if (cmp > 0)//向右找p = p.right;elsereturn p;}return null;
}

• .put()

  public V put(K key, V value) {......int cmp;Entry<K,V> parent;if (key == null)throw new NullPointerException();Comparable<? super K> k = (Comparable<? super K>) key;//使用元素的自然顺序do {parent = t;cmp = k.compareTo(t.key);if (cmp < 0) t = t.left;//向左找else if (cmp > 0) t = t.right;//向右找else return t.setValue(value);} while (t != null);Entry<K,V> e = new Entry<>(key, value, parent);//创建并插入新的entryif (cmp < 0) parent.left = e;else parent.right = e;fixAfterInsertion(e);//调整size++;return null;
}

  //红黑树调整函数fixAfterInsertion()
private void fixAfterInsertion(Entry<K,V> x) {x.color = RED;while (x != null && x != root && x.parent.color == RED) {if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {Entry<K,V> y = rightOf(parentOf(parentOf(x)));if (colorOf(y) == RED) {//如果y为null，则视为BLACKsetColor(parentOf(x), BLACK);              // 情况1setColor(y, BLACK);                        // 情况1setColor(parentOf(parentOf(x)), RED);      // 情况1x = parentOf(parentOf(x));                 // 情况1} else {if (x == rightOf(parentOf(x))) {x = parentOf(x);                       // 情况2rotateLeft(x);                         // 情况2}setColor(parentOf(x), BLACK);              // 情况3setColor(parentOf(parentOf(x)), RED);      // 情况3rotateRight(parentOf(parentOf(x)));        // 情况3}} else {Entry<K,V> y = leftOf(parentOf(parentOf(x)));if (colorOf(y) == RED) {setColor(parentOf(x), BLACK);              // 情况4setColor(y, BLACK);                        // 情况4setColor(parentOf(parentOf(x)), RED);      // 情况4x = parentOf(parentOf(x));                 // 情况4} else {if (x == leftOf(parentOf(x))) {x = parentOf(x);                       // 情况5rotateRight(x);                        // 情况5}setColor(parentOf(x), BLACK);              // 情况6setColor(parentOf(parentOf(x)), RED);      // 情况6rotateLeft(parentOf(parentOf(x)));         // 情况6}}}root.color = BLACK;
}

Code hosting

PSP5.1(Personal Software Process)

Steps	Time	percent
requirement	45minutes	16.7%
design	50minutes	18.5%
coding	1.5hours	32.2%
test	30minutes	11.1%
summary	55minutes	19.2%