leon_a
- 浏览: 79021 次
- 性别:
- 来自: 拜月神教
-
最新评论
-
huangfenghit：
你绝对的大牛~
答复: 阿里巴巴面试感言 -
liuxuejin：
好！慢慢下载来看看
区间树 -
xiaobian：
看不懂，怎么知道是讲的好呢 ？
数据挖掘 决策树ID3算法原理 -
longay00：
不错，很牛，不过没有原理与实验很难相信它的正确性。从代码上看， ...
决策树C4.5算法 -
yangguo：
用我的study方法就可以了。
答复: java最优算法讨论
package acmcode;
/**
* @author Leon.Chen
*
*/
public class IntervalTree {
/**
* 红
*/
private static final String RED = "red";
/**
* 黑
*/
private static final String BLACK = "black";
/**
* 根节点
*/
private RBNode root;
/**
* 左旋转
*
* @param x
*/
private void leftRotate(RBNode x) {
RBNode y = x.right;
x.right = y.left;
y.left.parent = x;
x.setMinPointAndMaxPoint();
y.parent = x.parent;
if (x.parent == null) {
root = y;
} else {
if (x == x.parent.left) {
x.parent.left = y;
} else {
x.parent.right = y;
}
}
y.left = x;
x.parent = y;
y.setMinPointAndMaxPoint();
}
/**
* 右旋转
*
* @param y
*/
private void rightRotate(RBNode y) {
RBNode x = y.left;
y.left = x.right;
x.right.parent = y;
y.setMinPointAndMaxPoint();
x.parent = y.parent;
if (y.parent == null) {
root = x;
} else {
if (y == y.parent.left) {
y.parent.left = x;
} else {
y.parent.right = x;
}
}
x.right = y;
y.parent = x;
x.setMinPointAndMaxPoint();
}
/**
* 红黑树插入方法
*
* @param z
*/
public void RBInsert(RBNode z) {
if (root == null) {
root = z;
root.color = BLACK;
root.setMinPointAndMaxPoint(z);
} else {
RBNode x = root;
RBNode y = null;
while (isNotNilNode(x)) {
y = x;
x.setMinPointAndMaxPoint(z);
if (z.value.compareTo(x.value) < 0) {
x = x.left;
} else {
x = x.right;
}
}
if (z.value.compareTo(y.value) < 0) {
y.left = z;
} else {
y.right = z;
}
z.color = RED;
z.setMinPointAndMaxPoint(z);
z.parent = y;
}
z.left = new RBNode(BLACK);
z.right = new RBNode(BLACK);
RBInsertFixUp(z);
}
/**
* 解决插入冲突
*
* @param z
*/
private void RBInsertFixUp(RBNode z) {
while (z.parent != null && z.parent.color.equals(RED)) {
if (z.parent == z.parent.parent.left) {
RBNode y = z.parent.parent.right;
if (y.color.equals(RED)) {
z.parent.color = BLACK;
y.color = BLACK;
z.parent.parent.color = RED;
z = z.parent.parent;
} else if (z == z.parent.right) {
z = z.parent;
leftRotate(z);
} else if (z == z.parent.left) {
z.parent.color = BLACK;
z.parent.parent.color = RED;
rightRotate(z.parent.parent);
}
} else {
RBNode y = z.parent.parent.left;
if (y.color.equals(RED)) {
z.parent.color = BLACK;
y.color = BLACK;
z.parent.parent.color = RED;
z = z.parent.parent;
} else if (z == z.parent.left) {
z = z.parent;
rightRotate(z);
} else if (z == z.parent.right) {
z.parent.color = BLACK;
z.parent.parent.color = RED;
leftRotate(z.parent.parent);
}
}
}
root.color = BLACK;
}
/**
* @param deleteNode
*/
public void RBDelete(RBNode deleteNode) {
RBNode y = null;
RBNode z = serach(deleteNode.value);
if (isNilNode(z.left) || isNilNode(z.right)) {
y = z;
} else {
y = treeSuccessor(z);
}
RBNode x = null;
if (isNotNilNode(y.left)) {
x = y.left;
} else {
x = y.right;
}
x.parent = y.parent;
if (isNilNode(y.parent)) {
root = x;
} else {
if (y == y.parent.left) {
y.parent.left = x;
} else {
y.parent.right = x;
}
}
if (y != z) {
z.value = y.value;
}
if (y.color.equals(BLACK)) {
RBDeleteFixUp(x);
}
}
/**
* @param x
*/
private void RBDeleteFixUp(RBNode x) {
// 解决黑黑冲突,完善中
while (x != root && x.color.equals(BLACK)) {
if (x == x.parent.left) {
RBNode w = x.parent.right;
if (w.color.equals(RED)) {
w.color = BLACK;
x.parent.color = RED;
leftRotate(x.parent);
w = x.parent.right;
} else if (w.left.color.equals(BLACK) && w.right.color.equals(BLACK)) {
w.color = RED;
x = x.parent;
} else if (w.right.color.equals(BLACK)) {
w.left.color = BLACK;
w.color = RED;
rightRotate(w);
w = x.parent.right;
} else if (w.left.color.equals(BLACK)) {
w.color = x.parent.color;
x.parent.color = BLACK;
w.right.color = BLACK;
leftRotate(x.parent);
x = root;
}
} else {
RBNode w = x.parent.left;
if (w.color.equals(RED)) {
w.color = BLACK;
x.parent.color = RED;
rightRotate(x.parent);
w = x.parent.left;
} else if (w.left.color.equals(BLACK) && w.right.color.equals(BLACK)) {
w.color = RED;
x = x.parent;
} else if (w.left.color.equals(BLACK)) {
w.right.color = BLACK;
w.color = RED;
leftRotate(w);
w = x.parent.left;
} else if (w.right.color.equals(BLACK)) {
w.color = x.parent.color;
x.parent.color = BLACK;
w.left.color = BLACK;
rightRotate(x.parent);
x = root;
}
}
}
x.color = BLACK;
}
/**
* 找后继
*
* @param node
* @return RBNode
*/
public RBNode treeSuccessor(RBNode node) {
if (node.right != null) {
return treeMiniMum(node.right);
}
RBNode currentNode = getParentNode(node);
while (currentNode != null && node == currentNode.right) {
node = currentNode;
currentNode = getParentNode(node);
}
return currentNode;
}
/**
* 找前驱
*
* @param node
* @return RBNode
*/
public RBNode treePrecursor(RBNode node) {
if (node.left != null) {
return treeMaxiMum(node.left);
}
RBNode currentNode = getParentNode(node);
while (currentNode != null && node == currentNode.left) {
node = currentNode;
currentNode = getParentNode(node);
}
return currentNode;
}
/**
* 最大节点
*
* @param node
* @return RBNode
*/
public RBNode treeMaxiMum(RBNode node) {
while (isNotNilNode(node.right)) {
node = node.right;
}
return node;
}
/**
* 最小节点
*
* @param node
* @return RBNode
*/
public RBNode treeMiniMum(RBNode node) {
while (isNotNilNode(node.left)) {
node = node.left;
}
return node;
}
/**
* 找节点的父节点
*
* @param node
* @return TreeNode
*/
public RBNode getParentNode(RBNode node) {
RBNode current = root;
RBNode trailCurrent = null;
while (isNotNilNode(current)) {
if (current.value.compareTo(node.value) == 0) {
break;
}
trailCurrent = current;
if (node.value.compareTo(current.value) < 0) {
current = current.left;
} else {
current = current.right;
}
}
return trailCurrent;
}
/**
* 搜索
*
* @param value
* @return TreeNode
*/
public RBNode serach(RBValue value) {
return treeSerach(root, value);
}
/**
* 搜索
*
* @param node
* @param value
* @return TreeNode
*/
public RBNode treeSerach(RBNode node, RBValue value) {
if (isNotNilNode(node) && node.value.compareTo(value) == 0) {
return node;
}
if (value.compareTo(node.value) < 0) {
return treeSerach(node.left, value);
} else {
return treeSerach(node.right, value);
}
}
/**
* 中序遍历
*
* @param node
*/
public void inOrder(RBNode node) {
if (isNotNilNode(node)) {
inOrder(node.left);
System.out.println(node.value+","+node.color);
inOrder(node.right);
}
}
/**
* 先序遍历
*
* @param node
*/
public void perOrder(RBNode node) {
if (isNotNilNode(node)) {
System.out.println(node.value+","+node.color);
perOrder(node.left);
perOrder(node.right);
}
}
/**
* @param node
* @return 是否为NIL[T]节点
*/
private boolean isNotNilNode(RBNode node) {
return node != null && node.value != null;
}
/**
* @param node
* @return 是否为NIL[T]节点
*/
private boolean isNilNode(RBNode node) {
return !isNotNilNode(node);
}
/**
* @param args
*/
public static void main(String[] args) {
IntervalTree tree = new IntervalTree();
tree.RBInsert(new RBNode(new RBValue(0,3)));
tree.RBInsert(new RBNode(new RBValue(5,8)));
tree.RBInsert(new RBNode(new RBValue(6,10)));
tree.RBInsert(new RBNode(new RBValue(8,9)));
tree.RBInsert(new RBNode(new RBValue(15,23)));
tree.RBInsert(new RBNode(new RBValue(16,21)));
tree.RBInsert(new RBNode(new RBValue(17,19)));
tree.RBInsert(new RBNode(new RBValue(19,20)));
tree.RBInsert(new RBNode(new RBValue(25,30)));
tree.RBInsert(new RBNode(new RBValue(26,26)));
System.out.println("=================");
System.out.println("root = "+tree.root.value);
System.out.println("=================");
tree.inOrder(tree.root);
System.out.println("=================");
tree.perOrder(tree.root);
}
}
package acmcode;
/**
* @author Leon.Chen
*
*/
public class RBNode {
/**
*
*/
public RBNode parent;
/**
*
*/
public RBNode left;
/**
*
*/
public RBNode right;
/**
*
*/
public RBValue value;
/**
*
*/
public String color;
/**
* @param color
*/
public RBNode(String color) {
this.color = color;
}
/**
*
*/
public RBNode() {
}
/**
* @param value
*/
public RBNode(RBValue value) {
this.value = value;
}
/**
* @param node
*/
public void setMinPointAndMaxPoint(RBNode node) {
if(node.value.startPoint<this.value.minPoint) {
this.value.minPoint = node.value.startPoint;
}
if(node.value.endPoint>this.value.maxPoint) {
this.value.maxPoint = node.value.endPoint;
}
}
/**
*
*/
public void setMinPointAndMaxPoint() {
int min = 0;
int max = 0;
if (this.left.value == null && this.right.value == null) {
min = this.value.startPoint;
max = this.value.endPoint;
} else {
min = getMin();
max = getMax();
}
this.value.minPoint = min;
this.value.maxPoint = max;
}
/**
* @return min
*/
private int getMin() {
RBNode left = this.left;
RBNode right = this.right;
int temp = getMin(left,right);
if(this.value.startPoint > temp) {
return temp;
}
return this.value.startPoint;
}
/**
* @return max
*/
private int getMax() {
RBNode left = this.left;
RBNode right = this.right;
int temp = getMax(left,right);
if(this.value.endPoint >temp) {
return this.value.endPoint;
}
return temp;
}
/**
* @param node1
* @param node2
* @return min
*/
private int getMin(RBNode node1, RBNode node2) {
if (node1.value == null && node2.value == null) {
return 2147483647;
}
if (node1.value == null) {
return node2.value.minPoint;
}
if (node2.value == null) {
return node1.value.minPoint;
}
return (node1.value.minPoint < node2.value.minPoint ? node1.value.minPoint : node2.value.minPoint);
}
/**
* @param node1
* @param node2
* @return max
*/
private int getMax(RBNode node1, RBNode node2) {
if (node1.value == null && node2.value == null) {
return 0;
}
if (node1.value == null) {
return node2.value.maxPoint;
}
if (node2.value == null) {
return node1.value.maxPoint;
}
return (node1.value.maxPoint < node2.value.maxPoint ? node2.value.maxPoint : node1.value.maxPoint);
}
}
package acmcode;
/**
* @author Leon.Chen
*
*/
public class RBValue {
/**
*
*/
public int startPoint;
/**
*
*/
public int endPoint;
/**
* 初始化minPoint为无穷大
*/
public int minPoint = 2147483647;
/**
*
*/
public int maxPoint;
/**
* @param startPoint
* @param endPoint
*/
public RBValue(int startPoint, int endPoint) {
this.startPoint = startPoint;
this.endPoint = endPoint;
}
/**
* @param otherValue
* @return 比较结果
*/
public int compareTo(RBValue otherValue) {
int thisVal = this.startPoint;
int anotherVal = otherValue.startPoint;
return (thisVal < anotherVal ? -1 : (thisVal == anotherVal ? 0 : 1));
}
public String toString() {
return "[" + startPoint + "," + endPoint + "]" + " , [" + minPoint + "," + maxPoint + "]";
}
}
1
顶
顶
1
踩
踩
分享到：
发表评论
-
庞果英雄会 覆盖数字
2013-11-14 15:13 856庞果覆盖数字原题如下 给定整数区间[a,b]和整数区间[x, ... -
2-3 tree
2013-10-09 17:10 771package com.leon.cc; imp ... -
编译原理生成LL1预测分析表
2013-08-11 20:47 5849package com.leon; impo ... -
应用倍增法后缀数组以及RMQ求解N个字符串最长公共子串问题
2011-11-30 16:35 1464/** * @see IOI2009国家集训队论文《后 ... -
谷哥的KOF连招问题
2010-10-09 14:38 1532传说问题是这样的 玩过KOF（拳皇）的人都知道，玩的时候会连招 ... -
KOF
2010-10-09 00:13 0package org.struct.trietree; ... -
ACM/ICPC HDU 1195
2010-09-06 10:37 1897本年度还有8篇博客需要完成 开篇前附加一个看完《盗梦空间》的我 ... -
答复: 阿里巴巴面试感言
2009-10-09 22:27 2185好吧，我承认我闲的蛋疼 问题：3000万条的记录取最大的前50 ... -
正向最大匹配改进算法
2009-05-26 22:11 5892AD.： 2年J2EE经验，熟悉常用数据结构算法，熟悉常 ... -
决策树C4.5算法
2009-05-19 02:05 5257数据挖掘中决策树C4.5预测算法实现(半成品，还要写规则后 ... -
红黑树初版
2008-07-16 17:20 1609package acmcode; /** * R ... -
四则运算的中缀转后缀，逆波兰表达式求值
2008-04-23 23:10 9086首先描述问题 给定一 ... -
最大0，1子矩阵
2008-04-20 21:16 6087首先描述一下问题 /** * * 时间限制(普 ... -
数据挖掘 决策树ID3算法原理
2008-04-11 22:24 11413上一篇博客写了ID3算法的简单实现 这一篇讲讲ID3的原理 写 ... -
决策树ID3算法
2008-04-01 22:18 7606算了,还是自己修正一个BUG.... package gr ... -
ext2.0 的XMLWriter
2008-02-20 21:04 1285做ext相关的一个example项目,把我们的客户端移植成ex ... -
树与哈夫曼树
2008-02-20 20:50 1593package tree; public ... -
LCS与图算法
2008-02-20 20:46 1235求两个字符串最长公共子串的问题。大体解法是用一个矩阵来记录两个 ... -
《程序员》算法擂台：骑士聚会
2008-02-20 20:40 1217在8×8的棋盘上分布着n个骑士，他们想约在某一个格中聚会。骑士 ...
相关推荐
区间树是一种数据结构，主要用于高效地处理一系列区间查询和操作，比如查找与特定点相交的区间、查找覆盖某一区间的最小区间等。在计算机科学中，它在图形学、数据库、调度算法等多个领域有广泛应用。这个压缩包文件...
由红黑树实现区间树算法，实现去检查找，和最小区间的确定。 区间树上的重叠区间查找算法:通过增加树结点的信息域将红黑树扩张为区间树，并通过给定的某个区间i，查找区间树上相应的重叠区间。 这是一个用c++语言...
区间树是一种数据结构，特别设计用于高效地处理区间或段上的查询和操作。在这个场景下，"重叠区间查找算法"是指在一组区间中找出与给定区间有重叠的区间集合。区间树通过分割区间并将其存储在二叉树结构中，允许我们...
红黑树和区间树是两种在计算机科学中广泛使用的数据结构，主要应用于高效的数据管理和查询。在本实验中，我们探讨了如何用C++来实现这两种数据结构，并提供了相关的可视化功能。 红黑树是一种自平衡二叉查找树，由...
算法导论，在红黑树的基础上扩张出区间树的数据结构，并且构造区间树的重叠区间查找算法。
### 中科大区间树查找报告知识点解析 #### 一、区间树的基本概念 区间树是一种特殊的二叉搜索树，主要用于存储一系列区间，并支持快速查询这些区间中与指定区间重叠的所有区间。它在数据结构中属于较为高级的一种...
本文讨论的区间树查询算法，是在平面内线段均与坐标轴平行的理想的情况下，采用几何分析的方法，通过构造空间复杂度为O(n)的便于搜索的区间树，能够在O(log n + k)(k为所有报告出的线段数量）的时间内，完成与坐标轴...
红黑树和区间树是两种在计算机科学中广泛使用的数据结构，主要应用于高效的数据存储和检索。它们在算法和数据结构领域具有重要地位，尤其在处理动态集合或需要快速查找和更新操作的问题时。 首先，我们来详细了解...
区间树上的重叠区间查找算法：构造1000个节点的区间树，查找具有最小低端点的重叠区间。亲测VS可运行，VC不能运行是因为不支持操作符重载。
区间树的实现
区间树上重叠区间查找 本次试验是在红黑树的基础上扩展数据结构
实验进行的是区间树的查询操作，参照的是《算法导论》中关于区间树的描述，在红黑树的基础上加以改造实现，采用的是c++。代码已经过测试可用
本文将深入探讨标题“c.rar_c++区间树_区间树”所涵盖的几个重要知识点：区间树、红黑树、二分查找、多种排序算法以及快速矩阵运算。这些知识点在实际编程中有着广泛的应用，尤其是在数据结构和算法设计中。 1. **...
区间树的数据结构通常基于二叉树，每个节点除了保存区间的相关信息外，还可能需要额外的信息来支持查询操作，如最大结束点等。 #### 2.4 运行结果 运行结果应展示了区间树的构建过程以及查询操作的结果。 #### ...
区间树是一种数据结构，主要用来高效地处理一系列区间上的查询，包括查找、插入和删除操作。在计算机科学中，特别是算法和数据结构领域，区间树是解决区间重叠问题的有效工具。标题“overlap-interval-.zip_interval...
区间树是一种高效的数据结构，常用于处理动态区间查询和更新问题。在给定的题目描述中，区间树被用来解决一个数列的单点修改和区间求和问题。以下是关于区间树及其应用的详细解释： **1. 区间树的基本概念** 区间树...
扩充的数据结构、动态有序统计和区间树》 本课程笔记主要探讨了计算机科学中的重要概念——数据结构的扩展、动态有序统计以及区间树。这些主题在算法设计和分析中起着至关重要的作用，特别是在处理大量数据时。以下...
区间树上重叠区间查找算法.doc
区间树（interval tree）是一种对动态集合进行维护的扩张红黑树，因此可在实验二红黑树的基础上进行扩张。为此，本实验（实验三）在实验二的基础上对红黑树的节点增加新的附加信息，并设计新的操作。从而熟悉并实现...
**Pascal 区间线段树详解** 线段树（Segment Tree）是一种数据结构，用于高效地处理数组或序列上的区间查询与修改操作。在Pascal编程语言中，我们可以使用记录（Record）类型来实现一个区间线段树。以下是基于给定...