树结构——二叉查找树
2017-07-13 本文已影响37人
zxcvbnmzsedr
定义
二叉查找树，也称二叉搜索树、有序二叉树（英语：ordered binary tree），排序二叉树（英语：sorted binary tree），是指一棵空树或者具有下列性质的二叉树：
- 若任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
- 若任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
- 任意节点的左、右子树也分别为二叉查找树；
- 没有键值相等的节点。
删除一个有左、右子树的节点
先弄出一个二叉树的叶子
private static class BinaryNode<K,V> {
K key; // 键
V value; // 值
BinaryNode<K,V> left; // 左子树
BinaryNode<K,V> right; // 右子树
BinaryNode(K key,V value) {
this(key,value, null, null);
}
BinaryNode(K key,V value, BinaryNode<K,V> left, BinaryNode<K,V> right) {
this.key = key;
this.value = value;
this.left = left;
this.right = right;
}
}
插入算法
向一个二元搜寻树b中插入一个节点s的算法，过程为：
- 若b是空树，则将s所指结点作为根节点插入，否则：
- 若s->data等于b的根节点的数据域之值，则返回，否则：
- 若s->data小于b的根节点的数据域之值，则把s所指节点插入到左子树中，否则：
- 把s所指节点插入到右子树中。（新插入节点总是叶子节点）
private BinaryNode insert(K key,V value,BinaryNode<K,V> node){
// 如果根为空，则直接把传进来的建值作为树的根
if(node == null){
return new BinaryNode(key,value);
}
// 比较树根和将要成为叶子的值
int result = compare(key,node.key);
// 节点值比根小，将节点插入左子树，否则插入右子树
if(result<0){
node.left = insert(key,value,node.left);
}else if(result > 0){
node.right = insert(key,value,node.right);
}
return node;
}
final int compare(Object k1, Object k2) {
return comparator==null ? ((Comparable<? super K>)k1).compareTo((K)k2)
: comparator.compare((K)k1, (K)k2);
}
查找算法
在二元搜寻树b中查找x的过程为：
- 若b是空树，则搜索失败，否则：
- 若x等于b的根节点的数据域之值，则查找成功；否则：
- 若x小于b的根节点的数据域之值，则搜索左子树；否则：
- 查找右子树。
private BinaryNode<K, V> getEntry(K key) {
if(key == null){
throw new NullPointerException();
}
BinarySearchTree.BinaryNode<K,V> p = rootTree;
while (p != null){
// 比较树根和和传入的key
int cmp = compare(key,p.key);
// 节点值比根小，则查找左子树，否则查找右子树
if(cmp < 0)
p = p.left;
else if (cmp > 0)
p = p.right;
else
return p;
}
return null;
}
删除算法
- 若*p结点为叶子结点，即PL（左子树）和PR（右子树）均为空树。由于删去叶子结点不破坏整棵树的结构，则只需修改其双亲结点的指针即可。
- 若p结点只有左子树PL或右子树PR，此时只要令PL或PR直接成为其双亲结点f的左子树（当p是左子树）或右子树（当p是右子树）即可，作此修改也不破坏二叉查找树的特性。
- 若p结点的左子树和右子树均不空。在删去p之后，为保持其它元素之间的相对位置不变，可按中序遍历保持有序进行调整，可以有两种做法：其一是令p的左子树为f的左/右（依p是f的左子树还是右子树而定）子树，s为p左子树的最右下的结点，而p的右子树为s的右子树；其二是令p的直接前驱（in-order predecessor）或直接后继（in-order successor）替代p，然后再从二叉查找树中删去它的直接前驱（或直接后继）。
private BinaryNode<K, V> deleteEntry(K key, BinaryNode<K, V> node) {
if (node == null) {
return node;
}
int result = compare(key, node.key);
if (result < 0) {
// 存在左子树
node.left = deleteEntry(key, node.left);
} else if (result > 0) {
// 存在右子树
node.right = deleteEntry(key, node.right);
} else if (node.left != null && node.right != null) {
/**
* 这边删除可以有两种方式，一种是找到右子树的最左节点，还有一种是找到左子树的最右节点
* 然后把要删除的节点替换掉
* node.key = findMax(node.left).key;
* node.value = findMax(node.left).value;
* node.left = deleteEntry(node.key, node.left);
*/
// 找到右子树的左边最小节点把要删除的节点替换掉
node.key = findMin(node.right).key;
node.value = findMin(node.right).value;
// 替换掉之后将节点删除
node.right = deleteEntry(node.key, node.right);
} else
node = (node.left != null) ? node.left : node.right;
return node;
}
二叉查找树的弊端
最坏情况下，当先后插入的关键字有序时，构成的二叉查找树蜕变为单支树，这个时候复杂度会退化成O(n)
完整代码
/**
* Created by tianzeng on 2017/5/13.
* 二叉查找树
* 1. 若任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
* 2. 若任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
* 3. 任意节点的左、右子树也分别为二叉查找树；
* 4. 没有键值相等的节点
*/
public class BinarySearchTree<K, V> {
/**
* 节点的数据结构
*/
private static class BinaryNode<K, V> {
K key;
V value;
BinaryNode<K, V> left;
BinaryNode<K, V> right;
BinaryNode(K key, V value) {
this(key, value, null, null);
}
BinaryNode(K key, V value, BinaryNode<K, V> left, BinaryNode<K, V> right) {
this.key = key;
this.value = value;
this.left = left;
this.right = right;
}
}
private BinaryNode rootTree; //
private final Comparator<? super K> comparator;
/**
* 构造一个空的二叉查找树
*/
public BinarySearchTree() {
this.comparator = null;
rootTree = null;
}
public BinarySearchTree(Comparator<? super K> comparator) {
this.comparator = comparator;
}
/**
* 清空二叉查找树
*/
public void clear() {
rootTree = null;
}
/**
* 判断二叉树是否为空
*/
public boolean isEmpty() {
return rootTree == null;
}
final int compare(Object k1, Object k2) {
return comparator == null ? ((Comparable<? super K>) k1).compareTo((K) k2)
: comparator.compare((K) k1, (K) k2);
}
/**
* 插入元素
*/
public void put(K key, V value) {
rootTree = insert(key, value, rootTree);
}
/**
* 插入元素
*/
private BinaryNode insert(K key, V value, BinaryNode<K, V> node) {
// 如果根为空
if (node == null) {
return new BinaryNode(key, value);
}
int result = compare(key, node.key);
// 节点值比根小，左子树
if (result < 0) {
node.left = insert(key, value, node.left);
} else if (result > 0) {
node.right = insert(key, value, node.right);
}
return node;
}
/**
* 查找元素
*/
public V get(K key) {
BinarySearchTree.BinaryNode<K, V> p = getEntry(key);
return (p == null ? null : p.value);
}
private BinaryNode<K, V> getEntry(K key) {
if (key == null) {
throw new NullPointerException();
}
BinarySearchTree.BinaryNode<K, V> p = rootTree;
while (p != null) {
int cmp = compare(key, p.key);
if (cmp < 0)
p = p.left;
else if (cmp > 0)
p = p.right;
else
return p;
}
return null;
}
public void remove(K key) {
rootTree = deleteEntry(key, rootTree);
}
/**
* 寻找该节点的最小节点
*/
BinaryNode<K,V> findMin(BinaryNode<K, V> node){
if(node == null){
return null;
}else if(node.left == null){
return node;
}
return findMin(node.left);
}
BinaryNode<K,V> findMax(BinaryNode<K, V> node){
if(node == null){
return null;
}else if(node.right == null){
return node;
}
return findMax(node.right);
}
private BinaryNode<K, V> deleteEntry(K key, BinaryNode<K, V> node) {
if (node == null) {
return node;
}
int result = compare(key, node.key);
if (result < 0) {
// 存在左子树
node.left = deleteEntry(key, node.left);
} else if (result > 0) {
// 存在右子树
node.right = deleteEntry(key, node.right);
} else if (node.left != null && node.right != null) {
/**
* node.key = findMax(node.left).key;
* node.value = findMax(node.left).value;
* node.left = deleteEntry(node.key, node.left);
*/
// 找到右子树的左边最小节点把要删除的节点替换掉
node.key = findMin(node.right).key;
node.value = findMin(node.right).value;
// 替换掉之后将节点删除
node.right = deleteEntry(node.key, node.right);
} else
node = (node.left != null) ? node.left : node.right;
return node;
}
public void print(){
print(rootTree);
}
public void print(BinaryNode root) {
if (root == null) {
return;
}
List<BinaryNode> list = new LinkedList<>();
BinaryNode node;
// 当前层的结点个数
int current = 1;
// 记录下一层的结点个数
int next = 0;
list.add(root);
while (list.size() > 0) {
node = list.remove(0);
current--;
System.out.printf("%-3s", node.value);
if (node.left != null) {
list.add(node.left);
next++;
}
if (node.right != null) {
list.add(node.right);
next++;
}
if (current ==0) {
System.out.println();
current = next;
next = 0;
}
}
}
}
测试：
