【树结构】二叉搜索树

以你之姓@ 2022-07-13 11:26 192阅读 0赞

### 二叉搜索树 ###

*  二叉搜索树定义
 *  二叉搜索树BST的优点以及缺点
 *  二叉搜索树的Java实现
 *   *  1.结点的数据结构的定义
     *  2. 计算二叉排序树的size
     *  3. 查找和插入
     *  4. 最大键和最小键的实现
     *  5. Key值向下取整和向上取整
     *  6. 获取排名
     *  7. 删除最小键值和最大键值的结点。
     *  8. 删除任意结点
 *  二叉搜索树的 golang 实现

# 二叉搜索树定义 #

先来说说这个二叉排序树的定义和性质：

> 定义：二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：  
> （1）若左子树不空，则左子树上所有结点的键值均小于或等于它的根结点的键值；  
> （2）若右子树不空，则右子树上所有结点的键值均大于或等于它的根结点的键值；  
> （3）左、右子树也分别为二叉排序树；  
> （4）节点的Key唯一

# 二叉搜索树BST的优点以及缺点 #

根据BST的定义和中序遍历(左根右节点遍历顺序)可得出，对于二叉搜索树的中序遍历可以使得节点有序。

BST的优点对于dictionary来说，主要优点就是使得查找速度大大提升，不用再进行遍历操作。时间复杂度一般情况下是O(logn)，但是最坏的情况下会出现“链表”的形式，复杂度退化到O(N)，比如下所示

11
     \
      13
       \
        15
         \
          17

当然也有基于BST优化出的各种平衡树，来保证时间复杂度O(logn)的稳定性。

# 二叉搜索树的Java实现 #

下面的代码将用java实现，并且全部基于递归实现(非递归算法复杂一些且效率高)。主要讨论BST的如下操作：  
查找、插入、最大键、最小键、向上取整、向下取整、排名k的键、获取键key的排名、删除最大最小键、删除操作、范围查找。

## 1.结点的数据结构的定义 ##

下面是BST(后文都用BST表示二叉排序树)中结点的数据结构的定义。

private class Node{ 
        private Key key;//键
        private Value value;//值
        private Node left, right;//指向子树的链接:包括左子树和右子树.
        private int N;//以当前节点为根的子树的结点总数
    //构造器
        public Node(Key key, Value value, int N) { 
            this.key = key;
            this.value = value;
            this.N = N;
        }
    }

此外，对于整个二叉查找树来说，有一个根节点，所以在BST类中定义了一个根结点：

private Node root;//二叉查找树的根节点

## 2. 计算二叉排序树的size ##

思想: 根据我们数据结构Node中的定义，里面有一个属性 N 表示的就是以当前节点为根的子树的结点总数。所以源码如下：

/** * 获取整个二叉查找树的大小 * @return */
    public int size(){ 
        return size(root);
    }
    /** * 获取某一个结点为根结点的二叉查找树的大小 * @param x * @return */
    private int size(Node x){ 
        if(x == null){ 
            return 0;
        } else { 
            return x.N;
        }
    }

## 3. 查找和插入 ##

在实现BST类的时候，BST继承自Comparable接口的，实现compareTo()函数。因为我们知道二叉查找树的键值是有有序的，左子树小于根节点，右子树大于根节点。所以实现Comparable接口，那么我们就很容易根据key找到插入的位置，而且对于BTS来说，插入的位置都是在叶子节点处。对于插入和查找都是基于键值的比较。下面是源码：

