下面是红黑树类的实现：
由于本人的java水平有限，写得不是很好，希望大牛们指点
RedBlackTree.java
由于本人的java水平有限，写得不是很好，希望大牛们指点
RedBlackTree.java
package datastruct;
import static java.lang.System.out;
import java.util.Stack;
import common.Color;
import common.TreeNode;
/**
*
* @Author changzhi
* @Email changzhiwin@163.com
* @Date Oct 27, 2009
* @File RedBlackTree.java
* @Project tree
*/
public class RedBlackTree<T extends Comparable<T>> {
/**
* 树根
*/
private TreeNode<T> root;
/**
* 哨兵节点
* can't use static var
*/
private TreeNode<T> nil;
public RedBlackTree()
{
nil = new TreeNode<T>(Color.BALCK,null,null,null,null);
this.root=nil;
}
public RedBlackTree(TreeNode<T> root)
{
nil = new TreeNode<T>(Color.BALCK,null,null,null,null);
this.root=root;
root.setParent(nil);
root.setLeft(nil);
root.setRight(nil);
}
/**
*
* @param key
* @return int
* 增加一个节点，初始其颜色为红色，这样将会导致不满足红黑树的性质，故
* 在这之后还需要对此树进行调整。
* 返回0添加成功
* 返回1有相同的key,添加失败
* 返回-1添加失败
*/
public int addNode(T key)
{
TreeNode<T> x = root;
TreeNode<T> y = nil ;
//空树
if(root == nil)
{
root = new TreeNode<T>(Color.BALCK,key,nil,nil,nil);
return 0;
}
//不是空树，引用y即指向插入节点的父节点
else
{
while(x != nil)
{
y = x;
if(x.getKey().compareTo(key) == 0)
return 1;
else if(x.getKey().compareTo(key) > 0)
x = x.getLeft();
else
x = x.getRight();
}
}
TreeNode<T> c = new TreeNode<T>(Color.RED,key,nil,nil,y);
if(y.getKey().compareTo(key) > 0)
y.setLeft(c);//成为左子树
else
y.setRight(c);//成为右子树
c.setLeft(nil );
c.setRight(nil);
insert_fixup(c);//调整
return 1;//插入成功
}
/**
* @param c
* 插入一个红节点后，为了维持红黑树的性质不变
* 定制的修复程序
*/
private void insert_fixup(TreeNode<T> c)
{
TreeNode<T> u = null;
while(c.getParent().getColor() == Color.RED)//父节点是红色，才需要调整
{
if(c.getParent() == c.getParent().getParent().getLeft())//考虑是祖父的左孩子时
{
u = c.getParent().getParent().getRight();//叔父节点
if(u.getColor() == Color.RED) //情况一
{
/* 如果叔父节点是红色的，而且父节点也是红色的，那么
* 只需要把叔父和父亲节的置为黑色，然后把祖父节点置为红色
* 这样就顺利的把需要调整的节点上移至祖父节点进行下一步调整
*/
c.getParent().setColor(Color.BALCK);
c.getParent().getParent().setColor(Color.RED);
u.setColor(Color.BALCK);
c = c.getParent().getParent();
}
else //情况二和情况三
{
if(c == c.getParent().getRight()) //情况二
{
/* 如果是父亲的右孩子，就需要左旋转，将情况二变成情况三,
* 旋转的节点是其父亲节点
*/
c = c.getParent();
left_rotate(c);
}
/* 下面的处理是针对情况三，即叔父节点为黑色，父亲节点为红色，
* 而且是父亲的左孩子，此时需要改变父亲和祖父的颜色，然后对
* 祖父节点进行右旋
*/
c.getParent().setColor(Color.BALCK);
c.getParent().getParent().setColor(Color.RED);
right_rotate(c.getParent().getParent());
}
}
else//考虑是祖父的右孩子时
{
/* 这种情况与上面的是完全对称的，故这此不在详叙
*/
u = c.getParent().getParent().getLeft();//right tree
if(u.getColor() == Color.RED)
{
c.getParent().setColor(Color.BALCK);
c.getParent().getParent().setColor(Color.RED);
u.setColor(Color.BALCK);
c = c.getParent().getParent();
}
else
{
if(c == c.getParent().getLeft())
{
c = c.getParent();
right_rotate(c);
}
c.getParent().setColor(Color.BALCK);
c.getParent().getParent().setColor(Color.RED);
left_rotate(c.getParent().getParent());
}
}
}
root.setColor(Color.BALCK);
}
/**
* @param node 此节点即是需要下移的节点
* @方法 左旋
*/
private void left_rotate(TreeNode<T> node)
{
/* 保存右子树的引用
*/
TreeNode<T> y = node.getRight();
/* 将node的右子树设置为y的左子树，如果y的左子树不空
* 则将其的父亲节点设置为node
* */
node.setRight(y.getLeft());
if(y.getLeft() != nil)
y.getLeft().setParent(node);
/* 将y节点上调，自然node节点就下调，成为y的子树
* */
y.setParent(node.getParent());
if(node.getParent() == nil)
root=y;
else
{
/*判断node节点是左子树还是右子树*/
if(node == node.getParent().getLeft())
node.getParent().setLeft(y);
else
node.getParent().setRight(y);
}
y.setLeft(node);
node.setParent(y);
}
/**
* @param node 此节点即是需要下移的节点
* @方法 右旋
*/
private void right_rotate(TreeNode<T> node)
{
/*此处右旋又和左旋对称，故不详叙*/
TreeNode<T> y = node.getLeft();
node.setLeft(y.getRight());
if(y.getRight() != nil)
y.getRight().setParent(node);
y.setParent(node.getParent());
if(node.getParent() == nil)
root=y;
else
{
if(node == node.getParent().getRight())
node.getParent().setRight(y);
else
node.getParent().setLeft(y);
}
y.setRight(node);
node.setParent(y);
}
/**
* @param key
* @return 删除成功与否
* @方法 删除数据为key的节点
*/
public boolean deleteNode(T key)
{
TreeNode<T> y = nil;
TreeNode<T> x = root;
/**
* 存取查找需要删除的节点的引用
*/
TreeNode<T> target;
/**
* 下面是查找过程，暂存于x中
*/
while(x != nil)
{
if(x.getKey().compareTo(key) == 0)
break;
else if(x.getKey().compareTo(key) > 0)
x = x.getLeft();
else
x = x.getRight();
}
/**
* 未找到，返回false
*/
if(x == nil)
return false;
/**
* 重新存到target中，因为后面要用x
*/
target = x;
/**
* 如果x最多只用一颗子树，则直接赋值
* 否则，需要找到x的第一个前驱节点，赋值给y
*/
if(x.getLeft() == nil || x.getRight() == nil)
y = x;
else
y = findFront(x);
/**
* 如果y的左子树不空
*/
if(y.getLeft() != nil)
x = y.getLeft();
else
x = y.getRight();
/**
* 设置x的父亲节的，即为以前y的父亲节的
*/
x.setParent(y.getParent());
/**
* 如果y是根节点，则x成为了根节点
* 否则，将x设置为y的父亲节的的子树
*/
if(y.getParent() == nil)
root = x;
else
{
if(y == y.getParent().getLeft())
y.getParent().setLeft(x);
else
y.getParent().setRight(x);
}
if(y != target)
{//copy y's data into target
target.setKey(y.getKey());
}
if(y.getColor() == Color.BALCK)
delete_fixup(x);
return true;
}
/**
* @param node
* 用于删除节点后，为了维持红黑树的性质
* 来定制的修复程序
*/
private void delete_fixup(TreeNode<T> node)
{
/*用于保存兄弟节点*/
TreeNode<T> w = null;
/*保证需要调整的节点是黑色的且不是根*/
while(node != root && node.getColor() == Color.BALCK)
{
/*一、考虑是左子树的情况*/
if(node == node.getParent().getLeft())
{
w = node.getParent().getRight();
/* 情况一：兄弟的颜色是红色的，此种情况需要其变成以下的情况二、三和四
* 因此需要将这个红色兄弟节点从右边移到左边去
* 于是将w的颜色变黑，其父节点变红，然后其父节点左旋
* 最后把w重新指向兄弟节点*/
if(w.getColor() == Color.RED)
{
w.setColor(Color.BALCK);
node.getParent().setColor(Color.RED);
left_rotate(node.getParent());
w = node.getParent().getRight();//new w
}
/* 情况二：兄弟节点为黑色而且连个孩子均为黑色，这种情况比较好办
* 因为左边少一个黑节点，而右边接连有两个，于是在右边减少一个，
* 然后把node指向其父节点，即将黑节点的需求上移
* */
if(w.getLeft().getColor() == Color.BALCK && w.getRight().getColor() == Color.BALCK)
{
w.setColor(Color.RED);
node = node.getParent();
}
/* 情况三：兄弟节点为黑色，兄弟的右孩子是黑色的，左孩子是红色的
* 情况四：兄弟节点为黑色，兄弟的右孩子是红色的
* */
else
{
/* 这个判断用于情况三，此时需要将w的左孩子颜色变为黑色，w变为
* 红色，然后右旋，w重新赋值
* 由此一来就将情况三变为情况四*/
if(w.getRight().getColor() == Color.BALCK)
{
w.getLeft().setColor(Color.BALCK);
w.setColor(Color.RED);
right_rotate(w);
w = node.getParent().getRight();
}
/* 以下是针对情况四的处理
* 可以将node的父亲的节点设置为黑色，w设置为原来node的
* 父亲节点的颜色，而且w的右孩子的颜色设置为黑色
* 然后左旋，即可将左边的黑高度加一，而右边的黑高度不变*/
w.setColor(node.getParent().getColor());
node.getParent().setColor(Color.BALCK);
w.getRight().setColor(Color.BALCK);
left_rotate(node.getParent());
node = root;//finished
}
}
/* 二、考虑是右子树的情况
* 此处跟上面的左子树情况完全对称，不详叙*/
else
{
w = node.getParent().getLeft();
if(w.getColor() == Color.RED)
{
w.setColor(Color.BALCK);
node.getParent().setColor(Color.BALCK);
right_rotate(node.getParent());
w = node.getParent().getLeft();//new w
}
if(w.getLeft().getColor() == Color.BALCK && w.getRight().getColor() == Color.BALCK)
{
w.setColor(Color.RED);
node = node.getParent();
}
else
{
if(w.getLeft().getColor() == Color.BALCK)
{
w.getRight().setColor(Color.BALCK);
w.setColor(Color.RED);
left_rotate(w);
w = node.getParent().getLeft();
}
w.setColor(node.getParent().getColor());
node.getParent().setColor(Color.BALCK);
w.getLeft().setColor(Color.BALCK);
right_rotate(node.getParent());
node = root;//finished
}
}
}
node.setColor(Color.BALCK);
}
/*
* 寻找node的前驱节点，并返回其引用*/
private TreeNode<T> findFront(TreeNode<T> node)
{
TreeNode<T> y = node;
TreeNode<T> x = node.getLeft();
while(x != nil)
{
y = x;
x = x.getRight();
}
return y;
}
/**
* @param key
* @return Object
*/
public boolean findByKey(T key)
{
return find(root,key)!=null;
}
private T find(TreeNode<T> node, T key)
{
/**
* 1，没有节点
* 2，此节点为叶子节点，则其指向nil节点，判断nil节点只需左子树或右子树为空即可
* 如果是以上情况，直接返回null，即找不到该关键字
*/
if(node == null || node == nil)// || node.getRight() == null)
return null;
/**
* 找到相等关键字，返回
*/
if(node.getKey().compareTo(key) == 0)
return node.getKey();
/**
* 在左子树上找
*/
T left = find(node.getLeft(),key);
if(left != null)
return left;
/**
* 在右子树上找
*/
T right = find(node.getRight(),key);
if(right != null)
return right;
return null;
}
/**
*
* @param order
* order = 1 先序
* order = 0 中序
* order = -1 后序
*/
public void travelTree(int order)
{
if(order == 0)
midTravel(root);//中序
else if(order == -1)
afterTravel(root);//后序
else
preTravel(root);//先序
}
/**
* 先序遍历
* @param node
*/
private void preTravel(TreeNode<T> node)
{
if( node == null || node == nil)
return ;
out.println("[ key = "+node.getKey()+" ],[ color = "+node.getColor()+" ]");
midTravel(node.getLeft());
midTravel(node.getRight());
}
/**
* 中序遍历
* @param node
*/
private void midTravel(TreeNode<T> node)
{
if( node == null || node == nil)
return ;
midTravel(node.getLeft());
out.println("[ key = "+node.getKey()+" ],[ color = "+node.getColor()+" ]");
midTravel(node.getRight());
}
/**
* 后序遍历 非递归实现
* @param node
*/
private void afterTravel(TreeNode<T> node)
{
Stack< TreeNode <T> > stack = new Stack< TreeNode<T> >();
TreeNode<T> p = null;
/**
* 记录上一个访问节点的引用，用于判断其父节点是否访问过
*/
TreeNode<T> pre = node;
while(node != nil)
{
stack.push(node);
node = node.getLeft();
}
while(stack.size() > 0)
{
p = stack.peek();
if(p.getRight() != nil && p.getRight() != pre)
{
TreeNode<T> temp = p.getRight();
while(temp != nil)
{
stack.push(temp);
temp = temp.getLeft();
}
}
else
{
p = stack.pop();
out.println("[ key = "+p.getKey()+" ],[ color = "+p.getColor()+" ]");
pre = p;
}
}
}
public String toString()
{
out.println("order is :");
travelTree(0);
return "end.";
}
}
- redblacktree.jar (5.6 KB)
- 下载次数: 0
- redblacktree.rar (11.2 KB)
- 下载次数: 0
分享到：
发表评论
相关推荐
- **树结构**：二叉树、平衡树（如AVL、红黑树）的理解和操作。 - **图算法**：Dijkstra、Floyd-Warshall、A*搜索等。 5. **系统设计**： - **微服务架构**：理解微服务设计原则，如服务发现、负载均衡、容错...
这些模板可以帮助参赛者在面对复杂问题时，迅速定位到合适的解决方案，并避免在比赛紧张的环境中重新发明轮子。 1. **排序算法**：如快速排序、归并排序、堆排序、冒泡排序、插入排序等，它们在处理大量数据的排序...
- **提高开发效率**：由于许多常见任务已经由标准库实现了，因此开发人员可以专注于解决特定问题而不是重新发明轮子。 - **增强代码质量**：标准库经过了广泛的测试和优化，因此使用标准库通常可以提高代码的质量和...
STL不仅提供了丰富的数据结构和算法，还遵循了C++的设计哲学，即“不要重复发明轮子”，让开发者能专注于解决问题本身，而不是基础工具的实现。因此，熟练掌握STL是每一位C++程序员必备的技能。
1. 容器（Containers）：如vector（动态数组）、list（双向链表）、set（红黑树实现的集合）、map（关联数组）等，它们提供了一种组织和管理数据的方式，并且提供了方便的操作接口。 2. 迭代器（Iterators）：迭代...
- **集合（Set）**：`std::set<T>` 是一个唯一元素的集合，通常基于红黑树实现，支持快速查找。 - **共享指针（shared_ptr）**：C++11引入的智能指针，用于管理动态分配的对象，自动释放内存，避免内存泄漏。 - *...
6. 容器类之间的关系：例如，set和map都是基于红黑树实现的，提供O(log n)的时间复杂度操作，而vector和deque则基于动态数组，提供连续的内存空间和快速的随机访问。了解这些容器之间的关系可以帮助我们选择最适合...