自己动手实现java数据结构（六）二叉搜索树

　　当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方法。

（编辑：永州站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!