/** * 查找：通过key获取value * @param key * @return */
    public Value get(Key key){ 
        return get(root, key);
    }
    /** * 在以 x 为根节点的子树中查找并返回Key所对应的值,如果找不到就返回null * 递归实现 * @param x * @param key * @return */
    private Value get(Node x, Key key){ 
        if(x == null){ 
            return null;
        }
    	//键值的比较
        int cmp = key.compareTo(x.key);
        if(cmp<0){ 
            return get(x.left, key);
        }else if(cmp>0){ 
            return get(x.right, key);
        } else{ 
            return x.value;
        }
    }
    
    
    /** * 插入：设置键值对 * @param key * @param value */
    public void put(Key key, Value value){ 
        root = put(root, key, value);
    }
    /** * key如果存在以 x 为根节点的子树中,则更新它的值; * 否则将key与value键值对插入并创建一个新的结点. * @param x * @param key * @param value * @return */
    private Node put(Node x, Key key, Value value){ 
        if( x==null ){ 
            x = new Node(key, value, 1);
            return x;
        }
        int cmp = key.compareTo(x.key);
        if(cmp<0){ 
            x.left = put(x.left, key, value);
        }else if(cmp>0){ 
            x.right = put(x.right, key, value);
        } else{ 
            x.value=value;//更新value的值
        }
        //设置根节点的N属性
        x.N = size(x.left) + size(x.right) + 1;
    
        return x;
    }

## 4. 最大键和最小键的实现 ##

求BST中的最大键值和最小键值。根据BSt的特性，其实原理很简单：最小值就是最左下边的一个节点。最大键值就是最右下边的结点。源码如下：

/** * 最小键 */
    public Key min(){ 
        return min(root).key;
    }
    /** * 返回结点x为root的二叉排序树中最小key值的Node * @param x * @return 返回树的最小key的结点 */
    private Node min(Node x){ 
        if(x.left == null){ 
            return x;
        }else{ 
            return min(x.left);
        }
    }
    
    /** * 最大键 */
    public Key max(){ 
        return max(root).key;
    }
    /** * 返回结点x为root的二叉排序树中最大key值的Node * @param x * @return */
    private Node max(Node x){ 
        if(x.right == null){ //右子树为空,则根节点是最大的
            return x;
        }else{ 
            return max(x.right);
        }
    }

## 5. Key值向下取整和向上取整 ##

所谓的向下取整和向上取整，就是给定键值key，向下取整的意思就是找出小于等于当前key的的Key值。向上取整的意思就是找出大于等于当前key的的Key值。实现也是基于Comparable接口的，具体的源码如下：

/** * key向下取整 */
    public Key floor(Key key){ 
        Node x = floor(root, key);
        if(x == null){ 
            return null;
        }
        return x.key;
    }
    /** * 以x 为根节点的二叉排序树,查找以参数key的向下取整的Node * @param x * @param key * @return */
    private Node floor(Node x, Key key){ 
        if(x == null){ 
            return null;
        }
    
        int cmp = key.compareTo(x.key);
        if(cmp == 0){ 
            return x;
        }
        if(cmp < 0){ //说明key参数小于x结点的key,所以向下取整结点在左子树
            return floor(x.left, key);
        }
        //向下取整在右子树,
        Node t = floor(x.right, key);
        if( t!= null){ 
            return t;
        }else { 
            return x;
        }
    }
    
    /** * key向上取整 */
    public Key ceiling(Key key){ 
        Node x = ceiling(root, key);
        if(x == null){ 
            return null;
        }
        return x.key;
    }
    /** * 以x 为根节点的二叉排序树,查找以参数key的向上取整的Node * @param x * @param key * @return */
    private Node ceiling(Node x, Key key){ 
        if(x == null){ 
            return null;
        }
    
        int cmp = key.compareTo(x.key);
        if(cmp == 0){ 
            return x;
        }
        if(cmp > 0){ //说明key参数大于x结点的key,所以向上取整结点在右子树
            return ceiling(x.right, key);
        }
        //向上取整在左子树,
        Node t = ceiling(x.left, key);
        if( t!= null){ 
            return t;
        }else { 
            return x;
        }
    }

## 6. 获取排名 ##

我们经常可能会遇到需要获取到排名为k的结点或则获取某一个结点的排名，具体的实现也是基于Comparable接口的比较。

