【数据结构】二叉排序树BST
二叉排序树二叉排序树(Binary Sort Tree)也叫二叉搜索树(Binary Search Tree) 二叉排序树本质上还是一个二叉树,只不过在其上定义了一些规则:一个结点的左子树中所有的结点不大于该结点的值,而其右子树中的所有结点不小于该结点的值。由此规则可得BST中序遍历是有序的。 BST中定义的操作有: minNode:某个子树中的关键字最小的结点 maxNode:某个子树中的关键字最大的结点 search:搜索某个关键字 predecessor:某个节点的前驱 successor:某个节点的后继 insert:在BST中插入一个元素 delete:在BST中删除一个元素 研究二叉排序树最主要的就是上述操作在BST中的时间复杂度为O(h),h为树高。 相关算法1.某棵子树中关键字最小的结点由BST的性质,沿着该结点的左分支往下走到最后一个结点 public BinaryTreeNode minNode(BinaryTreeNode node) { while (node.lchild != null) { node = node.lchild; } return node; } 2.某棵子树中关键字最大的结点 由BST的性质,沿着该结点的右分支往下走到最后一个结点 public BinaryTreeNode maxNode(BinaryTreeNode node) { while (node.rchild != null) { node = node.rchild; } return node; } 3.搜索 BST中的搜索类似于折半查找,因为BST的中序遍历就是一个有序数组。 public BinaryTreeNode search(BinaryTreeNode root,int e) { if (e == root.data || root == null) return root; if (e < root.data) return search(root.lchild,e); else return search(root.rchild,e); } 4.某个结点的前驱 如有左子树,那么返回左子树中的最小结点即可。 无左子树,沿着父节点往上走,知道到达这样的结点:其父节点为空(到达根)或者作为某个结点的右子树。 public BinaryTreeNode predecessor(BinaryTreeNode node) { if (node.lchild != null) return maxNode(node.lchild); BinaryTreeNode parent = node.parent; while (parent != null && parent.lchild == node) { node = parent; parent = node.parent; } return parent; } 5.某个结点的后继和前驱的算法类似 具体思路如下
6.在BST中插入一个元素 具体思路如下
具体的实现代码为 public void insert(BinaryTreeNode insertNode) { // O(lgn) BinaryTreeNode p = root,parent = null; while (p != null) { parent = p; // 注意位置 if (insertNode.data < p.data) p = p.lchild; else p = p.rchild; } // 出循环时,p为null,parent为要插入在该节点下面 insertNode.parent = parent; if (root == null) { root = insertNode; } else if (insertNode.data < parent.data) { // 将节点插入到parent的左边 parent.lchild = insertNode; } else { parent.rchild = insertNode; } } 插入结点的递归版本 这里我将跳出递归的条件设置为root.lchild/rchild == null,好处就是直接在root后面添加孩子就行了,不用再额外保存父亲结点。 public void insertRecur(BinaryTreeNode root,BinaryTreeNode insertNode) { // 递归终止条件 if (this.root == null) { this.root = insertNode; return; } else if (insertNode.data < root.data && root.lchild == null) { root.lchild = insertNode; insertNode.parent = root; return; } else if (insertNode.data >= root.data && root.rchild == null) { root.rchild = insertNode; insertNode.parent = root; return; } // 递归的往左右孩子插入 if (insertNode.data < root.data && root.lchild != null) insertRecur(root.lchild,insertNode); if (insertNode.data >= root.data && root.rchild != null) { insertRecur(root.rchild,insertNode); } }同时,通过插入方法也可以创建BST。只需循环的往里面插入节点即可。
7.在BST中删除一个元素 1.删除叶子结点----->仅需调整其父结点的指针 具体情况如下图
注意上面提到的“代替”,代替并不简单的是node = node.lchild这样的一句赋值,实际上要包含以下操作: 1.如果该结点是它父结点的左孩子,那么,将他的父结点的左孩子赋值为另一个结点 2.如果该结点是它父结点的右孩子,那么,将他的父结点的右孩子赋值为另一个结点 3.最后将用来代替的那个结点的父亲设置为被代替节点的父亲 此外还要注意被替换结点没有父亲节点的情况,也就是删除根。 下面是我最开始写出来的代码,其实看起来非常的混乱 public void deleted(BinaryTreeNode node) { if (node.lchild == null) { // 左子树为空,只需要移植右子树 // -------1.用该结点的右子树代替它------- // node = node.rchild; if (node.parent == null) { root = node.rchild; } else if (node == node.parent.lchild) { node.parent.lchild = node.rchild; } else { node.parent.rchild = node.rchild; } if (node.rchild != null) node.rchild.parent = node.parent; } else if (node.rchild == null) { // -------2.用该结点的左子树代替它------- // node = node.lchild; if (node.parent == null) { root = node.lchild; } else if (node == node.parent.lchild) { node.parent.lchild = node.lchild; } else { node.parent.rchild = node.lchild; } if (node.lchild != null) node.lchild.parent = node.parent; } else { BinaryTreeNode predecessorOfnode = predecessor(node); // -------3.用该结点的右子树代替它------- if (node.parent == null) { root = node.lchild; } else if (node.parent.lchild == node) { node.parent.lchild = node.lchild; } else if (node.parent.rchild == node) { node.parent.rchild = node.lchild; } node.lchild.parent = node.parent; node.rchild.parent = predecessorOfnode; // -------4.将右子树赋值给它的前驱------- predecessorOfnode.rchild = node.rchild; node.rchild.parent = predecessorOfnode; } }上面的代码存在大量的重复,将其抽出来一个替换的方法 // 用node2来替代node1 private void replace(BinaryTreeNode node1,BinaryTreeNode node2){ // node2可以为null,这样就将删除叶子结点的情况包含在里面了 if (node1.parent == null) { root = node2; } else if (node1 == node1.parent.lchild) { node1.parent.lchild = node2; } else { node1.parent.rchild = node2; } if (node2 != null) node2.parent = node1.parent; }于是删除的方法可以写为 public void delete(BinaryTreeNode node) { if (node.lchild == null) { // 左子树为空,只需要移植右子树 replace(node,node.rchild); } else if (node.rchild == null) { replace(node,node.lchild); } else { BinaryTreeNode predecessorOfnode = predecessor(node); replace(node,node.lchild); predecessorOfnode.rchild = node.rchild; node.rchild.parent = predecessorOfnode; } }
BST的实现继承上一篇博客的BinaryTree类,这样就可以调用遍历算法了 public class BinarySearchTree extends BinaryTree { // 从数组创建二叉树 @Override public void createTree(int[] array) { // 最多是O(nlgn) // 从一个数组创建二叉搜索树 for (int i : array) { insertRecur(root,new BinaryTreeNode(i)); } } // 某个子树的最小结点 public BinaryTreeNode minNode(BinaryTreeNode node) { while (node.lchild != null) { node = node.lchild; } return node; } //某个子树的最大结点 public BinaryTreeNode maxNode(BinaryTreeNode node) { while (node.rchild != null) { node = node.rchild; } return node; } // 搜索关键字为e的结点,并返回该结点的引用 public BinaryTreeNode search(BinaryTreeNode root,int e) { if (root == null || e == root.data) // 注意顺序 return root; if (e < root.data) return search(root.lchild,e); } // 插入结点,递归版本 public void insertRecur(BinaryTreeNode root,BinaryTreeNode insertNode) { // O(lgn) if (this.root == null) { this.root = insertNode; return; } else if (insertNode.data < root.data && root.lchild == null) { root.lchild = insertNode; insertNode.parent = root; return; } else if (insertNode.data >= root.data && root.rchild == null) { root.rchild = insertNode; insertNode.parent = root; return; } if (insertNode.data < root.data && root.lchild != null) insertRecur(root.lchild,insertNode); } } // 插入节点,非递归版本 public void insert(BinaryTreeNode insertNode) { // O(lgn) BinaryTreeNode p = root,parent = null; while (p != null) { parent = p; // 注意位置 if (insertNode.data < p.data) p = p.lchild; else p = p.rchild; } // 出循环时,p为null,parent为要插入在该节点下面 insertNode.parent = parent; if (root == null) { root = insertNode; } else if (insertNode.data < parent.data) { // 将节点插入到parent的左边 parent.lchild = insertNode; } else { parent.rchild = insertNode; } } // 用node2来替代node1 private void replace(BinaryTreeNode node1,BinaryTreeNode node2){ // node2可以为null,这样就将删除叶子结点的情况包含在里面了 if (node1.parent == null) { root = node2; } else if (node1 == node1.parent.lchild) { node1.parent.lchild = node2; } else { node1.parent.rchild = node2; } if (node2 != null) node2.parent = node1.parent; } // 删除某个结点 public void delete(BinaryTreeNode node) { if (node == null) return; if (node.lchild == null) { // 左子树为空,只需要移植右子树 replace(node,node.lchild); predecessorOfnode.rchild = node.rchild; node.rchild.parent = predecessorOfnode; } } // 删除某个结点 @Deprecated public void deleted(BinaryTreeNode node) { if (node == null) return; if (node.lchild == null) { // 左子树为空,只需要移植右子树 // -------1.用该结点的右子树代替它------- // node = node.rchild; if (node.parent == null) { root = node.rchild; } else if (node == node.parent.lchild) { node.parent.lchild = node.rchild; } else { node.parent.rchild = node.rchild; } if (node.rchild != null) node.rchild.parent = node.parent; } else if (node.rchild == null) { // -------2.用该结点的左子树代替它------- // node = node.lchild; if (node.parent == null) { root = node.lchild; } else if (node == node.parent.lchild) { node.parent.lchild = node.lchild; } else { node.parent.rchild = node.lchild; } if (node.lchild != null) node.lchild.parent = node.parent; } else { BinaryTreeNode predecessorOfnode = predecessor(node); // -------3.用该结点的右子树代替它------- if (node.parent == null) { root = node.lchild; } else if (node.parent.lchild == node) { node.parent.lchild = node.lchild; } else if (node.parent.rchild == node) { node.parent.rchild = node.lchild; } node.lchild.parent = node.parent; node.rchild.parent = predecessorOfnode; // -------4.将右子树赋值给它的前驱------- predecessorOfnode.rchild = node.rchild; node.rchild.parent = predecessorOfnode; } } // 返回某个节点node的前驱 public BinaryTreeNode predecessor(BinaryTreeNode node) { if (node.lchild != null) return maxNode(node.lchild); BinaryTreeNode parent = node.parent; while (parent != null && parent.lchild == node) { node = parent; parent = node.parent; } return parent; } // 返回某个节点node的后继 public BinaryTreeNode successor(BinaryTreeNode node) { if (node.rchild != null) return minNode(node.rchild); BinaryTreeNode parent = node.parent; while (parent != null && parent.rchild == node) { node = parent; parent = node.parent; } return parent; } }
测试
public static void main(String[] args) { BinarySearchTree bst = new BinarySearchTree(); int[] array = {1,9,2,7,4,5,3,6,8}; bst.createTree(array); System.out.println("中序递归遍历"); bst.inOrder(bst.root); System.out.println(""); System.out.println("层序遍历"); bst.levelOrderH(); bst.delete(bst.search(bst.root,4)); System.out.println("将4删除后在中序递归遍历"); bst.inOrder(bst.root); } 输出
中序递归遍历 1 2 3 4 5 6 7 8 9 层序遍历 1 9 2 7 4 8 3 5 6 将4删除后在中序递归遍历 1 2 3 5 6 7 8 9 上面这棵树的形态大致如下
可以清楚地看到,虽然这棵树严格满足BST的要求,但是这棵树是比较深的,而上述操作的时间复杂度直接与树的深度有关,也就是说如果创建的树高度太高,就会直接影响到BST上的操作的性能,因为上述操作的时间复杂度均为O(h),不要想当然地认为O(h)就是O(lgn)。像上面的这棵树,我们说他是不平衡的,平衡看起来,直观感受是做右子树高度差不多。平衡的二叉排序树即BBST,它的平均深度才为O(lgn),就能将上述操作的时间复杂度控制在O(lgn)以内。 (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |