BST 二分搜索树
二分搜索树是一种二叉树型数据结构，也是平衡二叉树AVL和红黑树的基础。
什么是二分搜索树？
二分搜索树是一种二叉树型数据结构，由一个个节点构成，每一个节点4个属性，分别是：
key, 键
val, key所代表的值
left, 指向左边的节点
right，指向右边的节点
一棵二分搜索树可以用下面的图表示(其中的数字表示key，val没有表示出来):
从图中可以看出二分搜索树满足下面几个规则：
每个节点有一个左孩子，一个右孩子，左右孩子不存在则为NULL
左孩子节点.key > 右孩子节点.key
最上面的节点称为根节点，一棵二分搜索树只有一个根节点
若一个节点没有左右孩子，或者说左右孩子均为NULL，则该节点为叶子节点
额外说明，二分搜索树中key不允许重复，value可以重复
根据以上规则，很轻易看出BST的两个性质：
BST的节点的位置是有规则的，要想查询某一个节点，可以从根节点一路向下查找，若查询节点比当前节点大，则向左子树方向查找，反之则向右子树方向查找，若相等则说明找到。若一路向下找到叶子节点，仍未找到，说明该节点在BST中不存在。
最小的节点一定位于BST的左下角, 最大的节点一定位于BST的右下角。
实现BST
由上面的介绍，我们很容易写出BST的成员变量和构造方法。
public class BST<K extends Comparable<K>,V> {
private class Node{
public K key;
public V value;
public Node left,right;
public Node(K key, V value){
this.key=key;
this.value=value;
left=null;
right=null;
}
public Node(){
this.key=null;
this.value=null;
left=null;
right=null;
}
}
private Node root;
private int size;
public BST(){
root=null;
size=0;
}
}我们额外设置了一个 size变量，用来表示BST内节点个数。
BST常用方法
resize() 获取节点个数, isEmpty()判断BST是否为空
public int getSize() {
return size;
}
public boolean isEmpty() {
return size==0;
}contains(K key) 根据key值查询某一节点是否存在
public boolean contains(K key) {
return contains(root ,key);
}
private boolean contains(Node node,K key){
if (node==null){
return false;
}
if (key.compareTo(node.key)==0){
return true;
}else if (key.compareTo(node.key)<0){
return contains(node.left,key);
}else {
return contains(node.right,key);
}
}我们用到了一个public 方法 contains(K key) 传入key值，随后调用private 方法 contains(Node root, K key)从根节点开始一路向下查找。
contains(Node node, K key) 方法是一个递归方法。它首先判断传如的节点是否为NULL, 若为NULL，说明已经递归到NULL了仍未找到，return false。否则说明还有戏，接着判断key和当前节点的key是否相等，若相等说明找到了，return true。否则说明当前节点不是要找的节点，继续向左子树和右子树递归。
get(K key)根据key值获得一个节点，set(K key, V newValue)设置key值查找节点并设置节点的value
public V get(K key) {
Node retNode=getNode(root,key);
if (retNode!=null){
return retNode.value;
}else {
return null;
}
}
private Node getNode(Node node,K key) {
if (node==null){
return null;
}
if (key.compareTo(node.key)==0){
return node;
}else if (key.compareTo(node.key)<0){
return getNode(node.left,key);
}else {
return getNode(node.right,key);
}
}
public void set(K key, V newValue) {
Node setNode=getNode(root,key);
if (setNode!=null){
setNode.value=newValue;
}else{
throw new IllegalArgumentException(key + "doesn't exist!");
}
}可以看出，整个逻辑与contains(K key)几乎完全相同
minimu()寻找二分搜索树中最小的元素的节点,并返回
public Node minimum(){
return minimum(root);
}
//寻找二分搜索树中以node为根节点的最小的元素的节点,并返回
private Node minimum( Node node){
if (node.left!=null){
return minimum(node.left);
}else {
return node;
}
}public minimum()方法调用private minimum(Node node)方法。私有private minimum(Node node)方法寻找二分搜索树中以node为根节点的最小的元素的节点,并返回。private minimmum(Node node)方法不断地向左下角递归，直到达到某一个节点的左孩子为NULL，说明找到了最小节点, return返回。
add(K key, V value)向BST中加入一个指定key的val的新节点
//向二分搜索树中加入新节点
public void add(K key, V value) {
root=add(root, key,value);
}
//向以node为根的二分搜索树中加入新节点
//并且返回node
private Node add(Node node, K key, V value){
if (node==null){
size++;
return new Node(key,value);
}
//Map中不能存在相同的key, 只能修改valau
if (key.compareTo(node.key)==0){
node.value=value;
return node;
}else if (key.compareTo(node.key)<0 ){
node.left=add(node.left,key,value);
}else {
node.right=add(node.right,key,value);
}
return node;
}public add(K key, V value)方法调用 private add(Node node, K key, V value)方法向BST中加入指定key和value的节点。 private add(root, key, value)从根节点向下寻找合适的位置添加新节点。private add(Node node, K key, V value)方法也是一个递归方法，当node为NULL，说明找到了合适的位置，新创创建一个node对象，size++。否则不断比较key 和当前节点的key。若key比node.key小，向左递归; 若key比node.key大，向右递归; 若key等于node.key则视为修改当前node.value，因为BST中不允许存在重复的key。
removeMin(Node node) 删除以node为根节点的最小节点, 并返回node
//删除以node为根节点的树的最小节点,并且返回node
private Node removeMin( Node node){
if (node.left==null){
Node rightNode=node.right;
node=null;
size--;
return rightNode;
}
node.left=removeMin(node.left);
return node;
}removeMin(Node node)也是一个递归方法。首先处理递归到底的情况, 若node.left为NULL, 说明node就是最小节点，size - -，将node.right备份成rightNode, 将node指向NULL, 最后返回rightNode给父节点.left。若没有递归到底，则继续向左递归。
public V remove(K key)给定key值删除某一个节点
删除节点是BST中最复杂的操作，可能需要用到前面的minimum(Node node)方法。
删除BST 节点可以分成三类情况来讨论:
待删除节点delNode只有右孩子, 直接将delNode.right返回到 父节点.left 或 父节点.right, delNode指向NULL, size - - 即可
待删除节点delNode只有左孩子, 直接将delNode.leftt返回到 父节点.left 或 父节点.right, delNode指向NULL, size - - 即可
待删除节点delNode既有左孩子，也有右孩子，需要将 以delNode.right为根节点的子树中最小节点(也称successor后继节点)移到 delNode的位置替代delNode，
第三种情况也就是最复杂的情况，用图表示如下:
根据上面所说，可以写出 remove(K key)方法
public V remove(K key) {
Node delNode=getNode(root,key);
if (delNode!=null){
root=remove(root,key);
return delNode.value;
}else {
return null;
}
}
//从以node为根节点的子树中删除,并返回node
private Node remove(Node node, K key){
//需要删除的节点不存在, return NULL
if (node==null){
return null;
}
if (key.compareTo(node.key)<0){
node.left=remove(node.left,key);
return node;
}else if (key.compareTo(node.key)>0){
node.right=remove(node.right,key);
return node;
}else {//e==node.e
if (node.left==null){
Node rightNode=node.right;
node=null;
size--;
return rightNode;
}else if (node.right==null){
Node leftNode=node.left;
node=null;
size--;
return leftNode;
}else {
Node successor=minimum(node.right);
successor.right=removeMin(node.right);//已经size--了
successor.left=node.left;
node=null;
return successor;
}
}
}至此，我们已经实现了一个二分搜索树的所有重要功能。二分搜索树一般不会单独暴露给用户，而是以 Map (称为映射或字典) 或 Set (称为集合)的方式给用户调用。后面将会讲解如何用二分搜索树实现一个Map 和一个Set.
Last updated
Was this helpful?