/** * 排名为k的结点的key */
    public Key select(int k){ 
        Node x = select(root, k);
        if(x == null){ 
            return null;
        }
        return x.key;
    }
    /** * 返回排名为k的结点 * @param x 根节点 * @param k 排名 * @return */
    private Node select(Node x, int k){ 
        if(x == null){ 
            return null;
        }
        int t = size(x.left);//获取左子树的节点数
        if(t == k) { //左子树节点数和k相同
            return x.left ;
        } else if( t+1 == k ){ //左子树结点数比k小一.
            return x;
        } else if(t>k){ //排名k的结点在左子树
            return select(x.left, k);
        }else{ 
            //排名k的在右子树
            return select(x.right, k-t-1);
        }
    }
    
    /** * 返回给定键key的排名 */
    public int rank(Key key){ 
        return rank(root, key);
    }
    /** * 在二叉排序树x上返回key的排名 * @param x * @param key * @return */
    private int rank(Node x, Key key){ 
        if(x == null){ 
            return 0;
        }
        int cmp = key.compareTo(x.key);
        if(cmp < 0){ 
            //key键小于root的key,所以key在左子树中
            return rank(x.left, key);
        } else if(cmp>0){ 
            //key大于root的key,所以key在右子树中
            return 1+size(x.left)+rank(x.right, key);
        } else{ 
            return size(x.left)+1;
        }
    }

## 7. 删除最小键值和最大键值的结点。 ##

删除二叉排序树中的最大键值和最小键值的结点。这里的思想和找到最大键值和最小键值结点几乎一样。只是这里需要删除该结点。由于最大键值和最小键值的位置的特殊性，都在叶子结点，所以这里的删除都是比较简单的，不涉及到子树的移动。源码如下：

/** * 删除键值最小结点 */
    public void deleteMin(){ 
        //删除root二叉查找树中的最小key的结点,其实也就是最左边的结点
        root = deleteMin(root);
    }
    /** * 删除键值最小结点 * @param x * @return 返回新的二叉查找树的根节点 */
    private Node deleteMin(Node x){ 
        if(x.left == null){ 
            return x.right;//删除根节点,这时返回的是新的二叉查找树的根节点
        }
        x.left = deleteMin(x.left);
        x.N = size(x.left) + size(x.right) + 1;
        return x;
    }
    
    /** * 删除:键值最大结点 */
    public void deleteMax(){ 
        //删除root二叉查找树中的最小key的结点,其实也就是最左边的结点
        root = deleteMax(root);
    }
    /** * 删除 * @param x * @return 返回新的二叉查找树的根节点 */
    private Node deleteMax(Node x){ 
        if(x.right == null){ //右子树为空
            return x.left;//删除根节点,这时返回的是新的二叉查找树的根节点
        }
        x.right = deleteMax(x.right);
        x.N = size(x.left) + size(x.right) + 1;
        return x;
    }

## 8. 删除任意结点 ##

这里的删除指删除二叉排序树中任意位置的结点x，这个时候的结点x就有如下4种情况：  
首先做个约定：待删除的结点是结点x，其父结点是结点p，左子树结点是l，右子树结点是r，兄弟结点为b。其中NIL均为虚拟的null结点。(以上结点均在存在的情况下)  
1、当待删除结点x位于叶子结点位置：  
这时直接删除该叶子结点x，并将其父结点p指向该结点的域设置为null。  
![待删除结点x位于叶子结点][x]  
这时只要删除叶子结点x，然后将p的左结点指向NIL 结点：  
![删除叶子结点之后][SouthEast]

2、当待删除结点x只有一个子结点时(该结点只有左子树或则右子树：即左子树和右子树中有一个为空)，这时将x结点的父结点p指向待删除的结点x的指针直接指向x结点的唯一儿子结点(l或则是r)，然后删除x结点就OK了。下图只演示只有左子树的时候，只有右子树时候相同：  
![待删除结点x只有一个左子结点时][x 1]  
这时只用删除x结点，并将p结点左子树指向x的子结点L. 如下图：  
![删除结点x之后][x 2]

