自己动手实现java数据结构(六)二叉搜索树(3)
当key值对应的目标节点不存在时,运用哨兵的思想,通过双亲节点和哨兵节点的相对位置,在目标位置插入一个新的节点。 @Override V put(K key,V value) { this.root = new EntryNode<>(key,value); this.size++; :::获得目标节点 TargetEntryNode<K,V> targetEntryNode = getTargetEntryNode(key); if(targetEntryNode.relativePosition == RelativePosition.CURRENT){ :::目标节点存在于当前容器 :::暂存之前的value V oldValue = targetEntryNode.target.value; :::替换为新的value targetEntryNode.target.value =:::返回之前的value oldValue; }:::目标节点不存在于当前容器 EntryNode<K,1)"> targetEntryNode.parent; RelativePosition.LEFT){ :::目标节点位于左边 parent.left = :::目标节点位于右边 parent.right = ; } } 3.5 二叉搜索树删除接口实现二叉搜索树节点在被删除时,被删除节点存在三种情况: 1.不存在任何孩子节点(既没有左孩子,也没有右孩子) 直接将双亲节点和当前节点的连接切断(双亲对应孩子节点引用置为null)。 2.只存在一个孩子节点(只存在左孩子或者只存在右孩子) 被删除节点唯一的孩子节点代替被删除节点本身,唯一的孩子节点和双亲节点直接相连。 3.既有左孩子节点,又有右孩子节点 找到被删除节点的直接后继节点(直接前驱节点也行,本质上是保证删除之后依然保证有序性),将被删除节点和其直接后继交换位置。 当右孩子节点存在时,直接后继节点必定存在于右子树中,并且其直接后继一定不存在左孩子节点(否则就不是直接后继节点了),因此被删除节点的直接后继节点至多只存在一个右孩子节点(或没有任何孩子节点)。在两者交换位置后,可以转换为第一或第二种情况进行处理。 节点删除前: 1.无孩子节点的删除: ? 2. 只有一个孩子节点的删除: 3. 拥有两个孩子的节点的删除: 二叉搜索树节点删除代码实现: V remove(K key) { :::查询目标节点 TargetEntryNode<K,1)">if(targetEntryNode.relativePosition !=:::没有找到目标节点 ; }:::找到了目标节点 :::从二叉树中删除目标节点 deleteEntryNode(targetEntryNode.target); targetEntryNode.target.value; } } * 将目标节点从二叉搜索树中删除 * target 需要被删除的节点 * void deleteEntryNode(EntryNode<K,1)">/* * 删除二叉搜索树节点 * 1.无左右孩子 * 直接删除 * 2.只有左孩子或者右孩子 * 将唯一的孩子和parent节点直接相连 * 3.既有左孩子,又有右孩子 * 找到自己的直接前驱/后继(左侧的最右节点/右侧的最左节点) * 将自己和直接后继进行交换,转换为第1或第2种情况,并将自己删除 * */ :::size自减1 this.size--; :::既有左孩子,又有右孩子 if(target.left != null && target.right != :::找到直接后继(右侧的最左节点) EntryNode<K,V> targetSuccessor = getSuccessor(target); :::target的key/value和自己的后继交换 target.key = targetSuccessor.key; target.value = targetSuccessor.value; :::target指向自己的后继,转换为第一/第二种情况 target = targetSuccessor; } EntryNode<K,1)"> target.parent; :::获得代替被删除节点原先位置的节点(从左右孩子中选择一个) EntryNode<K,V> replacement = (target.left != null ? target.left : target.right); if(replacement == :::无左右孩子 :::被删除的target是根节点,且无左右孩子 if(parent == :::全树置空 ; }{ RelativePosition relativePosition = getRelativeByParent(parent,target); :::直接删除,断开和双亲节点的联系 if(relativePosition == RelativePosition.LEFT){ parent.left = ; }{ parent.right = ; } target.parent = ; } }:::只有左孩子或者右孩子 :::被删除的target是根节点,且只有左孩子或者右孩子 if(target.parent == :::将存在的子树孩子节点,设置为根节点 this.root = replacement; }{ replacement.parent = target.parent; RelativePosition relativePosition =:::被删除节点的双亲节点指向被代替的节点 RelativePosition.LEFT){ parent.left = replacement; }{ parent.right = replacement; } } } } 3.6?二叉搜索树查询接口实现二叉搜索树的查询接口使用了getTargetEntryNode方法。 (编辑:ASP站长网) |