3. 迭代器迭代时，下一个节点总是指向当前节点的直接后继

  
     * 二叉搜索树 迭代器实现
     * class Itr implements Iterator<Map.EntryNode<K,1)">
         * 当前迭代节点
         *  currentNode;

        
         * 下一个节点
         *  nextNode;

         Itr() {
            :::初始化时，nextNode指向第一个节点
            this.nextNode = TreeMap..getFirstNode();
        }

        @Override
         hasNext() {
            this.nextNode != );
        }

        @Override
        public Map.EntryNode<K,1)"> next() {
            this.currentNode = .nextNode;

            this.getSuccessor(.nextNode);

            .currentNode;
        }

        @Override
         remove() {
            this.currentNode == new IteratorStateErrorException("迭代器状态异常: 可能在一次迭代中进行了多次remove操作");
            }

            :::判断当前被删除的节点是否同时存在左右孩子
            this.currentNode.left != null && this.currentNode.right != 
                    同时存在左右孩子的节点删除时当前节点会和直接后继(nextNode)进行交换
                    因此nextNode指向当前节点
                 */
                this.nextNode = .currentNode;
            }
            :::删除当前节点
            TreeMap.this.deleteEntryNode(.currentNode);

            :::currentNode设置为null，防止反复调用remove方法
            ;
        }
    }

5.二叉搜索树性能

5.1 空间效率

　　二叉搜索树的内部节点除了key，value的引用，同时还维护着双亲，左右孩子节点的引用(不一定存在)，因此其空间效率比链表稍差，更是不如向量结构紧凑。但是这一点点空间效率的损失，带来的是二叉搜索树全面而优异的增删改查效率。

5.2 时间效率

　　二叉搜索树的插入，删除依赖于查询接口，而查询接口是以二分查找的方式实现的。在理想状态下(平衡的)，二叉搜索树的增删改查接口的效率为(O(logN))，N为当前二叉搜索树存储的元素总数；也可以说，二叉搜索树增删改查接口的效率正比于二叉搜索树的高度。

6.二叉搜索树总结

6.1 当前版本缺陷：

　　至此，我们实现了一个最基础的二叉搜索树，但还存在一个致命缺陷：

　　二叉搜索树在插入数据时，以二分查找的方式确定插入的位置。但是当插入数据的数据不够随机时，会降低二叉搜索树的查询效率。举个极端例子，当按照顺序插入1到10000的元素以从小到大顺序插入，二叉搜索树将退化为一个一维的链表(极端不平衡)，查询效率从O(logN)急剧降低为O(n)。

　　我们希望在插入，删除元素时，通过及时的调整二叉搜索树结构，用一系列等价变换的操作，使二叉搜索树始终保持一个适度平衡的状态。我们称这样的二叉搜索树为平衡二叉搜索树(Balanced?Binary?Search?Tree)，常见的平衡二叉搜索树有AVL树、红黑树等。

　　只有平衡二叉搜索树才能始终保证始终高效的查询效率(O(logN))，而不会因为极端数据集合的插入，造成效率的大幅降低。

6.2 完整代码

（编辑：网站开发网_盐城站长网 ）

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