3、当待删除结点x有两个子结点的时候，这时候删除待删除结点x是最麻烦的。一个最经典的方案是：用删除结点x的后继结点填补它的位置。因为x有一个右子结点，因此它的后继结点就是右子树中的最小结点，这样替换就能保证有序性，因为x.key和它的后继之间不存在其他的键。我们用下面的4个步骤解决x替换为它后继结点的任务：  
1）将指向即将被删除的结点x的链接保存为t;

2）将x指向它的后继结点min(x.right);

3）将x的右链接指向deleteMin(t.right) (这里也就是右子树删除最小结点之后的)，也就是删除最小结点后，其右子树所有节点都仍大于x.key的右子二叉查找树。

4）将x的左链接(本为空)设为t.left(其下所有的键都小于被删除的结点和它的后继结点)。

源码如下：

/** * 删除键key结点. * @param key */
    public void delete(Key key){ 
        root = delete(root, key);
    }
    /** * 删除以x为根结点的二叉查找树的key键的结点 * @param x * @param key * @return 新的二叉查找树的根节点 */
    private Node delete(Node x, Key key){ 
        if( x == null ){ 
            return null;
        }
        int cmp = key.compareTo(x.key);
        if (cmp < 0) { 
            x.left = delete(x.left, key);
        } else if(cmp > 0){ 
            x.right = delete(x.right, key);
        } else { //这时删除根节点x
            if(x.left == null){ 
                return x.right;
            }
            if(x.right == null){ 
                return x.left;
            }
            //根节点有左右子树
            Node t = x;
            //1. 先求出x的右子树中最小键值的结点并让x指向它.
            x = min(t.right);
            //2. 将t的右子树删除最小的结点之后的根节点返回
            x.right = deleteMin(t.right);
            //3. 将t的左子树给x的左子树
            x.left = t.left;
        }
        x.N = size(x.left) + size(x.right) + 1;
        return x;
    }

# 二叉搜索树的 golang 实现 #

下面是我后来用golang实现的版本

