实验三
—: |
| 姓名 | 郭子任 |
Pro1
1.二叉搜索树结点定义
public class public class TreeNode {
int val;//关键字
TreeNode left;//左孩子
TreeNode right;//右孩子
TreeNode parent;//父节点
public TreeNode() {
}
public TreeNode(int val) {
this.val = val;
}
}
2.查找值最小的结点
private TreeNode findMostLeftprivate TreeNode findMostLeft(TreeNode node){
if (node == null){
return null;
}
while (node.left != null){
node = node.left;
}
return node;
}
3.查找值最大的结点
private TreeNode findMaxprivate TreeNode findMax(TreeNode node){
if (node == null){
return null;
}
while (node.right != null){
node = node.right;
}
return node;
}
4.查找前驱结点
public TreeNode getPredecessorNodepublic TreeNode getPredecessorNode(TreeNode node){
if (node == null){
return null;
}
if (node.left != null){
return findMax(node.left);
}else{
TreeNode parent = node.parent;
while (parent != null && node != parent.right){
node = node.parent;
parent = node;
}
return parent;
}
}
5.查找后继结点
public TreeNode getSucessorNodepublic TreeNode getSucessorNode(TreeNode node){
if (node == null){
return null;
}
//是否有右子树，有的话，就是右子树最左节点
if (node.right != null){
return findMostLeft(node.right);
}else {
TreeNode parent = node.parent;
while (parent != null && node != parent.left){
node = node.parent;
parent = parent.parent;
}
return parent;
}
//没有右子树，则向上找
}
6.判断是否为搜索/查找/排序二叉树
public boolean isBinarySearchTreepublic boolean isBinarySearchTree(TreeNode root) {
if (root == null){
System.out.println("这是个空树");
return true;
}
Stack stack = new Stack<>();
TreeNode p = root;
Integer pre = null;
while (!stack.isEmpty() || p != null){
if(p != null){
stack.push(p);
p = p.left;
}else{
p = stack.pop();
if (pre != null && p.val < pre){
return false;
}
pre = new Integer(p.val);
// System.out.print(p.val + " ");
p = p.right;
}
}
return true;
}
7.根据给定列表构造二叉树
public TreeNode constructBinaryTreeByArraypublic TreeNode constructBinaryTreeByArray(List arr) {
if (arr.size() == 0){
return null;
}
int length = arr.size();
HashMap nodes = new HashMap<>();
int i = 0;
TreeNode root = new TreeNode(arr.get(i));
nodes.put(arr.get(0),root);
TreeNode cur = null;
while (true){
if (i == 0){
cur = root;
}else{
//null的话，直接遍历下一个
if (null == arr.get(i)){
i++;
continue;
}
cur = getNode(nodes,i,arr);
}
int leftChildPosition = 2 * i + 1;
int rightChildPosition = 2 * (i + 1) ;
if (leftChildPosition >= length){
break;
}
cur.left = getNode(nodes,leftChildPosition,arr);
if (rightChildPosition >= length){
break;
}
cur.right = getNode(nodes,rightChildPosition,arr);;
i++;
}
return root;
}
private TreeNode getNode(HashMap nodes,int i,List arr) {
TreeNode cur = null;
//存在的话 直接返回
if (null == arr.get(i)){
return cur;
}
if (nodes.containsKey(arr.get(i))) {
cur = nodes.get(arr.get(i));
}else{
cur = new TreeNode(arr.get(i));
nodes.put(arr.get(i),cur);
}
return cur;
}
8.测试判断是否为二叉树
测试代码
@Test
public void test(){
List<Integer> arr = new ArrayList<>();
arr.add(5);
arr.add(1);
arr.add(4);
arr.add(null);
arr.add(null);
arr.add(3);
arr.add(6);
TreeNode root = constructBinaryTreeByArray(arr);
boolean result = isBinarySearchTree(root);
System.out.println(result);
}测试结果
false
Process finished with exit code 0Pro2
红黑树Java实现
public class BRT<public class BRT<K> {
private transient int size = 0;
// Red-black mechanics
private transient Entry root;
private static final boolean RED = false;
private static final boolean BLACK = true;
static final class Entry<K> {
K key;
Entry left;
Entry right;
Entry parent;
boolean color = BLACK;
Entry(K key,Entry parent) {
this.key = key;
this.parent = parent;
}
public K getKey() {
return key;
}
}
final Entry getFirstEntry() {
Entry p = root;
if (p != null) {
while (p.left != null) {
p = p.left;
}
}
return p;
}
public int size() {
return size;
}
public void put(K key) {
Entry t = root;
if (t == null) {
root = new Entry<>(key, null);
size = 1;
return ;
}
Entry parent;
int cmp;
if (key == null) {
throw new NullPointerException();
}
@SuppressWarnings("unchecked")
Comparablesuper K> k = (Comparablesuper K>) key;
do {
parent = t;
cmp = k.compareTo(t.key);
if (cmp < 0) {
t = t.left;
}else if (cmp > 0) {
t = t.right;
}else {
}
} while (t != null);
Entry e = new Entry<>(key,parent);
if (cmp < 0) {
parent.left = e;
}else {
parent.right = e;
}
fixAfterInsertion(e);
size++;
}
/** From CLR */
private void fixAfterInsertion(Entry x) {
x.color = RED;
while (x != null && x != root && x.parent.color == RED) {
if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
Entry y = rightOf(parentOf(parentOf(x)));
if (colorOf(y) == RED) {
setColor(parentOf(x), BLACK);
setColor(y, BLACK);
setColor(parentOf(parentOf(x)), RED);
x = parentOf(parentOf(x));
} else {
if (x == rightOf(parentOf(x))) {
x = parentOf(x);
rotateLeft(x);
}
setColor(parentOf(x), BLACK);
setColor(parentOf(parentOf(x)), RED);
rotateRight(parentOf(parentOf(x)));
}
} else {
Entry y = leftOf(parentOf(parentOf(x)));
if (colorOf(y) == RED) {
setColor(parentOf(x), BLACK);
setColor(y, BLACK);
setColor(parentOf(parentOf(x)), RED);
x = parentOf(parentOf(x));
} else {
if (x == leftOf(parentOf(x))) {
x = parentOf(x);
rotateRight(x);
}
setColor(parentOf(x), BLACK);
setColor(parentOf(parentOf(x)), RED);
rotateLeft(parentOf(parentOf(x)));
}
}
}
root.color = BLACK;
}
public static boolean colorOf(Entry p) {
return (p == null ? BLACK : p.color);
}
private static Entry parentOf(Entry p) {
return (p == null ? null: p.parent);
}
private static void setColor(Entry p, boolean c) {
if (p != null) {
p.color = c;
}
}
private static Entry leftOf(Entry p) {
return (p == null) ? null: p.left;
}
private static Entry rightOf(Entry p) {
return (p == null) ? null: p.right;
}
/** From CLR */
private void rotateLeft(Entry p) {
if (p != null) {
Entry 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;
} else {
p.parent.right = r;
}
r.left = p;
p.parent = r;
}
}
/** From CLR */
private void rotateRight(Entry p) {
if (p != null) {
Entry 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;
}
}
public void remove(Object key) {
Entry p = getEntry(key);
if (p == null) {
return ;
}
deleteEntry(p);
}
final Entry getEntry(Object key) {
if (key == null) {
throw new NullPointerException();
}
@SuppressWarnings("unchecked")
Comparablesuper K> k = (Comparablesuper K>) key;
Entry p = root;
while (p != null) {
int cmp = k.compareTo(p.key);
if (cmp < 0) {
p = p.left;
} else if (cmp > 0) {
p = p.right;
} else {
return p;
}
}
return null;
}
/**
* Delete node p, and then rebalance the tree.
*/
private void deleteEntry(Entry p) {
size--;
// If strictly internal, copy successor's element to p and then make p
// point to successor.
if (p.left != null && p.right != null) {
Entry s = successor(p);
p.key = s.key;
p = s;
} // p has 2 children
// Start fixup at replacement node, if it exists.
Entry replacement = (p.left != null ? p.left : p.right);
if (replacement != null) {
// Link replacement to parent
replacement.parent = p.parent;
if (p.parent == null) {
root = replacement;
} else if (p == p.parent.left) {
p.parent.left = replacement;
} else {
p.parent.right = replacement;
}
// Null out links so they are OK to use by fixAfterDeletion.
p.left = p.right = p.parent = null;
// Fix replacement
if (p.color == BLACK) {
fixAfterDeletion(replacement);
}
} else if (p.parent == null) { // return if we are the only node.
root = null;
} else { // No children. Use self as phantom replacement and unlink.
if (p.color == BLACK) {
fixAfterDeletion(p);
}
if (p.parent != null) {
if (p == p.parent.left) {
p.parent.left = null;
} else if (p == p.parent.right) {
p.parent.right = null;
}
p.parent = null;
}
}
}
/** From CLR */
private void fixAfterDeletion(Entry x) {
while (x != root && colorOf(x) == BLACK) {
if (x == leftOf(parentOf(x))) {
Entry sib = rightOf(parentOf(x));
if (colorOf(sib) == RED) {
setColor(sib, BLACK);
setColor(parentOf(x), RED);
rotateLeft(parentOf(x));
sib = rightOf(parentOf(x));
}
if (colorOf(leftOf(sib)) == BLACK &&
colorOf(rightOf(sib)) == BLACK) {
setColor(sib, RED);
x = parentOf(x);
} else {
if (colorOf(rightOf(sib)) == BLACK) {
setColor(leftOf(sib), BLACK);
setColor(sib, RED);
rotateRight(sib);
sib = rightOf(parentOf(x));
}
setColor(sib, colorOf(parentOf(x)));
setColor(parentOf(x), BLACK);
setColor(rightOf(sib), BLACK);
rotateLeft(parentOf(x));
x = root;
}
} else { // symmetric
Entry sib = leftOf(parentOf(x));
if (colorOf(sib) == RED) {
setColor(sib, BLACK);
setColor(parentOf(x), RED);
rotateRight(parentOf(x));
sib = leftOf(parentOf(x));
}
if (colorOf(rightOf(sib)) == BLACK &&
colorOf(leftOf(sib)) == BLACK) {
setColor(sib, RED);
x = parentOf(x);
} else {
if (colorOf(leftOf(sib)) == BLACK) {
setColor(rightOf(sib), BLACK);
setColor(sib, RED);
rotateLeft(sib);
sib = leftOf(parentOf(x));
}
setColor(sib, colorOf(parentOf(x)));
setColor(parentOf(x), BLACK);
setColor(leftOf(sib), BLACK);
rotateRight(parentOf(x));
x = root;
}
}
}
setColor(x, BLACK);
}
/**
* Returns the successor of the specified Entry, or null if no such.
*/
static Entry successor(Entry t) {
if (t == null) {
return null;
} else if (t.right != null) {
Entry p = t.right;
while (p.left != null) {
p = p.left;
}
return p;
} else {
Entry p = t.parent;
Entry ch = t;
while (p != null && ch == p.right) {
ch = p;
p = p.parent;
}
return p;
}
}
private class KeyIterator implements Iterator {
Entry next;
KeyIterator(Entry first){
next = first;
}
@Override
public boolean hasNext() {
return next != null;
}
@Override
public Object next() {
Entry e = next;
if (e == null) {
throw new NoSuchElementException();
}
next = successor(e);
return e;
}
}
Iterator keyIterator() {
return new KeyIterator(getFirstEntry());
}
}
测试代码
public static void mainpublic static void main(String[] args) {
BRT brt = new BRT();
int[] arr = new int[]{1,5,6,7,8,9,10,11,12,13,14,15};
for (int i = 0; i < arr.length; i++) {
brt.put(arr[i]);
}
traverse(brt);
brt.remove(14);
brt.remove(9);
brt.remove(5);
System.out.println("-------------------------------");
traverse(brt);
}
private static void traverse(BRT brt) {
Iterator iterator = brt.keyIterator();
while (iterator.hasNext()){
BRT.Entry entry = (BRT.Entry) iterator.next();
if (!entry.color){
System.out.print("red ");
}else{
System.out.print("black ");
}
System.out.println(entry.key);
}
}
测试结果
black black 1
black 5
black 6
black 7
black 8
red 9
black 10
black 11
black 12
red 13
black 14
red 15
-------------------------------
red 1
black 6
black 7
red 8
black 10
black 11
black 12
black 13
black 15
三、二叉搜索树与红黑树对比
1.区别
- 红黑树结点有红色黑色之分，二叉查找树没有
- 红黑树是接近平衡的二叉树，二叉查找树不一定是平衡的
- 红黑树不会退化为高度O(n)，二叉查找树在给定序列有序时高度会退化为O(n)
- 为了保持平衡，红黑树有旋转操作，二叉查找树没有
2.时间复杂度
| 红黑树 | 二叉查找树 | |
|---|---|---|
| 插入 | O(logn) | O(h) |
| 删除 | O(logn) | O(h) |
| 前驱 | O(logn) | O(h) |
| 后继 | O(logn) | O(h) |
| 查找给定结点 | O(logn) | O(h) |
3.空间复杂度
两者以上各种操作空间复杂度相同均为O(1)
本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！