package binary_search_tree
    
    /** 定义数据结构 */
    type BinarySearchNode struct { 
    	key   int
    	value string
    	left  *BinarySearchNode
    	right *BinarySearchNode
    }
    
    /** 定义一个二叉查找树 */
    type BinarySearchTree struct { 
    	root *BinarySearchNode
    	size int
    }
    
    func newBinarySearchNode(k int, v string) *BinarySearchNode { 
    	return &BinarySearchNode{ 
    		key:   k,
    		value: v,
    		left:  nil,
    		right: nil,
    	}
    }
    
    func newBinarySearchTree() *BinarySearchTree { 
    	return &BinarySearchTree{ 
    		root: nil,
    		size: 0,
    	}
    }
    
    /** 返回是否插入成功 */
    func (bst *BinarySearchTree) Put(k int, v string) bool { 
    	if bst.root == nil { 
    		bst.root = &BinarySearchNode{ 
    			key:   k,
    			value: v,
    			left:  nil,
    			right: nil,
    		}
    		bst.size++
    		return true
    	}
    	succ := insert(bst.root, k, v)
    	if succ { 
    		bst.size++
    	}
    	return succ
    }
    
    func (bst *BinarySearchTree) Delete(k int) bool { 
    	if bst == nil { 
    		panic("binary search tree is nil")
    	}
    	return delete(bst.root, k) != nil
    }
    
    func (bst *BinarySearchTree) Get(k int) (string, bool) { 
    	if bst == nil { 
    		panic("binary search tree is nil")
    	}
    	return get(bst.root, k)
    }
    
    /** insert or update precondition: root is not nil 如果当前结点为nil, 表示bsn为根节点，且为nil, 直接panic 如果当前结点的key大于k, 那么递归插入左结点； 如果当前结点的key小于k, 那么递归插入右结点； */
    func insert(root *BinarySearchNode, k int, v string) bool { 
    	if root == nil { 
    		// occur only root is nil
    		panic("root is nil")
    	}
    	if k < root.key && root.left != nil { 
    		//recursively insert into left
    		return insert(root.left, k, v)
    	} else if k < root.key && root.left == nil { 
    		//insert into left
    		root.left = &BinarySearchNode{ 
    			key:   k,
    			value: v,
    			left:  nil,
    			right: nil,
    		}
    		return true
    	} else if k > root.key && root.right != nil { 
    		//recursively insert into right
    		return insert(root.right, k, v)
    	} else if k > root.key && root.right == nil { 
    		root.right = &BinarySearchNode{ 
    			key:   k,
    			value: v,
    			left:  nil,
    			right: nil,
    		}
    		return true
    	} else { 
    		// update current node
    		root.value = v
    		return true
    	}
    }
    
    /** delete a node named k */
    func delete(root *BinarySearchNode, k int) *BinarySearchNode { 
    	if root == nil { 
    		panic("delete from nil tree")
    	}
    	if root.key > k && root.left != nil { 
    		root.left = delete(root.left, k)
    	} else if root.key > k && root.left == nil { 
    		// k is not existed, return success
    		return nil
    	} else if root.key < k && root.right != nil { 
    		root.right = delete(root.right, k)
    	} else if root.key < k && root.right == nil { 
    		// k is not existed, return success
    		return nil
    	} else { 
    		// root.key == key， delete current node
    		if root.left != nil && root.right != nil { 
    			// both left child and right child of this bsn are not nill
    			// find the min key which is greater than root.key
    			minNode := findMin(root.right)
    			root.key = minNode.key
    			root.value = minNode.value
    			delete(root.right, root.key)
    		} else { 
    			// single child or no child
    			if root.left == nil { 
    				root = root.right
    			} else { 
    				root = root.left
    			}
    		}
    	}
    	return root
    }
    
    func get(root *BinarySearchNode, k int) (string, bool) { 
    	if root == nil { 
    		return "", false
    	}
    	if root.key == k { 
    		return root.value, true
    	} else if root.key > k && root.left != nil { 
    		return get(root.left, k)
    	} else if root.key < k && root.right != nil { 
    		return get(root.right, k)
    	} else { 
    		return "", false
    	}
    }
    
    /** 从root结点开始找到最小key的节点 */
    func findMin(root *BinarySearchNode) *BinarySearchNode { 
    	if root == nil { 
    		panic("the tree is nil")
    	}
    	if root.left != nil { 
    		return findMin(root.left)
    	} else { 
    		return root
    	}
    }

然后做了一些测试

package binary_search_tree
    
    import (
    	"fmt"
    	"strconv"
    	"testing"
    )
    
    /* 33 / \ 22 44 / \ / \ 11 28 40 49 / \ /\ \ \ 7 16 25 30 42 60 */
    func prepare_data() (*BinarySearchNode, int) { 
    	root := &BinarySearchNode{ 
    		key:   33,
    		value: "33",
    	}
    	key_22 := &BinarySearchNode{ 
    		key:   22,
    		value: "22",
    	}
    	key_44 := &BinarySearchNode{ 
    		key:   44,
    		value: "44",
    	}
    	key_11 := &BinarySearchNode{ 
    		key:   11,
    		value: "11",
    	}
    	key_28 := &BinarySearchNode{ 
    		key:   28,
    		value: "28",
    	}
    	key_40 := &BinarySearchNode{ 
    		key:   40,
    		value: "40",
    	}
    	key_49 := &BinarySearchNode{ 
    		key:   49,
    		value: "49",
    	}
    	key_7 := &BinarySearchNode{ 
    		key:   7,
    		value: "7",
    	}
    	key_16 := &BinarySearchNode{ 
    		key:   16,
    		value: "16",
    	}
    	key_25 := &BinarySearchNode{ 
    		key:   25,
    		value: "25",
    	}
    	key_30 := &BinarySearchNode{ 
    		key:   30,
    		value: "30",
    	}
    	key_42 := &BinarySearchNode{ 
    		key:   42,
    		value: "42",
    	}
    	key_60 := &BinarySearchNode{ 
    		key:   60,
    		value: "60",
    	}
    	/* 33 / \ 22 44 / \ / \ 11 28 40 49 / \ /\ \ \ 7 16 25 30 42 60 */
    	root.left = key_22
    	root.right = key_44
    	key_22.left = key_11
    	key_22.right = key_28
    	key_44.left = key_40
    	key_44.right = key_49
    	key_11.left = key_7
    	key_11.right = key_16
    	key_28.left = key_25
    	key_28.right = key_30
    	key_40.right = key_42
    	key_49.right = key_60
    
    	return root, 13
    }
    
    func TestBinarySearchTree_Get(t *testing.T) { 
    	root, num := prepare_data()
    	bst := &BinarySearchTree{ 
    		root: root,
    		size: num,
    	}
    	fmt.Println(bst.Get(42))
    }
    
    /* 33 / \ 22 44 / \ / \ 11 28 40 49 / \ /\ \ \ 7 16 25 30 42 60 */
    func TestBinarySearchTree_Put(t *testing.T) { 
    	root, num := prepare_data()
    	bst := &BinarySearchTree{ 
    		root: root,
    		size: num,
    	}
    	fmt.Println(bst.Put(7, "6"))
    	val, ok := bst.Get(7)
    	fmt.Println("Get key = 7, ", ok, ", val=", val)
    }
    
    /* 33 / \ 22 44 / \ / \ 11 28 40 49 / \ /\ \ \ 7 16 25 30 42 60 */
    func TestBinarySearchTree_Delete(t *testing.T) { 
    	root, num := prepare_data()
    	bst := &BinarySearchTree{ 
    		root: root,
    		size: num,
    	}
    	ok := bst.Delete(33)
    	fmt.Println(ok)
    	fmt.Println(bst.Get(7))
    }
    
    func TestBinarySearchTree_Put2(b *testing.T) { 
    	root, num := prepare_data()
    	bst := &BinarySearchTree{ 
    		root: root,
    		size: num,
    	}
    	for i := 0; i < 10000; i++ { 
    		bst.Put(int(i), strconv.Itoa(i))
    	}
    	for i := 0; i < 10000; i++ { 
    		fmt.Println(bst.Get(int(i)))
    	}
    }
    
    func TestBinarySearchTree_Put3(b *testing.T) { 
    	prepare_data()
    	m := make(map[int]*BinarySearchNode)
    	for i := 0; i < 10000; i++ { 
    		m[i] = &BinarySearchNode{ 
    			key:   i,
    			value: strconv.Itoa(i),
    			left:  nil,
    			right: nil,
    		}
    	}
    	for i := 0; i < 10000; i++ { 
    		fmt.Println(m[i])
    	}
    }
    
    func BenchmarkBinarySearchTree_Put(b *testing.B) { 
    	root, num := prepare_data()
    	bst := &BinarySearchTree{ 
    		root: root,
    		size: num,
    	}
    	for i := 0; i < 10000; i++ { 
    		bst.Put(int(i), strconv.Itoa(i))
    	}
    	for i := 0; i < 10000; i++ { 
    		bst.Get(int(i))
    	}
    }

[x]: /images/20220713/d638c1e856514c339c950a361656a1d3.png
[SouthEast]: /images/20220713/4a2f002d4e8c4aaeb82c61fabceaf8bf.png
[x 1]: /images/20220713/bb0bbf7dd31a4a01910520d5fdeb3cff.png
[x 2]: /images/20220713/3b09bad2cb2b4280875d48d1048e84b3.png